论文标题
无冲突电动汽车路由问题的组成算法
A Compositional Algorithm for the Conflict-Free Electric Vehicle Routing Problem
论文作者
论文摘要
无冲突的电动汽车路由问题（CF-EVRP）是车辆路由问题（VRP）的扩展，这是一个组合式优化的问题，是为访问客户访问客户的设计路线的组合优化问题，例如车辆数量或总旅行距离的数量，是最小的。该问题发现了许多物流应用程序，特别是用于高度自动化的物质处理系统。 CF-EVRP涉及限制，例如向客户交付时的时间窗口，车辆运营范围有限，以及道路部门可以同时容纳的车辆数量有限。在本文中，提出了用于解决CF-EVRP的组成算法COMSAT。算法通过子问题迭代，直到找到全球可行的解决方案。所提出的算法是使用优化SMT溶剂实现的，并根据以前呈现的单片模型的实现进行评估。该算法的健全性和完整性已被证明，并在一组生成的问题上进行了基准测试，并能够解决工业规模的问题。
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.
