具有容量限制的无人驾驶清扫车路径优化模型及求解算法

Optimization Model and Solving Algorithm for Autonomous Sweeper Path Planning with Capacity Constraints

摘要: 合理规划车辆行驶路线，减少不必要的行驶时间是实现无人清扫车推广的关键技术。本文为有容量限制和中间设施点选择的无人清扫车路线问题建立了一个可以直接求出行驶路线的优化模型，并设计了对应的二级模拟退火算法进行求解。首先，以平均分配为原则，根据容量限制确定垃圾站，生成两辆无人清扫车可行的初始路线；其次，对两辆无人清扫车的行驶路线进行组合并利用模拟退火算法加以优化；最后，逐一优化两辆清扫车的行驶路线并分别生成其最终行驶路线。通过算例分析结果显示，本文设计的二级模拟退火算法可将无人清扫车的总行驶时间减少高达44%，减少了清扫车的工作成本，实现最终线路的工作负荷的均衡，证明了该模型和算法的可靠与高效性。

Abstract: Efficient route planning for vehicles, aimed at minimizing unnecessary travel time, is a critical technology for the widespread adoption of unmanned cleaning vehicles. This paper establishes an optimization model for the unmanned cleaning vehicle routing problem with capacity constraints and the selection of intermediate facility points. It also designs a corresponding two-stage simulated annealing algorithm for solution. First, following the principle of equitable distribution, garbage stations are determined based on capacity constraints to generate initial feasible routes for two unmanned cleaning vehicles. Second, the routes of the two vehicles are combined and optimized using a simulated annealing algorithm. Finally, each of the two cleaning vehicle routes is optimized individually to generate their final travel routes. Results from case studies demonstrate that the two-stage simulated annealing algorithm designed in this paper can reduce the total travel time of unmanned cleaning vehicles by up to 44%. This reduction leads to cost savings for the cleaning vehicles and balances the workload for the final routes, confirming the reliability and efficiency of the proposed model and algorithm.