Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (11): 241-248.DOI: 10.3778/j.issn.1002-8331.1701-0040

Previous Articles     Next Articles

Study on vehicle routing problem with stochastic demands and time windows combining with new remediation strategies

DENG Ye, ZHU Wanhong, TANG Jian   

  1. College of Field Engineering, PLA University of Science and Technology, Nanjing 210001, China
  • Online:2018-06-01 Published:2018-06-14

随机需求有时间窗的路径优化及补救策略研究

邓  烨,朱万红,唐  建   

  1. 解放军理工大学 野战工程学院,南京 210001

Abstract: Based on the characteristics of uncertainty and timeliness of customer demands in urban logistics, this paper considers a problem of vehicle routing with stochastic demands and time windows, and as well as three remediation strategies with different information scheduling levels on condition of the delivery failure. A chance constrained and mixed integer programming mathematical model is constructed and transformed into an equivalent deterministic one for solving. An improved hybrid evolutionary algorithm with multiple operators is proposed to solve the model, and the superiority of the algorithm is verified by an example. Besides, the sensitivity of the model parameters and the risk cost under the three remediation strategies are analyzed. The results show that the real time feedback and dispatching strategy can decrease the risk costs of time constraint as  much as possible and the economic advantage of reducing the distribution distance is obvious.

Key words: urban logistics, Vehicle Routing Problem with Stochastic Demands and Time Windows(VRPSDTW) , remediation strategies, hybrid evolutionary algorithm

摘要: 针对城市物流配送中客户需求量不确定且时效性要求较高的特点,考虑客户需求量为随机变量且有时间窗的车辆路径优化问题,同时基于不同的信息化调度水平,考虑了配送失败时的三种补救策略。构建了机会约束混合整数规划数学模型并转化为等价的确定性模型进行求解。提出了含有多种算子的改进混合进化算法来求解该模型,并基于算例,验证了算法的优越性。同时,对模型的参数敏感性和三种补救策略下的风险成本进行了分析。结果表明,采用提前预测,实时反馈,即时派出新车的补救策略可以最大程度保证满足客户时间约束,同时还具有降低配送路程的经济优势。

关键词: 城市物流配送, 随机需求有时间窗车辆路径问题, 补救策略, 混合进化算法