多约束条件下城市道路环卫车优化配置与路径规划

为有效解决当前城市环卫车调度决策过度依赖人工主观经验造成的车辆配置不合理和作业效率低下问题，本文提出一种多约束条件下的城市道路环卫车优化配置与路径规划方法。通过综合考虑环卫车在现实作业中的作业时限、服务次数、行驶速度和车辆退出节点等多种约束条件，将物理道路网络拓展为时空网络，刻画车辆在路网上的时空运行轨迹，进而将环卫车优化配置与路径规划问题从数学上描述为带多类约束条件的弧路径问题(Arc Routing Problem, ARP)。 在此基础上，构建以车辆配置与出行总成本最小化为目标函数的环卫车优化配置与路径规划模型，并通过设计分支定价算法精确求解模型。将所提方法应用于苏州工业园区19个区域路网的环卫车辆配置与调度管理，从经济成本、作业效率和环保效益这3方面评估所提方法的可行性和有效性。结果表明：本文所提方法能够显著节约环卫运营成本，提升环卫车辆作业效率；同时，可有效降低环卫车辆碳排放量，形成良好的经济和社会效益，为智慧环卫提供了行之有效的新方案。

Optimal Allocation and Routing of Sanitation Vehicles on Urban Roads Under Multiple Constraints

To avoid unreasonable vehicle allocation caused by excessive manual experience in the urban sanitation vehicle dispatching problem, this paper proposes an approach for optimal allocation and routing of sanitation vehicles on urban roads under multiple constraints. First, multiple constraints in sanitation vehicle routing are comprehensively considered, including operation time limit, service time limit on links, driving speed limit, and vehicle exiting of the road network. The travel trajectory of each vehicle is described from time and space dimensions by expanding the physical road network into a time- space network. The optimal allocation and routing of sanitation vehicles are then described as an Arc Routing Problem (ARP) with multiple constraints. A mathematical model for minimizing the total vehicle ownership cost and travel time cost is developed. A branch-and-price algorithm is designed to solve the model accurately. The proposed approach was evaluated using 19 realistic instance networks in Industrial Park, Suzhou, China. The feasibility and effectiveness of the proposed approach were validated from three aspects, including economic cost, operational efficiency, and environmental benefit. The experimental results show that the proposed approach can significantly save the cost of sanitation operation and management while improving the travel efficiency of sanitation vehicles. Meanwhile, it is also capable of reducing carbon emissions effectively, forming good economic and social benefits and therefore providing a potential solution for smart sanitation.