基于量子超启发进化算法的低碳取送货车辆调度研究

Vehicle routing problem with simultaneous delivery and pickup (VRPSDP) is a hot issue in the current field of logistics. With the strengthening of environmental awareness, the study of VRPSDP problem with the goal of minimizing the carbon emission has important scientific significance. For the basic problem it is assumed that the amount of carbon emission depends on the distances to be traveled and the degree to which the used vehicles are loaded. In our models, in addition to carbon emissions associated with these factors, but also associated with vehicle type, road network, traffic flow, and vehicle travel speed. And three low-carbon VRPSDP models which considered large-scale, multi-constraint, multi-vehicle, time dependent travel, and dynamic random demand are developed. Then, design a quantum evolution-based hyper-heuristic for these three problems. Analyze the performance of the proposed models and methods through theoretical and experiments. At last, develop a city VRPSDP experiment platform for enterprise data validation. This research can obtain a series of theory and application results on the complex low-carbon VRPSDP modeling, quantum evolution-based hyper-heuristic framework design, hyper-heuristic high-level heuristic strategy, low-level heuristic rules extraction, coding, the convergence of the algorithm and computational complexity etc. Thus providing an effective theoretic and technical support for the development of low-carbon logistics.

取送货混排车辆路径问题（VRPSDP）是目前物流领域的一个热点问题，随着环保意识的加强，研究以低碳为目标的VRPSDP问题建模与优化理论具有重要的科学意义和实用价值。本项目在深入分析碳排放与车辆行驶距离、车型、载货量、道路网络、交通流量和行驶速度等因素相互关系的基础上，面向大规模、多约束、多车型、动态网络、动态随机问题，建立其典型低碳VRPSDP问题模型；构造量子超启发进化算法，借助其良好的泛化能力实现对上述不同模型的求解；通过理论和实验对所提出的模型与方法进行性能分析；并开发城市集送货车辆调度实验平台进行企业数据实例验证；以期在复杂VRPSDP低碳车辆调度问题的建模、量子超启发算法框架设计、高层启发式策略的设计、低层优化规则提取、调度方案的编码、算法的通用性、健壮性与计算复杂性等方面取得有实用价值的理论与应用成果，从而为低碳物流的发展提供有效的理论方法和技术支持。

低碳物流已成为现代物流发展的重要趋势，通过合理的设计车辆配送路线，在节约企业成本的同时降低二氧化碳的排放对于增加企业竞争力和抑制全球变暖有着重要的现实意义；同时对该问题的研究还能丰富和充实物流科学、运筹学及组合优化等研究领域，具有较强的理论意义。本项目针对取送货混排低碳车辆调度中几类典型问题，在分析其理论与实践背景的基础上，建立了多车型、面向多配送中心、基于动态网络的取送货混排低碳VRP模型，提出了基于量子进化算法及其超启发进化算法的求解方法，本项目的主要研究工作和成果如下：(1)根据车型种类，客户的取货和送货需求，建立了以碳排放量最小为目标的多车型取送货混排低碳车辆路径问题的模型。模型中的碳排放量的计算考虑了车型、距离和车辆载重。(2)结合客户的取送货以及时间窗要求，根据旅行速度依赖函数，给出了速度可变情况下的碳排放计算规律，建立了以总旅行时间最小和总的碳排放量最低为目标的动态网络取送货混排多目标优化模型。(3)针对多配送中心问题，提出了将多个配送中心抽象成一个配送中心体系的策略，建立了多配送中心取送货混排问题的多目标优化模型，模型以碳排放量最小和总路径最短为目标进行优化。(4)设计了求解上述模型的量子超启发进化算法，给出了量子超启发进化算法框架，设计了基于量子旋转门更新选择概率的高层启发式策略及与取送货混排低碳车辆调度问题相关的低层启发式算子。(5)在上述理论工作研究的基础上，搭建了取送货混排低碳车辆调度仿真平台，该平台集成了上述取送货混排低碳调度模型以及所提的超启发量子进化算法，为实现智能化物流配送的工程应用提供理论、方法和技术支持。