基于耗油量的带装箱约束多类型车辆调度问题研究

We study the vehicle routing problem with packing constraints arising in logistics distribution. Different from the problem objected at minimizing the total distance in literature, our problem aims at minimizing the fuel consumption. Besides, the vehicle type in our problem is heterogeneous, which makes our problem more close to the practice. Based on whether considering the time window, two problems are classified: (1) heterogeneous fleet vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints (2) heterogeneous fleet vehicle routing problem minimizing fuel consumption under time window and three-dimensional loading constraints. For each problem, we first build the mathematical model, which includes the constraints considered in practice for packing and the relationship between the fuel consumption, the total weight of the vehicle and the vehicle speed. Then, we design heuristic algorithm for the packing problem with practical constraints. Finally, we use effective meta-heuristic to solve the vehicle routing problem. Our study can help the logistic company to save the fuel consumption and logistic cost. The saving of fuel consumption can reduce air emission, thus has significant practice value for energy saving and environmental protection. In addition, as this problem combines two NP-hard problems: packing problem and vehicle routing problem, the study of this problem has important theoretical significance.

本项目拟对在实际物流配送中经常碰到带装箱约束车辆调度问题进行研究。与文献中大都以缩短车辆行驶距离为目标不同，本项目以降低耗油量为目标，同时，加入了车辆类型的多样性，因此更加贴近实际。根据是否考虑时间窗，该问题分成了两个版本：（1）基于耗油量的带装箱约束多类型车辆调度问题（2）考虑时间窗，基于耗油量的带装箱约束多类型车辆调度问题。对每个问题，首先进行数学建模，确定车辆耗油量跟车辆载货重量、行驶速度的关系以及实际装箱过程中需要考虑的约束条件，然后，设计启发式算法有效求解带实际约束条件的装箱这个子问题，最后，设计出有效的超启发式搜索策略求解车辆调度子问题。本项目的研究能够帮助企业减少耗油量，减低物流成本，同时，耗油的减低能够减少尾气的排放，对节能和环境保护有着重要意义。此外，该问题结合了装箱和车辆调度两个NP 难问题，因此，研究该问题具有重要的理论价值。

本项对实际物流配送中经常碰到带装箱约束车辆调度问题进行了研究。与文献中大都以缩短车辆行驶距离为目标不同，本项目以降低耗油量为目标，同时，加入了车辆类型的多样性，因此更加贴近实际。根据是否考虑时间窗，该问题分成了两个版本：（1）基于耗油量的带装箱约束多类型车辆调度问题（2）考虑时间窗，基于耗油量的带装箱约束多类型车辆调度问题。对每个问题，首先进行数学建模，确定车辆耗油量跟车辆载货重量、行驶速度的关系以及实际装箱过程中需要考虑的约束条件，然后，设计启发式算法有效求解带实际约束条件的装箱这个子问题，最后，设计出有效的超启发式搜索策略求解车辆调度子问题。测试数据表明，我们设计的算法能够快速有效地求解这两个问题，并能减少车辆在配送过程中的耗油量。本项目的研究能够帮助企业合理有效地安排车辆配送路线，降低物流成本。