摘要
以电子商务环境下物流配送为背景,建立了带有时间窗和回程载货约束的车辆路径问题优化模型,设计了改进的变邻域搜索求解算法.该算法采用改进的Braysy顺序插入法生成问题初始解,再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进.通过对多个算例的求解实验,并与采用一般流程的变邻域搜索算法进行比较,结果表明所提出的变邻域搜索算法的求解效果明显优于采用一般流程的变邻域搜索算法,是求解该类问题的有效算法.
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.
出处
《东北大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2008年第3期316-319,共4页
Journal of Northeastern University(Natural Science)
基金
国家自然科学基金(70301007；70771020；70501018)
教育部新世纪优秀人才支持计划项目(NCET-06-0286)．
关键词
车辆路径问题
时间窗口
回程载货
变邻域搜索
局域搜索算子
vehicle routing problem
time window
backhaul
VNS（variable neighborhood search）
local search operator
