计重收费模式下考虑装箱约束的车辆路径优化问题研究

In this project, we study the vehicle routing problem with toll-by-weight under three-dimensional loading constraints (VRPWC3DL), which reflects some real characteristics of logistics distribution and highway transportation. The objective of this problem is to minimize the total transportation cost that is related to both freight and vehicle weight. Moreover, multiple practical loading constrains must be satisfied when designing routes for each vehicle in this problem. This project is mainly consisted of three parts of research, namely, the study of vehicle routing problem with weight-related cost, the study of three-dimensional single container loading problem with multiple practical loading constraints, and the study of vehicle routing problem with weight-related cost under three-dimensional loading constraints. In each study, we will first formally define the problem and explore the special properties of the problem. Then, we will build respective mathematical models for further analyses. Finally, exact algorithms or heuristics will be developed based on former analyses and the performance of the algorithms will be thoroughly tested. This project could help logistics enterprises save transportation cost and increase economic benefits. At the same time, it could serve as theoretical guidance for relevant departments in our government to support policy-making and policy-analysis. In addition, VRPWC3DL combines two NP-hard optimization problems (vehicle routing problem and three-dimensional bin packing problem)，therefore, it will enrich the research related to combinatorial optimization and other relevant academic fields, which shows great theoretical importance.

本项目面向公路运输中计重收费和装箱约束的现实需求，重点研究计重收费模式下考虑装箱约束的车辆路径优化问题。该问题以降低计重收费模式下的公路运输费用为目标，并要求在设计车辆行驶路径的同时考虑实际装车过程中面临的多重约束条件，它是两类经典的NP难问题（车辆路径优化问题和装箱问题）的联合决策问题。本项目将主要围绕（1）计重收费模式下的车辆路径优化问题的求解方法研究；（2）多约束三维单箱装箱问题的求解方法研究；（3）计重收费模式下考虑装箱约束的车辆路径优化问题的求解方法研究而展开。每一个研究内容采用的主要研究步骤可以概括为：定义问题、分析问题的特性和规律、建立数学模型、设计精确算法或启发式算法、检验算法性能。本项目的研究能够为企业降低物流成本、提高经济效益提供帮助，也可以为相关政府部门的政策分析与制定提供支持。同时，本项目提出的问题可以丰富组合优化等相关的学术研究领域，具有较高的理论价值。

计重收费模式下考虑装箱约束的车辆路径优化问题是车辆路径优化问题和三维装箱问题这两类经典的NP难问题的联合决策问题。本项目主要围绕（1）计重收费模式下的车辆路径优化问题的求解方法研究；（2）多约束三维单箱装箱问题的求解方法研究；（3）计重收费模式下考虑装箱约束的车辆路径优化问题的求解方法研究而展开。目前已完成对多约束三维单箱装箱问题的研究，包括针对带时间窗的变尺寸装箱问题、集装箱混合装载问题、二维铡刀式带装载问题、多集装箱装载成本最小化问题和广义集装箱装载问题设计并实现求解算法和生成标准测试数据。根据调研，对计重收费模式下的车辆路径优化问题进行细化研究，完成了考虑服务优先级的车辆路径优化问题的研究，包括设计并实现求解算法和生成标准测试数据。对计重收费模式下考虑装箱约束的车辆路径优化问题的研究尚在进行中，我们建立了该问题的数学模型，逐步设计并实现启发式算法，并且生成标准测试数据。在算法中构造车辆路径的过程中，不断对货物进行预装载，结合统计估计，预判路径的可行性，达到提前剪枝的效果，从而提高算法效率。本项目的研究能够为企业降低物流成本、提高经济效益提供帮助，也可以为相关政府部门的政策分析与制定提供支持。同时，本项目提出的问题可以丰富组合优化等相关的学术研究领域，具有较高的理论价值。项目资助发表SCI论文1篇，待发表4篇，签约出版专著1部，参加国际学术会议并做报告4次。项目资助国内外专家报告与学术交流12次，参与承办学术会议4场。培养研究生5名，其中3名已经取得硕士学位并且1名继续攻读博士学位，2名在读。项目投入经费18万元，支出15.423247万元，各项支出基本与预算相符。剩余经费2.576753万元，计划用于本项目研究后续支出。