随机需求车辆路径问题及混合变邻域分散搜索算法求解

作     者：李阳 范厚明 张晓楠 杨翔 LI Yang;FAN Hou-ming;ZHANG Xiao-nan;YANG Xiang

作者机构：大连海事大学战略管理与系统规划研究所辽宁大连116026 陕西科技大学机电工程学院陕西西安710021 

出 版 物：《控制理论与应用》 (Control Theory & Applications)

年 卷 期：2017年第34卷第12期

页      面：1594-1604页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金项目(61473053 70801007) 辽宁省社会科学规划基金重点项目(L16AGL004) 辽宁省教育厅科学技术研究一般项目(L2014046) 大连市科学技术计划项目(2015D12ZC181)资助~~ 

主　　题：车辆路径问题 随机需求 点重优化策略 分散搜索算法 变邻域搜索算法 

摘      要：随机需求车辆路径问题(capacitated vehicle routing problem with stochastic demand,CVRPSD)是对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP)的扩展,需求不确定的特点使其较CVRP更复杂,对求解方法要求更高.基于先预优化后重调度思想,提出两阶段的混合变邻域分散搜索算法(variable neighborhood scatter search,VNSS)对该问题进行求解:预优化阶段构建随机机会约束规划模型,对客户点随机需求作机会约束确定型等价处理,生成最优预优化方案;重调度阶段采用新的点重优化策略进行线路调整,降低因失败点而产生的额外成本,减少对人工和车辆的占用.算例验证表明,随机机会约束模型和两阶段变邻域分散搜索算法在求解CVRPSD时较为有效,点重优化策略调整效果较佳.