Dynamic Vehicle Routing Under Uncertain Energy Consumption and Energy Gain Opportunities

Abstract

The amount of energy that needs to be spent by a vehicle to travel between different locations, and the amount of energy that can be regained at certain locations, may not always be known in advance with certainty. In this case, the path that needs to be followed by the vehicle in order to visit some points of interest without exhausting its energy reserves, has to be determined in a dynamic way, via an online algorithm. To this end, we propose a heuristic which takes dynamic routing decisions based on the actually remaining energy of the vehicle and the estimated energy costs/gains of different path options. We evaluate the algorithm via simulations, showing that it always achieves better results than the statically optimal path-planning algorithm and close to optimal results as long as the energy storage capacity of the vehicle is not marginally sufficient to travel between locations where the vehicle can gain some energy. In addition, we investigate different variants of the algorithm that trade-off the achieved coverage for less runtime complexity. © 2021, Springer Nature Switzerland AG.