基于迭代变邻域下降算法求解TTRP问题

为了求解卡车带挂车的车辆路径问题(truck and trailer routing problem, TTRP),提出迭代变邻域下降算法(iterated variable neighborhood descent, IVND).该算法首先使用T-cluster算法求得一个初始可行解.然后,设计了基于多邻域算子的变邻域下降搜索算法.在搜索过程中,借鉴"粒邻域"的思想定义了"受限邻域",同时设计了基于switch-vehicle-type算子的扰动策略.最后,选取国际上通用的Chao测试数据集(21个50～199个顾客规模的标准测试算例)对算法性能进行测试.通过与文献中其它4种算法比较,实验结果表明,提出的IVND算法可以在最短的计算时间内收敛到满意解,并且IVND算法结构简单、计算效率高、易实现,可以被灵活地扩展解决其它车辆路径问题和组合优化问题.

Solving TTRP problem based on an iterated variable neighborhood descent algorithm

To solve the truck and trailer routing problem (TTRP), an iterated variable neighborhood descent (IVND) algorithm was proposed. First, the T-cluster heuristic was implemented for generating an initial solution. Next, a VND based on multi-operator optimization was developed. In VND, the restricted neighborhood was introduced based on the idea of granular neighborhoods, and a perturbation strategy had been designed by switch-vehicle-type operator to help optimization escape from local minima. Computational results are reported for 21 test problems with 50~199 customers from Chao's benchmark and the results indicate that the proposed IVND algorithm could converge to the satisfactory solutions within the shortest computational time. In addition, the IVND is flexible, efficient and easy to implement, and could be extended to handle other variants of vehicle routing problem and other combinatorial optimization problem.