东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2008, Vol. 29 ›› Issue (3): 316-319.DOI: -

• 论著 • 上一篇    下一篇

求解VRPBTW的变邻域搜索算法

刘士新;刘玲;张涛;   

  1. 东北大学信息科学与工程学院;东北大学信息科学与工程学院;上海财经大学信息管理与工程学院 辽宁 沈阳 110004;辽宁 沈阳 110004;上海 200433
  • 收稿日期:2013-06-22 修回日期:2013-06-22 出版日期:2008-03-15 发布日期:2013-06-22
  • 通讯作者: Liu, S.-X.
  • 作者简介:-
  • 基金资助:
    国家自然科学基金(70301007；70771020；70501018);;

Variable neighborhood search for solving vehicle routing problems with backhauls and time windows

Liu, Shi-Xin (1); Liu, Ling (1); Zhang, Tao (2)   

  1. (1) School of Information Science and Engineering, Northeastern University, Shenyang 110004, China; (2) School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
  • Received:2013-06-22 Revised:2013-06-22 Online:2008-03-15 Published:2013-06-22
  • Contact: Liu, S.-X.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

692

摘要： 以电子商务环境下物流配送为背景,建立了带有时间窗和回程载货约束的车辆路径问题优化模型,设计了改进的变邻域搜索求解算法.该算法采用改进的Braysy顺序插入法生成问题初始解,再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进.通过对多个算例的求解实验,并与采用一般流程的变邻域搜索算法进行比较,结果表明所提出的变邻域搜索算法的求解效果明显优于采用一般流程的变邻域搜索算法,是求解该类问题的有效算法.

关键词: 车辆路径问题, 时间窗口, 回程载货, 变邻域搜索, 局域搜索算子

Abstract: Based on the background of goods distribution in e-business environment, a model for solving the problems VRPBTW, i.e., the vehicle routing problems with backhauls and time windows, is developed, and it is analyzed to improve the VNS (variable neighborhood search) algorithm so as to solve the problems. Applying the modified sequential cheapest insertion heuristic proposed originally by Braysy to generating an initial solution for improvement, the algorithm introduces four different local search operators in accordance to VNS mechanism. The results of computational tests including 15 examples were compared with that by conventional VNS and showed that the modified VNS algorithm is effective for solving the problems and greatly outperforms the conventional one.

中图分类号: