2022/03/14 by Sabino Francesco Roselli, Roselli, Sabino Francesco, Per-Lage Götvall +5
Business, Management and Accounting · Engineering · #FOS: Electrical engineering #Sustainable Supply Chain Management #Systems and Control (eess.SY) #Urban and Freight Transport Logistics #Vehicle Routing Optimization Methods #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2203.06977
openalex publication_date 2022/03/14 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
The Conflict-Free Electric Vehicle Routing Problem (CF-EVRP) is an extension\nof the Vehicle Routing Problem (VRP), a combinatorial optimization problem of\ndesigning routes for vehicles to visit customers such that a cost function,\ntypically the number of vehicles or the total travelled distance, is minimized.\nThe problem finds many logistics applications, particularly for highly\nautomated logistic systems for material handling. The CF-EVRP involves\nconstraints such as time windows on the delivery to the customers, limited\noperating range of the vehicles, and limited capacity on the number of vehicles\nthat a road segment can accommodate at the same time. In this paper, the\ncompositional algorithm ComSat for solving the CF-EVRP is presented. The\nalgorithm iterates through the sub-problems until a globally feasible solution\nis found. The proposed algorithm is implemented using an optimizing SMT-solver\nand is evaluated against an implementation of a previously presented monolithic\nmodel. The soundness and completeness of the algorithm are proven, and it is\nbenchmarked on a set of generated problems and found to be able to solve\nproblems of industrial size.\n