引用本文:李阳,范厚明,张晓楠,杨翔.随机需求车辆路径问题及混合变邻域分散搜索算法求解[J].控制理论与应用,2017,34(12):1594~1604.[点击复制]
LI Yang,FAN Hou-ming,ZHANG Xiao-nan,YANG Xiang.Two-phase variable neighborhood scatter search for the capacitated vehicle routing problem with stochastic demand[J].Control Theory and Technology,2017,34(12):1594~1604.[点击复制]
随机需求车辆路径问题及混合变邻域分散搜索算法求解
Two-phase variable neighborhood scatter search for the capacitated vehicle routing problem with stochastic demand
摘要点击 2823  全文点击 1584  投稿时间：2016-11-23  修订日期：2017-09-11
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2017.60888
  2017,34(12):1594-1604
中文关键词  车辆路径问题  随机需求  点重优化策略  分散搜索算法  变邻域搜索算法
英文关键词  vehicle routing problem  stochastic demand  re-dispatch policy  scatter search algorithm  variable neighborhood search algorithm
基金项目  国家自然科学基金项目(61473053, 70801007), 辽宁省社会科学规划基金重点项目(L16AGL004), 辽宁省教育厅科学技术研究一般项目(L2014 046), 大连市科学技术计划项目(2015D12ZC181)
作者单位E-mail
李阳 大连海事大学 战略管理与系统规划研究所 liyang02030019@126.com 
范厚明* 大连海事大学 战略管理与系统规划研究所 fhm468@163.com 
张晓楠 陕西科技大学 机电工程学院 西安  
杨翔 大连海事大学 战略管理与系统规划研究所  
中文摘要
      随机需求车辆路径问题(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.