混合启发式算法求解多配送人员车辆路径问题  

Hybrid Heuristic Algorithm for the Vehicle Routing Problem with Multiple Deliverymen

作　　者：苏欣欣 王红卫 秦虎 王恺[3] SU Xin-xin;WANG Hong-wei;QIN Hu;WANG Kai(School of Management Engineering, Qingdao University of Technology, Qingdao 266000, China;School of Management,Huazhong University of Science and Technology, Wuhan 430074, China;Economics and Management School, Wuhan University, Wuhan 430000, China)

机构地区：[1]青岛理工大学管理工程学院,山东青岛266000 [2]华中科技大学管理学院,湖北武汉430074 [3]武汉大学经济与管理学院,湖北武汉430000

出　　处：《运筹与管理》2022年第2期42-47,共6页Operations Research and Management Science

基　　金：国家自然科学基金创新研究群体项目(71821001);国家自然科学基金面上项目(71971090,71671131)。

摘　　要：为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。To solve the vehicle routing problem with time windows and multiple deliverymen,we adopt a hybrid heuristic algorithm,which is characterized by the hybridization of the integer programming recombination,the local search(LS)algorithm and the simulated annealing(SA)algorithm.In the proposed algorithm,the integer programming recombination is capable of providing better solutions for further improvement,and LS and SA make a good balance between exploration and exploitation.Computational results indicate the proposed algorithm is more effective than CPLEX and the tabu search algorithm.

关 键 词：车辆路径问题 时间窗 多配送人员 混合启发式算法 

分 类 号：U116.2[交通运输工程]