The world’s leading publication for data science, AI, and ML professionals.

How to reduce the environmental impact of freight ?

Building a route optimizer to minimize co2 emissions

Building an app to provide CO2 optimized routes through a multimodal network

Photo by Viktor Hanacek on picjumbo
Photo by Viktor Hanacek on picjumbo

The context

Moving goods and raw materials efficiently is a must for any firm nowadays. This dependency comes along with a major challenge: freight represents about 8% of the total greenhouse gases emitted in the U.S.

Green house gases emitted in the US. Data from EPA and BTS [1,2]. Figure by author.
Green house gases emitted in the US. Data from EPA and BTS [1,2]. Figure by author.

So how could shippers reduce the carbon footprint of their loads? And what would be the tradeoffs?

The answer to the first question is relatively straightforward: optimize shipments by using less carbon-intensive transportation modes. The second questions’ answer is more nuanced, but in general, using more environmental-friendly logistic solutions will cost less and take more time to arrive at destination.

To demonstrate these answers, I built a simplified model that provides an optimized multimodal (rail and road) route based on the departure, the destination positions, and some parameters to be optimized. In this post, I will take you through this project as I hope to inspire you to work on things that matter.


Building a simplified multimodal network simulator with Dash

I like to kick off my projects by building a simplified version first. This helps to:

  • Move fast, not stay stuck on details.
  • Keep track of the details that will require special attention when building the final model.
  • Get instantaneous gratification.
  • Share a non-confidential version of the project with the community.

For this simplified version of the project, I set up a Dashboard app in Python where the user can interactively explore some multimodal optimized routes and understand the tradeoffs with truckload shipments.

Data

The generated multimodal network. Green lines are rail segments, blue are highways and red dots are intermodal terminals. Figure by author.
The generated multimodal network. Green lines are rail segments, blue are highways and red dots are intermodal terminals. Figure by author.

Anyone who has worked with road networks knows how large these files can become on a continental scale. As the goal is to make the Dashboard as simple as possible, the road network has been approximated by the highway network. Both, the highway network and the rail network are available on the BTS database [3]. The two data sets have been cleaned and simplified using the OSMnx package [4]. This simplification is crucial as the graph is relatively heavy and it contains many nodes with two edges that can be contracted.

Optimization parameters

To understand the trade-off of greener shipments, the user can select the feature to be optimized: CO2 emissions, cost, or duration.

The CO2 data is based on USLCI database [5], the duration is computed from the track speed limits, and the costs are computed by aggregating historical data.

Routing algorithm

To find the optimal path for a given parameter, three simple routing algorithms have been tested: Dijkstra, Bidirectional Dijkstra and Astar (A*). Using more advanced path search algorithms, like contraction hierarchies, is not very useful if you want to use Python because of the language’s relative slowness. The gif below shows how these algorithms iterate to find the optimal path. Astar being goal-directed, it will run through the fewest iterations.

Network exploration to find the least polluting path from Charlotte to Denver. GIF by author.
Network exploration to find the least polluting path from Charlotte to Denver. GIF by author.

Nevertheless, for each new node, Astar has to compute the heuristic, which takes time. Moreover, as most routes queried will be medium to long-haul, the borders of the graph are often reached during the graph search, thus limiting the running time of no-goal directed methods. For these reasons and for this specific graph, it was found that the fastest solution, on average, is Bidirectional Dijkstra search.

Simplifications

Simplifications and abstraction had to be done due to the lack of open source available data:

  • The costs have limited accuracy in this simplified version of the project as they are not time-dependent and they have low granularity.
  • The railroad route combinations may not be relevant as it is assumed that all combinations are feasible. In fact, rail firms don’t collaborate with all their peers: they have specific partnerships. Some routes provided by this model will thus not be applicable to real-life situations, but it gives a good sense of how the final model will work.

Dash app

To make the app interactive, I used Dash. A handy, easy-to-use dashboard developed by the Plotly community [6]. The biggest challenge when building the app is to make it respond as quickly as possible to provide a smooth user experience. As this application is based on a heavy graph, the run-time bottleneck resides in loading the graph. Here are two simple methods I applied to reduce this bottleneck:

  1. Avoid loading the entire graph for each new request: Instead of reloading or rebuilding the graph for every request, edges are removed depending on the selected rail operators. They are then added back at the end of the query.
  2. Reduce the memory usage of the graph: Simplify the graph to an undirected graph and change the variables dtypes (i.e float to int)

The deployment of the app was done with Heroku [7]. You can try it out on this link. Please be patient, even with the above-mentioned optimizations, the run time is not top-notch 😅

Dash app. GIF by author.
Dash app. GIF by author.

Result

In most cases, multimodal shipments emit significantly less CO2, they cost less but they take longer than Truckload. Thus, firms for whom shipment time is not too constraining could use a multimodal solution to pay less and be more environmentally friendly.

The final model

At Loadsmart we want to be the number one marketplace for freight transportation. We want to provide shippers optimized and tailored solutions for their logistics needs. To that end, the final model of this project will propose optimized multimodal shipments with real time pricing and scheduling to help shippers decarbonize their operations by making their supply chain greener.

The final model will be based on a modified version of the CSA algorithm [8] using multi-criteria Pareto set optimization and fuzzy logic ranking. If there is some interest from the community, I could write an article about this model.

Acknowledgments

Except for the cost data, this simplified version of the project was built entirely from Open Source data, models, services and references.

I would like to thank the whole community for sharing so much. Let’s use this knowledge to build tools for the greater purpose.

You can have a look at the code on this Github repo. I would be more than happy to get any feedback/questions.

Notes

[1] United States Environmental Protection Agency. "Inventory of U.S. Greenhouse Gas Emissions and Sinks" (2018). link

[2] Bureau of Transportation Statistics. Energy Consumption by Select Freight Transportation Modes (2018). link

[3] Bureau of Transportation Statistics | National Transportation Atlas Database. link

[4] Boeing, G. (2017) "OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks." link

[5] U.S. Life Cycle Inventory Database (USLCI). link

[6] Plotly Dash. link

[7] Heroku. link

[8] Julian Dibbelt et al. (2013) "Intriguingly Simple and Fast Transit Routing." link


Related Articles