引用本文: | 李阳,范厚明,张晓楠,杨翔.随机需求车辆路径问题及混合变邻域分散搜索算法求解[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 |
摘要点击 3251 全文点击 1734 投稿时间: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) |
|
中文摘要 |
随机需求车辆路径问题(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. |
|
|
|
|
|