Electric Vehicle Location-Routing Task-Motion Planning
Yazz Warsame, Stefan Edelkamp · 2023
This work presents a solution to the electric location-routing problem with capacitated energy and item load using a location-routing task motion planning approach. Our solution consists of three stages, (i) we start by generating collision-free regions of interest using a probabilistic roadmap. (ii) we propose modifications to the capacitated hierarchical agglomerative clustering algorithm (CAC). First, we consider the vehicle's starting location, ensuring that the vehicle has enough energy to enter a cluster and visit all the customers in the cluster with a full battery charge. Secondly, an adaptive threshold approach ensures the vehicle can traverse between the clusters and visit the customers. This stage generates capacitated clusters within the vehicle's capacity and decides how many facilities to open and their locations to satisfy the customers' demands. (iii) we use an off-the-shelf PDDL solver and a second-order vehicle model in an obstacle-rich environment. We compare the performance of our approach to CAC. For our simulated experiments, we analyze various routes and costs for different attributes, such as the cluster strategies, energy capacity, number of customers and item load, where the results measure the runtime, number of customer visits and the average travel distance. When the vehicle cannot visit all the customers in a cluster due to a limited energy capacity, it seeks to maximize the number of customer visits.