求解VRPBTW的变邻域搜索算法

• 作 者: 刘士新 刘玲 张涛
• 机 构: 东北大学信息科学与工程学院,上海财经大学信息管理与工程学院
• 出 处: 东北大学学报：自然科学版
• 发表日期: 2008年3期
• 关键词: 车辆路径问题 时间窗口 回程载货 变邻域搜索 局域搜索算子 vehicle routing problem time window backhaul VNS（v
• 基金项目: 国家自然科学基金资助项目（70301007,70771020,70501018）,教育部新世纪优秀人才支持计划项目（NCET-06-0286）.

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