随机需求车辆路径问题及混合变邻域分散搜索算法求解
李阳1
范厚明1
张晓楠2
杨翔1
1.大连海事大学战略管理与系统规划研究所,辽宁大连,1160262.陕西科技大学机电工程学院,陕西西安,710021
摘要：随机需求车辆路径问题(capacitated vehicle routing problem with stochastic demand,CVRPSD)是对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP)的扩展,需求不确定的特点使其较CVRP更复杂,对求解方法要求更高.基于先预优化后重调度思想,提出两阶段的混合变邻域分散搜索算法(variable neighborhood scatter search,VNSS)对该问题进行求解:预优化阶段构建随机机会约束规划模型,对客户点随机需求作机会约束确定型等价处理,生成最优预优化方案;重调度阶段采用新的点重优化策略进行线路调整,降低因失败点而产生的额外成本,减少对人工和车辆的占用.算例验证表明,随机机会约束模型和两阶段变邻域分散搜索算法在求解CVRPSD时较为有效,点重优化策略调整效果较佳.
关键词：车辆路径问题随机需求点重优化策略分散搜索算法变邻域搜索算法
分类号：TP301.6(计算技术、计算机技术)
论文发表日期：2017-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：11( 1594-1604 )
英文信息