多禁止时间窗约束的路径恢复问题研究
|
摘要
突发灾难的应急物资的配送有时受多禁止时间约束,为此,针对多禁止时间窗约束的应急物资运输路径优化问题,考虑多禁止时间窗的约束,建立了以总配送时间最小为目标、多禁止时间窗约束的应急物资运输路径优化模型。鉴于该模型为混合整数规划模型,采用GUROBI求解,并与建立的对应的多时间窗约束的路径优化模型对比。最后通过算例分析验证了该模型的高效性和算法的有效性。结果表明,多禁止时间窗约束的应急物资运输路径优化模型求解效率更高;此外评估救灾点对配送时间的影响以及分析多禁止时间窗对应急物资配送规划的影响,结果表明部分救灾点显著影响总配送时间,禁止时间窗的开始时间以及宽度影响总配送路线、时间以及到达各救灾点的时间,因此考虑时间约束特点可为应急物资运输决策提供实用价值。
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.
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.
引文
[1]饶卫振,金淳,黄英艺.求解TSP问题的最近邻域与插入混合算法[J].系统工程理论与实践,2011,31(8):1419-1428.
[2]Yi W,?zdamarb L.A dynamic logistics coordintion model for evacuation and support indisaster response activities[J].European Journal of Operational Research,2007,179(3):1177-1193.
[3]Oezdamar L,Ekinci E,Kuecuekyazici B.Emergency logistics planning in natural disasters[J].Annals of Operations Research,2004,129(1/2/3/4):217-245.
[4]孙华丽,王循庆,薛耀锋.随机需求应急物流多阶段定位-路径鲁棒优化研究[J].运筹与管理,2013,22(6):45-51.
[5]王绍仁,马祖军.震害紧急响应阶段应急物流系统中的LRP[J].系统工程理论与实践,2011,31(8):1497-1507.
[6]蔡鉴明,李夏苗,杨光华.基于时变性和可靠性的地震灾害应急物流运输路径选择[J].铁道科学与工程学报,2011,8(5):101-106.
[7]马华伟,左春荣,杨善林.多时间窗车辆运输问题的建模与求解[J].系统工程学报,2009,24(5):607-613.
[8]Ohlmann J W,Thomas B W.A compressed annealing heuristic for the traveling salesman problem with time windows[J].Informs Journal on Computing,2007,19(1):80-90.
[9]Christofides N,Mingozzi A,Toth P.State space relaxation procedures for the computation of bounds to routing problems[J].Networks,1981,11(2):145-164.
[10]Dumas Y,Desrosiers J,Gelinas E,et al.An optimal algorithm for the traveling salesman problem with time windows[J].Operations Research,1995,43(2):367-371.
[11]Silva R F D,Urrutia S.A general VNS heuristic for the traveling salesman problem with time window[J].Discrete Optimization,2010,7(4):203-211.
[12]Baker E K.Technical note-an exact algorithm for the time-constrained traveling salesman problem[J].Operations Research,1983,31(5):938-945.
[13]Kara I,Derya T.Formulations for minimizing tour duration of the traveling salesman problem with time windows[J].Procedia Economics&Finance,2015,26(8):1026-1034.
[14]何正文,贾涛,徐渝.基于禁止时间窗的应急物资运输车辆路径问题[J].运筹与管理,2009,18(2):1-6.
[15]吴瑶,马祖军.时变路网下带时间窗的易腐食品生产-配送问题[J].系统工程理论与实践,2017,37(1):172-181.
[2]Yi W,?zdamarb L.A dynamic logistics coordintion model for evacuation and support indisaster response activities[J].European Journal of Operational Research,2007,179(3):1177-1193.
[3]Oezdamar L,Ekinci E,Kuecuekyazici B.Emergency logistics planning in natural disasters[J].Annals of Operations Research,2004,129(1/2/3/4):217-245.
[4]孙华丽,王循庆,薛耀锋.随机需求应急物流多阶段定位-路径鲁棒优化研究[J].运筹与管理,2013,22(6):45-51.
[5]王绍仁,马祖军.震害紧急响应阶段应急物流系统中的LRP[J].系统工程理论与实践,2011,31(8):1497-1507.
[6]蔡鉴明,李夏苗,杨光华.基于时变性和可靠性的地震灾害应急物流运输路径选择[J].铁道科学与工程学报,2011,8(5):101-106.
[7]马华伟,左春荣,杨善林.多时间窗车辆运输问题的建模与求解[J].系统工程学报,2009,24(5):607-613.
[8]Ohlmann J W,Thomas B W.A compressed annealing heuristic for the traveling salesman problem with time windows[J].Informs Journal on Computing,2007,19(1):80-90.
[9]Christofides N,Mingozzi A,Toth P.State space relaxation procedures for the computation of bounds to routing problems[J].Networks,1981,11(2):145-164.
[10]Dumas Y,Desrosiers J,Gelinas E,et al.An optimal algorithm for the traveling salesman problem with time windows[J].Operations Research,1995,43(2):367-371.
[11]Silva R F D,Urrutia S.A general VNS heuristic for the traveling salesman problem with time window[J].Discrete Optimization,2010,7(4):203-211.
[12]Baker E K.Technical note-an exact algorithm for the time-constrained traveling salesman problem[J].Operations Research,1983,31(5):938-945.
[13]Kara I,Derya T.Formulations for minimizing tour duration of the traveling salesman problem with time windows[J].Procedia Economics&Finance,2015,26(8):1026-1034.
[14]何正文,贾涛,徐渝.基于禁止时间窗的应急物资运输车辆路径问题[J].运筹与管理,2009,18(2):1-6.
[15]吴瑶,马祖军.时变路网下带时间窗的易腐食品生产-配送问题[J].系统工程理论与实践,2017,37(1):172-181.