随机时变车辆路径问题的多目标鲁棒优化方法
|
摘要
车辆路径问题(vehicle routing problem,VRP)是物流配送的核心问题之一,为了提高物流配送的时效性,在传统VRP模型的基础上,同时考虑了路网交通状态的时变性和随机性,基于最小最大准则,提出了一种带硬时间窗的随机时变车辆路径问题(stochastic time-dependent vehicle routing problem,STDVRP)的多目标鲁棒优化模型.设计了一种非支配排序蚁群算法(non-dominated sorting ant colony optimisation,NSACO),求解STDVRP多目标优化模型;通过测试算例,对比分析了NSACO算法与改进型非支配排序遗传算法(non-dominated sorting genetic algorithm II,NSGA-II).研究结果表明:对于车辆数最小的Pareto边界解,NSACO算法的平均车辆数比NSGA-II算法小3.33%;对于最坏行程时间最小的Pareto边界解,NSACO算法的平均最坏行程时间比NSGAII算法小17.49%.
The vehicle routing problem(VRP) is a core issue of distribution logistics. In order to improve the timeliness of deliveries, a multi-objective robust optimisation model based on the minimax criterion was proposed for the stochastic time-dependent vehicle routing problem(STDVRP) with hard time windows,considering both the stochastic and time-varying nature of link travel times. A non-dominated sorting ant colony optimisation(NSACO) algorithm was designed to solve this multi-objective optimisation model for the STDVRP.The NSACO algorithm was compared with the non-dominated sorting genetic algorithm II(NSGA-II) through computational instances. The results show that for the Pareto boundary of the minimised number of vehicles,the average number of vehicles for NSACO is 3.33% less than that of NSGA-II,and for the Pareto boundary of the minimised worst travel time,the average worst travel time for NSACO is 17.49% less than that of NSGA-II.
The vehicle routing problem(VRP) is a core issue of distribution logistics. In order to improve the timeliness of deliveries, a multi-objective robust optimisation model based on the minimax criterion was proposed for the stochastic time-dependent vehicle routing problem(STDVRP) with hard time windows,considering both the stochastic and time-varying nature of link travel times. A non-dominated sorting ant colony optimisation(NSACO) algorithm was designed to solve this multi-objective optimisation model for the STDVRP.The NSACO algorithm was compared with the non-dominated sorting genetic algorithm II(NSGA-II) through computational instances. The results show that for the Pareto boundary of the minimised number of vehicles,the average number of vehicles for NSACO is 3.33% less than that of NSGA-II,and for the Pareto boundary of the minimised worst travel time,the average worst travel time for NSACO is 17.49% less than that of NSGA-II.
引文
[1]HALL R W.The fastest path through a network with random time-dependent travel times[J].Transportation Science,1986,20(3):182-188.
[2]MILLER-HOOKS E D,MAHMASSANI H S.Least expected time paths in stochastic,time-varying transportation networks[J].Transportation Science,2000,34(2):198-215.
[3]WELLMAN M P,FORD M,LARSON K.Path planning under time-dependent uncertainty[C]//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence.San Francisco:Morgan Kaufmann Publishers Inc.,1995:532-539.
[4]HUANG H,GAO S.Optimal paths in dynamic networks with dependent random link travel times[J].Transportation Research Part B:Methodological,2012,46(5):579-598.
[5]SIM M.Robust optimization[D].Cambridge:Massachusetts Institute of Technology,2004.
[6]SUN Shichao,DUAN Zhengyu,SUN Shuo,et al.How to find the optimal paths in stochastic time-dependent transportation networks[C]//17th International Conference on Intelligent Transportation Systems.Qingdao:IEEE,2014:2348-2353.
[7]SUN Shichao,DUAN Zhengyu,YANG Dongyuan.Optimal paths planning in dynamic transportation networks with random link travel times[J].Journal of Central South University,2014,21(4):1616-1623.
[8]LECLUYSE C,VAN WOENSEL T,PEREMANS H.Vehicle routing with stochastic time-dependent travel times[J].4OR-A Quarterly Journal of Operations Research,2009,7(4):363-377.
[9]NAHUM O E,HADAS Y.Developing a model for the stochastic time-dependent vehicle-routing problem[C]//International Conference on Computers&Industrial Engineering.Troyes:IEEE,2009:118-123.
[10]NAHUM O E,HADAS Y.A comparison of two algorithms for the stochastic time-dependent vehiclerouting problem[C]//Proceedings of the Transportation Research Board 89th Annual Meeting.Washington,D.C.,USA:Ttansportation Research Board,2010:1-18.
[11]GENDREAU M,JABALI O,REI W.50th anniversary invited article-future research directions in stochastic vehicle routing[J].Transportation Science,2016,50(4):1163-1173.
[12]何承,朱扬勇.城市交通大数据[M].上海:上海科学技术出版社,2015:285-300.
[13]ICHOUA S,GENDREAU M,POTVIN J Y.Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research,2003,144(2):379-396.
[14]谭艳艳.几种改进的分解类多目标进化算法及其应用[D].西安:西安电子科技大学,2013.
[15]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[16]OMBUKI B,ROSS B J,HANSHAR F.Multiobjective genetic algorithms for vehicle routing problem with time windows[J].Applied Intelligence,2006,24(1):17-30.
[17]JEMAI J,ZEKRI M,MELLOULI K.An NSGA-IIalgorithm for the green vehicle routing problem[C]//European Conference on Evolutionary Computation in Combinatorial Optimization.Málaga:Springer Berlin Heidelberg,2012:37-48.
[18]DONATI A V,MONTEMANNI R,CASAGRANDE N,et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal ofOperational Research,2008,185(3):1174-1191.
[19]段征宇,杨东援,王上.时间依赖型车辆路径问题的一种改进蚁群算法[J].控制理论与应用,2010,27(11):1557-1563.DUAN Zhengyu,YANG Dongyuan,WANG Shang.Improved ant colony optimization algorithm for timedependent vehicle routing problem[J].Control Theory&Applications,2010,27(11):1557-1563.
[20]ZHANG T,CHAOVALITWONGSE W A,ZHANGY.Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery[J].Journal of Combinatorial Optimization,2014,28(1):288-309.
[21]SCHAFFER J D.Some experiments in machine learning using vector evaluated genetic algorithms[R].Nashville:Vanderbilt University,1985.
[22]高媛.非支配排序遗传算法(NSGA)的研究与应用[D].杭州:浙江大学,2006.
[23]万旭,林健良,杨晓伟.改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统,2005,4(4):572-576.WAN Xu,LIN Jianliang,YANG Xiaowei.Improved MMAS for vehicle routing problem with time window[J].Computer Integrated Manufacturing Systems,2005,4(4):572-576.
[24]李士勇,陈永强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004:26-33.
[25]STüTZLE T,HOOS H H.MAX-MIN ant system[J].Future Generation Computer Systems,2000,16(8):889-914.
[26]SOLOMON M M.Benchmark problems and solutions[EB/OL].[2016-07-02].http://w.cba.neu.edu/~msolomo n/home.htm.
[2]MILLER-HOOKS E D,MAHMASSANI H S.Least expected time paths in stochastic,time-varying transportation networks[J].Transportation Science,2000,34(2):198-215.
[3]WELLMAN M P,FORD M,LARSON K.Path planning under time-dependent uncertainty[C]//Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence.San Francisco:Morgan Kaufmann Publishers Inc.,1995:532-539.
[4]HUANG H,GAO S.Optimal paths in dynamic networks with dependent random link travel times[J].Transportation Research Part B:Methodological,2012,46(5):579-598.
[5]SIM M.Robust optimization[D].Cambridge:Massachusetts Institute of Technology,2004.
[6]SUN Shichao,DUAN Zhengyu,SUN Shuo,et al.How to find the optimal paths in stochastic time-dependent transportation networks[C]//17th International Conference on Intelligent Transportation Systems.Qingdao:IEEE,2014:2348-2353.
[7]SUN Shichao,DUAN Zhengyu,YANG Dongyuan.Optimal paths planning in dynamic transportation networks with random link travel times[J].Journal of Central South University,2014,21(4):1616-1623.
[8]LECLUYSE C,VAN WOENSEL T,PEREMANS H.Vehicle routing with stochastic time-dependent travel times[J].4OR-A Quarterly Journal of Operations Research,2009,7(4):363-377.
[9]NAHUM O E,HADAS Y.Developing a model for the stochastic time-dependent vehicle-routing problem[C]//International Conference on Computers&Industrial Engineering.Troyes:IEEE,2009:118-123.
[10]NAHUM O E,HADAS Y.A comparison of two algorithms for the stochastic time-dependent vehiclerouting problem[C]//Proceedings of the Transportation Research Board 89th Annual Meeting.Washington,D.C.,USA:Ttansportation Research Board,2010:1-18.
[11]GENDREAU M,JABALI O,REI W.50th anniversary invited article-future research directions in stochastic vehicle routing[J].Transportation Science,2016,50(4):1163-1173.
[12]何承,朱扬勇.城市交通大数据[M].上海:上海科学技术出版社,2015:285-300.
[13]ICHOUA S,GENDREAU M,POTVIN J Y.Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research,2003,144(2):379-396.
[14]谭艳艳.几种改进的分解类多目标进化算法及其应用[D].西安:西安电子科技大学,2013.
[15]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[16]OMBUKI B,ROSS B J,HANSHAR F.Multiobjective genetic algorithms for vehicle routing problem with time windows[J].Applied Intelligence,2006,24(1):17-30.
[17]JEMAI J,ZEKRI M,MELLOULI K.An NSGA-IIalgorithm for the green vehicle routing problem[C]//European Conference on Evolutionary Computation in Combinatorial Optimization.Málaga:Springer Berlin Heidelberg,2012:37-48.
[18]DONATI A V,MONTEMANNI R,CASAGRANDE N,et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal ofOperational Research,2008,185(3):1174-1191.
[19]段征宇,杨东援,王上.时间依赖型车辆路径问题的一种改进蚁群算法[J].控制理论与应用,2010,27(11):1557-1563.DUAN Zhengyu,YANG Dongyuan,WANG Shang.Improved ant colony optimization algorithm for timedependent vehicle routing problem[J].Control Theory&Applications,2010,27(11):1557-1563.
[20]ZHANG T,CHAOVALITWONGSE W A,ZHANGY.Integrated ant colony and tabu search approach for time dependent vehicle routing problems with simultaneous pickup and delivery[J].Journal of Combinatorial Optimization,2014,28(1):288-309.
[21]SCHAFFER J D.Some experiments in machine learning using vector evaluated genetic algorithms[R].Nashville:Vanderbilt University,1985.
[22]高媛.非支配排序遗传算法(NSGA)的研究与应用[D].杭州:浙江大学,2006.
[23]万旭,林健良,杨晓伟.改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统,2005,4(4):572-576.WAN Xu,LIN Jianliang,YANG Xiaowei.Improved MMAS for vehicle routing problem with time window[J].Computer Integrated Manufacturing Systems,2005,4(4):572-576.
[24]李士勇,陈永强,李研.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004:26-33.
[25]STüTZLE T,HOOS H H.MAX-MIN ant system[J].Future Generation Computer Systems,2000,16(8):889-914.
[26]SOLOMON M M.Benchmark problems and solutions[EB/OL].[2016-07-02].http://w.cba.neu.edu/~msolomo n/home.htm.