考虑充电站选址和容量限制的电动物流车辆路径问题研究

The shortage of charging station is one of the main obstacles to restrict the electrification of logistics vehicles. The location and capacity limitation of charging station can directly affect the operation cost and routing scheduling of electric freight vehicle. The purpose of this project is to systematically study the electric freight vehicle routing problem with charging station location and capacity limitation. First, by analyzing the influence mechanism of charging station location and capacity limitation on operation cost structure and vehicle scheduling program, a mixed integer programming model of vehicle freight routing problem with charging station location and capacity limitation is constructed. Second, based on the structure characteristics, build the set-partitioning model and develop a branch-and-price-and-cut exact algorithm for solving the problem by designing the label-setting algorithm of the pricing problem and the valid inequality to accelerate the lower bound convergence. By improving algorithm framework and search operator structure, the adaptive large neighborhood search heuristic algorithm for solving the problem is developed. Finally, we evaluate these two algorithms by instance experiment, and apply the developed algorithm to the vehicle scheduling management in real industry. The research results provide the decision technology support for the logistics enterprise to formulate the electric freight vehicle logistics management system.

缺少充电站是制约物流车辆电动化发展的主要障碍之一。充电站选址和容量限制会对电动物流车辆的运营成本和行驶路径造成直接影响。本项目旨在对考虑充电站选址和容量限制的电动物流车辆路径问题展开系统研究。首先，通过分析充电站选址和容量限制对运营成本结构和车辆路径规划的影响机理，构建考虑充电站选址和容量限制的电动车辆路径问题混合整数规划模型，其次，基于问题结构特征构建集合划分模型，通过设计求解定价子问题的标号设定算法和加速下界收敛的合法不等式，开发求解问题的分枝定价切割精确算法。设计改进算法框架和搜索算子结构，开发求解问题的自适应大领域搜索启发式算法。最后，通过算例实验对所开发的两种算法进行验证和评价，并将所开发的算法初步应用于物流企业的实际物流管理中。本项目的研究成果将为物流企业制定电动车辆物流管理方案提供决策技术支持。

随着近年来电动汽车产业的快速发展普及，充电设备短缺和管理混乱是制约物流车辆电动化发展的主要障碍之一。充电站选址和容量限制会对电动物流车辆的运营成本和路径规划造成直接影响。越来越多的企业开始加大对电动车辆配套充电和换电设备的开发和应用。因此，本项目就充电站和电池换电站的容量限制和影响效应方面的研究。按照前期项目申请书中规划，本项目完成了充电站选址和容量限制对电动车辆路径规划的影响机理分析，考虑充电站选址和容量限制的电动车辆路径问题模型构建，考虑充电站选址和容量限制的电动物流车辆路径优化算法设计以及算法测试和应用开发。项目期间已完成论文撰写5篇，投稿3篇，录用2篇。依托本项目，本人与华东电子有限公司开展横向合作，申请获批软件著作权1项，目前该软件已经公司港口运营系统中实施部署应用。此外本项目在调研中发现，随着物流供应链上下游的进一步整合，物流服务越来越需要考虑上游产品加工流程和产品特性对车辆路径规划问题的影响。因此，项目决定下一阶段结合各类型产品生产调度和物流特性开发一类电动物流车辆规划调度子问题，为物流企业开展物流管理优化提供技术支持。