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

Two-phase variable neighborhood scatter search for the capacitated vehicle routing problem with stochastic demand

作　　者：李阳[1] 范厚明[1] 张晓楠[2] 杨翔[1] LI Yang;FAN Hou-ming;ZHANG Xiao-nan;YANG Xiang(Institute of Strategy Management and System Planning,Dalian Maritime University,Dalian Liaoning 116026,China;College of Mechanical and Electrical Engineering,Shaanxi University of Science and Technology,Xi’an Shaanxi 710021,China)

机构地区：[1]大连海事大学战略管理与系统规划研究所,辽宁大连116026 [2]陕西科技大学机电工程学院,陕西西安710021

出　　处：《控制理论与应用》2017年第12期1594-1604,共11页Control Theory & Applications

基　　金：国家自然科学基金项目(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时较为有效,点重优化策略调整效果较佳.The capacitated vehicle routing problem with stochastic demand(CVRPSD)is an extension of capacitated vehicle routing problem(CVRP)which is a well-known NP-hard problem.Due to the stochastic characteristic of customer’s demand,the solution process is evidently different from deterministic CVRP and it is rather complicated to be solved.Based on the principles of pre-optimization and re-dispatch,a two-stage variable neighborhood scatter search algorithm(VNSS)is proposed.In first stage,the stochastic chance constrained optimization model is constructed and the stochastic constrain of customer’s demand is transformed to a certain constrain.On base of the equivalent formation,the optimal solutions of pre-optimization scheme are generated by VNSS and it could be participated in the re-dispatch optimization.In second stage,the paper proposes a new re-dispatch policy to deal with the so-called failure point in pre-optimization scheme.The failure point and the customers afterwards are re-optimized to avoid unnecessary vehicle routings which may cause extra costs and more vehicles.Numerical results show that the two-stage VNSS and re-dispatch policy is rather effective.

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

分 类 号：O22[理学—运筹学与控制论]