时间依赖型同时取送货VRP及超启发式算法  

Hyper-heuristic for time-dependent VRP with simultaneous delivery and pickup

作　　者：张景玲[1] 刘金龙 赵燕伟[1] 王宏伟 冷龙龙 冯勤炳 ZHANG Jingling;LIU Jinlong;ZHAO Yanwei;WANG Hongwei;LENG Longlong;FENG Qinbing(Key Laboratory of special equipment manufacturing and advanced processing technology,Ministry of Education,Zhejiang University of Technology,Hangzhou 310014,China)

机构地区：[1]浙江工业大学特种装备制造与先进加工技术教育部重点实验室,浙江杭州310014

出　　处：《计算机集成制造系统》2020年第7期1905-1917,共13页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61402409,51875524);浙江省自然科学基金资助项目(LY19F030017)。

摘　　要：为有效地协调正逆向物流,更好地体现城市物流配送速度时变的特点,降低物流配送成本,以时间依赖型同时取送货车辆路径问题为对象,建立其数学规划模型;设计了基于禁忌搜索的超启发式算法对其进行求解。在算法高层,设计了基于禁忌搜索评分制的选择策略及模拟退火的接收准则,实时监控底层启发式算子的性能并选择最优算子。通过基准实例测试及实验对比分析,表明了该算法能快速地找到满意解,所设计高层策略能保证算法跳出局部最优并快速收敛,从而证明了所提算法求解该问题的有效性。To harmonize the relationship between logistics and reverse logistics and to describe the characteristics of vehicle with variable speed more specifically in urban logistics, a model of Time Dependent Vehicle Routing Problem with Simultaneous Delivery and Pickup(TDVRPSDP) was built. Aiming at reducing the costs of logistics activity, a Hyper-Heuristic(HH) algorithm was designed to solve TDVRPSDP. The proposed algorithm utilized Tabu Search(TS) as select strategy and Simulated Annealing(SA) as acceptance criteria(AC) in high-level heuristic to improve the performance of hyper-heuristic framework by timely and rapidly monitoring the performance information of Low-Level Heuristics(LLH) and choosing the best one according to its performance before. Simulation results and comparisons showed that the proposed algorithm was effective to solve TDVRPSDP within reasonable computing time. In addition, the ability to jump out local optimum and speed up optimizing of strategies designed had been proved by the test of benchmark instance and comparison of result from predecessor.

关 键 词：车辆路径问题 同时取送货 时间依赖网络 超启发式算法 禁忌搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] U116.2[自动化与计算机技术—计算机科学与技术]