计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (12): 265-270.DOI: 10.3778/j.issn.1002-8331.1803-0392

• 工程与应用 • 上一篇    

多禁止时间窗约束的路径恢复问题研究

姚书婷,胡志华,魏  晨   

  1. 上海海事大学 物流研究中心,上海 201306
  • 出版日期:2019-06-15 发布日期:2019-06-13

Distribution Recovery from Multiple Forbidding Time Windows at Customers

YAO Shuting, HU Zhihua, WEI Chen   

  1. Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China
  • Online:2019-06-15 Published:2019-06-13

摘要: 突发灾难的应急物资的配送有时受多禁止时间约束,为此,针对多禁止时间窗约束的应急物资运输路径优化问题,考虑多禁止时间窗的约束,建立了以总配送时间最小为目标、多禁止时间窗约束的应急物资运输路径优化模型。鉴于该模型为混合整数规划模型,采用GUROBI求解,并与建立的对应的多时间窗约束的路径优化模型对比。最后通过算例分析验证了该模型的高效性和算法的有效性。结果表明,多禁止时间窗约束的应急物资运输路径优化模型求解效率更高;此外评估救灾点对配送时间的影响以及分析多禁止时间窗对应急物资配送规划的影响,结果表明部分救灾点显著影响总配送时间,禁止时间窗的开始时间以及宽度影响总配送路线、时间以及到达各救灾点的时间,因此考虑时间约束特点可为应急物资运输决策提供实用价值。

关键词: 应急物流, 多禁止时间窗, 旅行商问题, 路径优化

Abstract: Emergency supplies distribution for catastrophe may be limited by the forbidding time. Therefore, it builds an optimization model based on routing problem, with the consideration of multiple forbidding time windows, to minimize the total emergency delivery costs(time). GUROBI is used to solve this mixed integer programming model, then it is compared with the routing optimization model, which considers multiple time windows. In the end of this paper, it confirms the validation and efficiency of model and algorithm with numerical analysis, the results show that the model with multiple forbidding time windows is more efficient. It additionally analyzes the impact of relief points on delivery time and the impact of multiple forbidding time windows on emergency delivery planning, the results show that some relief points have remarkable impact on the total delivery time, which is up to 2 percentage, the starting time and the width of forbidding time windows affect the whole route, time and arriving time at each relief point. Hence, considering the time constraints is significant for emergency.

Key words: emergency logistics;multiple forbidding time windows, travelling salesman problem, routing optimization