A Compositional Algorithm for the Conflict-Free Electric Vehicle Routing Problem
The Conflict-Free Electric Vehicle Routing Problem (CF-EVRP) is an extension of the Vehicle Routing Problem (VRP), a combinatorial optimization problem of designing routes for vehicles to visit customers such that a cost function, typically the number of vehicles or the total travelled distance, is minimized. The problem finds many logistics applications, particularly for highly automated logistic systems for material handling. The CF-EVRP involves constraints such as time windows on the delivery to the customers, limited operating range of the vehicles, and limited capacity on the number of vehicles that a road segment can accommodate at the same time. In this paper, the compositional algorithm ComSat for solving the CF-EVRP is presented. The algorithm iterates through the sub-problems until a globally feasible solution is found. The proposed algorithm is implemented using an optimizing SMT-solver and is evaluated against an implementation of a previously presented monolithic model. The soundness and completeness of the algorithm are proven, and it is benchmarked on a set of generated problems and found to be able to solve problems of industrial size.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
An SMT Based Compositional Algorithm to Solve a Conflict-Free Electric Vehicle Routing Problem
The Vehicle Routing Problem (VRP) is the combinatorial optimization problem of designing routes for vehicles to visit customers in such a fashion that a cost function, typically the number of vehicles, or the total trave…
Combinatorial OptimizationSchedulingLeveraging Conflicting Constraints in Solving Vehicle Routing Problems
The Conflict-Free Electric Vehicle Routing Problem (CF-EVRP) is a combinatorial optimization problem of designing routes for vehicles to visit customers such that a cost function, typically the number of vehicles or the …
Combinatorial OptimizationConflict-free Charging and Real-time Control for an Electric Bus Network
The rapid adoption of electric buses by transit agencies around the world is leading to new challenges in the planning and operation of bus networks. In particular, the limited driving range of electric vehicles imposes …
SchedulingCooperative Control in Eco-Driving of Electric Connected and Autonomous Vehicles in an Un-Signalized Urban Intersection
This paper addresses the problem of finding the optimal Eco-Driving (ED) speed profile of an electric Connected and Automated Vehicle (CAV) in an isolated urban un-signalized intersection. The problem is formulated as a …
Autonomous VehiclesEfficient Online Scheduling and Routing for Automated Guided Vehicles In Loop-Based Graphs
Automated guided vehicles (AGVs) are widely used in various industries, and scheduling and routing them in a conflict-free manner is crucial to their efficient operation. We propose a loop-based algorithm that solves the…
Scheduling