随机需求车辆路径问题及混合变邻域分散搜索算法求解
Two-phase variable neighborhood scatter search for the capacitated vehicle routing problem with stochastic demand

随机需求车辆路径问题(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.