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

作     者：王超 高扬 刘超 WANG Chao;GAO Yang;LIU Chao

作者机构：北京工业大学经济与管理学院北京100124 北京现代制造业发展研究基地北京100124 波士顿大学物理系波士顿02215 

出 版 物：《系统工程理论与实践》 (Systems Engineering-Theory & Practice)

年 卷 期：2018年第38卷第11期

页      面：2892-2906页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 0701[理学-数学] 0823[工学-交通运输工程] 

基　　金：国家自然科学基金青年项目(61603011,61603010) 国家自然科学基金面上项目(61773029,71772016) 2017年博士后国际交流计划派出项目(20170016) 

主　　题：车辆路径 卡车和拖车 局部搜索 变邻域下降 

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