Sustainability Blog – Green Vehicle Routing

By Christian Puchert

Turning the Vehicle Routing Problem (VRP) into a Green VRP

In the European Union, the transport sector is responsible for 25% of all GHG emissions; in turn, 71% of these emissions are due to transport on the road.[1] In order to reach net-zero emissions by 2050, reducing the emissions in this sector therefore plays a crucial role.

The Emissions Trading System (ETS), which forces companies to buy allowances for their GHG emissions, is being extended to road transport by 2027 with the ETS2: There will be a price per ton of CO₂ emitted which will be dynamic depending on the market conditions. The EU is decreasing the available allowances each year, which will drive up the price of polluting.

With sustainability becoming increasingly more important, planning operations for logistics companies is not just about efficiency in terms of time or travel distance anymore, it must be “green” as well. While in the past, they often addressed their planning puzzles as a Vehicle Routing Problem (VRP), this is just not enough anymore: one has to consider the green aspect as well, turning the VRP into a Green VRP (GVRP).

But what is VRP? It is a field in operations research that is applied whenever in the industry, vehicles (e.g., trucks) deliver goods to customers. In a simple form, it can be stated as follows: given a set of locations, a depot and a set of vehicles, assign each location to a vehicle such that each vehicle starts at the depot, visits several locations and returns to the depot, where each location is visited exactly once.

Introduced by Dantzig and Ramser in 1959[2], it has been a research topic for decades and seen numerous variants and extensions, where additional side constraints need to be satisfied, e.g., capacity restrictions on the vehicles or time window restrictions. Previously, the focus has always been on minimizing the total distance travelled or the total duration, to achieve cost savings and a better utilization of the vehicles. Of course, one could argue that this indirectly also leads to a reduction in the greenhouse gas (GHG) emissions, but that was not the focus of the VRP.

Incorporating Green Requirements

The way in which companies plan their operations is changing, and thus, the Green VRP includes modifications and extensions to the VRP to deal with that new situation. Especially since 2010, research activity around it has increased a lot.[3] Among the most notable changes, these are the following:

Changing the objective function.

• A number of scientific studies incorporate carbon emission trades into the objective function of the (G)VRP, e.g., Kwon et al.[4] Apart from that, also fuel consumption or the GHG emissions themselves were considered. This changing objective functions entails further research questions, such as how these are measured within the model. Some of the scientific studies already consider the effect of traffic congestion, road conditions or topography. Under the term Time-Dependent VRP, the difficulties that arise from the variability in travel speed are investigated.

So far, these studies focusing on changing the objective function have simplified assumptions, e.g., regarding the interplay between congestion and travel speed. Therefore, research on solution methods for more realistic models is still needed. Also, extending the objective function often results in a multi-objective function. In order to enable algorithms to deal with that, in many research papers, the objective is converted into a single objective by using a weighted sum. An open question is still how to obtain a “reasonable” weighting as well as other ways to handle that.

• Incorporating the recharging of electric vehicles.
  Due to the emissions caused by combustors, more emission neutral vehicles are entering the fleets, such as vehicles that drive with alternative fuels or electric vehicles. The latter, though, have a smaller driving range and thus need to be recharged regularly, which requires additional time. In their work from 2012, Erdoğan and Miller-Hooks[5] discuss a variant of the VRP, which, in addition to customer locations, adds recharging stations to the model. Unlike customer locations in a classical VRP, which are visited exactly once by a vehicle, they can be visited arbitrarily often. An additional driving range constraint ensures that a vehicle will visit such a station before it runs out of energy.

Although Erdoğan and Miller-Hooks, actually the first one to use the term “Green VRP”, incorporate the recharging of electric vehicles, they neglect other aspects that are dealt with in subsequent works: a vehicle does not need to be loaded fully until it continues its journey; instead of loading, batteries may be swapped; the availability of chargers may be restricted, which incurs waiting times at recharging stations; charging times may be non-linear; charging may also happen at customer locations, maybe even overnight.

Previous research only considers a subset of these aspects while disregarding or simplifying others or ignoring further aspects such as the battery life or the influence of vehicle load on energy consumption. Developing and solving models that combine them is a direction for future research.

• Placement of depots and charging stations.
  An extension of the VRP, the Location Routing Problem (LRP), adds the strategic decision where to locate additional facilities such as depots from which to serve the customers, which is done simultaneously with the routing of vehicles. There has been research on that problem in the past, but recently, green variants of it have been investigated as well: some publications discuss the placement of battery-swap stations for electric vehicles, e.g. Hof et al.[6]; others deal with the placement of charging stations while taking driving ranges, charging times and different recharging options into account, e.g. Schiffer and Walther[7].

Those modifications bring additional complexity to the VRP and thus impose algorithmic challenges. The VRP as well as the GVRP may be solved using various methods, including exact methods and metaheuristic methods. Solving the VRP exactly is already a challenge, and even more so for the GVRP. A big research focus therefore lies on metaheuristic methods, which need to be adjusted as well. Heuristics that performed well for the classical VRP will most likely perform sub-optimally for the GVRP, if they find feasible solutions at all. Therefore, modifications of existing heuristics as well as new heuristics are devised.

Conclusion

The ETS2 and the need to reduce GHG emissions force logistics companies to rethink the way they plan their operations, and incorporating the “green” aspect into the classical vehicle routing problem imposes additional algorithmic complexity. Existing models and algorithms, often metaheuristic methods, are likely to fail or yield sub-optimal solutions for the Green VRP. Even though modifications and extensions have already been developed, there is still a significant room for improvement for which further research is needed.

Logistics companies may need new optimizers to reduce their GHG emissions or add electric vehicles to their fleets. The development of fast and efficient algorithms is a challenge, given the increased complexity of the planning problem. Hence, research is needed to tackle this; the existing results already give directions. Ab Ovo is looking forward to incorporating green requirements into the algorithms in order to realize the sustainability targets of the market.

[1] https://www.consilium.europa.eu/en/policies/clean-and-sustainable-mobility/

[2] Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.

[3] Sabet, S., & Farooq, B. (2022). Green vehicle routing problem: State of the art and future directions. IEEE Access, 10, 101622-101642.

[4] Kwon, Y. J., Choi, Y. J., & Lee, D. H. (2013). Heterogeneous fixed fleet vehicle routing considering carbon emission. Transportation Research Part D: Transport and Environment, 23, 81-89.

[5] Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation research part E: logistics and transportation review, 48(1), 100-114.

[6] Hof, J., Schneider, M., & Goeke, D. (2017). Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops. Transportation research part B: methodological, 97, 102-112.

[7] Schiffer, M., & Walther, G. (2017). The electric location routing problem with time windows and partial recharging. European journal of operational research, 260(3), 995-1013.