研究了一种带时间窗的多车型需求可拆分揽收配送问题(Multi-Vehicle Split Pickup and Delivery Problem with Time Windows,MVSPDPTW)。针对这个问题以执行任务车辆行驶路径总长度最小为目标函数,建立了一个混合整数线性规划模型。提...研究了一种带时间窗的多车型需求可拆分揽收配送问题(Multi-Vehicle Split Pickup and Delivery Problem with Time Windows,MVSPDPTW)。针对这个问题以执行任务车辆行驶路径总长度最小为目标函数,建立了一个混合整数线性规划模型。提出了一种高效禁忌模拟退火(Tabu Simulated Annealing,TSA)算法,在算法中设计了两种新的邻域搜索算子,分别用于修复违反容量约束以及换车操作,多种算子配合的方式扩大了邻域搜索范围,避免算法陷入局部最优。此外在算法中加入了禁忌机制以及违反约束惩罚机制,实现了搜索空间的有效裁剪,提高了算法的全局寻优能力。最后基于Solomon数据集和构造的仿真数据集等对算法进行了大量仿真实验,实验验证了该算法的有效性。展开更多
The vehicle routing problem(VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the res...The vehicle routing problem(VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups(VRPSPDP) is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.展开更多
文摘研究了一种带时间窗的多车型需求可拆分揽收配送问题(Multi-Vehicle Split Pickup and Delivery Problem with Time Windows,MVSPDPTW)。针对这个问题以执行任务车辆行驶路径总长度最小为目标函数,建立了一个混合整数线性规划模型。提出了一种高效禁忌模拟退火(Tabu Simulated Annealing,TSA)算法,在算法中设计了两种新的邻域搜索算子,分别用于修复违反容量约束以及换车操作,多种算子配合的方式扩大了邻域搜索范围,避免算法陷入局部最优。此外在算法中加入了禁忌机制以及违反约束惩罚机制,实现了搜索空间的有效裁剪,提高了算法的全局寻优能力。最后基于Solomon数据集和构造的仿真数据集等对算法进行了大量仿真实验,实验验证了该算法的有效性。
基金Project supported by the National Natural Science Foundation of China(No.51138003)the National Social Science Foundation of Chongqing of China(No.2013YBJJ035)
文摘The vehicle routing problem(VRP) is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups(VRPSPDP) is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.
