Dynamic routing optimization with electric vehicles under stochastic battery depletion

ABSTRACT

This paper addresses a dynamic traveling salesman problem with electric vehicles under stochastic battery depletion. In the problem, traffic density and battery consumption rate are not known precisely, and their probability distributions are subject to change during the transportation operations. The problem has been formulated and solved using the Dynamic Programming (DP) approach. We develop a DP-based heuristic, which combines Restricted DP and Prim’s algorithms, to solve larger instances. The provided algorithms can determine distribution plans that reduce energy consumption and range anxiety of electric vehicle drivers. The added values of the model and the solution approach have been shown based on a case study and 270 instance-setting pairs that involve relatively larger problems. The heuristic algorithm outperformed a benchmark heuristic by providing 6.87% lower calculated required energy on average. The provided decision support tools can be used to assure energy conservation and emission reduction for short-haul freight distribution systems.

KEYWORDS:

• Traveling salesman problem
• dynamicity
• electric vehicle
• stochastic battery depletion
• dynamic programming

Acknowledgments

This work was supported by Research Fund of the Hacettepe University. Project Number: SUK-2022-19963.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. Urbanization by Hannah Ritchie and Max Roser, https://ourworldindata.org/urbanization, Online accessed: December 2021.

2. https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/, Online accessed: November 2021.

3. MP-TESTDATA-The TSPLIB Symmetric Traveling Salesman Problem Instances, http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/, Online accessed: January 2022.

4. Pollution-Routing Problem Instance Library, www.apollo.management.soton.ac.uk/prplib.htm, Online accessed: November 2021.

5. For the analyses, the given distances between cities are divided to 10 in order to generate urban scenarios.