多通路时变网络下低碳车辆路径优化模型与算法
|
摘要
针对城市日益拥堵的交通现状及城市环境污染问题,从现实路网多通路属性的研究入手,设计符合时变网络碳排放计算的时段划分方法,分析了行驶速度变化及车辆载重对排放造成的影响,建立了多通路时变网络下的低碳车辆路径优化模型。基于减少城市环境污染的目标,制定了多通路网络中的通路选择规则,并引入改进冷却函数,设计了双循环模拟退火算法对模型进行求解。通过算例验证了模型与算法减少碳排放的有效性,实验结果表明,多通路时变网络下的车辆配送优化路径可明显降低配送车辆油耗。
In response to the current situation of increasing attention of urban congestion and environment pollution,the multi-graph characteristics of urban road networks were considered,and a time zone division method for carbon emission calculation was designed for the actual time-varying network.By analyzing the impact of speed changes and vehicle loads on the emission,the low-carbon Vehicle Routing Problem(VPR)optimization model under the multigraph time-varying network was proposed.According to the characteristics of the model,apath selection rule based on the fuel consumption was established,and an enhanced cooling function was introduced in the double cycle simulated annealing algorithm.By validating the effectiveness of the model and algorithm through an instance,the result showed that the fuel consumption of distribution vehicles under the multi-graph time-varying network could be significantly reduced.
In response to the current situation of increasing attention of urban congestion and environment pollution,the multi-graph characteristics of urban road networks were considered,and a time zone division method for carbon emission calculation was designed for the actual time-varying network.By analyzing the impact of speed changes and vehicle loads on the emission,the low-carbon Vehicle Routing Problem(VPR)optimization model under the multigraph time-varying network was proposed.According to the characteristics of the model,apath selection rule based on the fuel consumption was established,and an enhanced cooling function was introduced in the double cycle simulated annealing algorithm.By validating the effectiveness of the model and algorithm through an instance,the result showed that the fuel consumption of distribution vehicles under the multi-graph time-varying network could be significantly reduced.
引文
[1]DEMIR E,BEKTA爦T,LAPORTE G.A review of recent research on green road freight transportation[J].European Journal of Operational Research,2014,237(3):775-793.
[2]DANIELE V,PAOLO T.Vehicle routing problems,methods and applications[M].Philadelphia,Pa.,USA:Society for Industrial and Applied Mathematics,2014.
[3]DEMIR E,BEKTA爦T,LAPORTE G.A comparative analysis of several vehicle emission models for road freight transportation[J].Transportation Research Part D:Transport and Environment,2011,16(5):347-357.
[4]FIGLIOZZI M.Vehicle routing problem for emissions minimization[J].Transportation Research Record:Journal of the Transportation Research Board,2010,2197(1):1-7.
[5]KUO Y.Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J].Computers&Industrial Engineering,2010,59(1):157-165.
[6]FRANCESCHETTI A,HONHON D,VAN WOENSEL T,et al.The time-dependent pollution-routing problem[J].Transportation Research Part B:Methodological,2013,56:265-293.
[7]SOYSAL M,BLOEMHOF-RUWAARD J M,BEKTA爦T.The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations[J].International Journal of Production Economics,2015,164:366-378.
[8]HUANG Yixiao,ZHAO Lei,VAN WOENSEL T,et al.Time-dependent vehicle routing problem with path flexibility[J].Transportation Research Part B:Methodological,2017,95:169-195.
[9]GARAIX T,ARTIGUES C,FEILLET D,et al.Vehicle routing problems with alternative paths:an application to on-demand transportation[J].European Journal of Operational Research,2010,204(1):62-75.
[10]SETAK M,HABIBI M,KARIMI H,et al.A time-dependent vehicle routing problem in multigraph with FIFO property[J].Journal of Manufacturing Systems,2015,35:37-45.
[11]QIAN Jiani,EGLESE R.Fuel emissions optimization in vehicle routing problems with time-varying speeds[J].European Journal of Operational Research,2016,248(3):840-848.
[12]ZHANG Junping,WANG Feiyue,WANG Kunfeng,et al.Data-driven intelligent transportation systems:a survey[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1624-1639.
[13]LU Huapu,SUN Zhiyuan,QU Wencong.Big data and its applications in urban intelligenttransportation system[J].Journal of Transportation Systems Engineering and Information Technology,2015,15(5):45-52(in Chinese).[陆化普,孙智源,屈闻聪.大数据及其在城市智能交通系统中的应用综述[J].交通运输系统工程与信息,2015,15(5):45-52.]
[14]LYU Yisheng,DUAN Yanjie,KANG Wenwen,et al.Traffic flow prediction with big data:a deep learning approach[J].IEEE Transactions on Intelligent Transportation Systems,2015,16(2):865-873.
[15]WANG Jingyuan,GU Qian,WU Junjie,et al.Traffic speed prediction and congestion source exploration:a deep learning method[C]//Proceedings of the 16th IEEE International Conference on Data Mining.Washington,D.C.,USA:IEEE,2016:499-508.
[16]KIM G,ONG Y S,CHEONG T,et al.Solving the dynamic vehicle routing problem under traffic congestion[J].IEEETransactions on Intelligent Transportation Systems,2016,17(8):2367-2380.
[17]EHMKE J F,CAMPBELL A M,THOMAS B W.Datadriven approaches for emissions-minimized paths in urban areas[J].Computers&Operations Research,2016,67:34-47.
[18]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.
[19]GHIANI G,GUERRIERO E.A note on the Ichoua,Gendreau,and Potvin(2003)travel time model[J].Transportation Science,2014,48(3):458-462.
[20]HICKMAN J,HASSEL D,JOUMARD R,et al.Methodology for calculating transport emissions and energy consumption[EB/OL].[2017-03-10].http://www.transport-research.info/sites/default/files/project/documents/meet.pdf.
[21]KOURIDIS C,GKATZOFLIAS D,KIOUTSIOUKIS I,et al.Uncertainty estimates and guidance for road transport emission calculations[EB/OL].[2017-03-10].https://webdosya.csb.gov.tr/db/necen/editordosya/file/NEC/COPERT_Training/9_Uncertainty_Estimation_EN.pdf.
[22]NAM E K,GIANNELLI R.Fuel consumption modeling of conventional and advanced technology vehicles in the physical emission rate estimator(PERE)[R].Washington,D.C.,USA:Environmental Protection Agency,2005.
[23]SCORA G,BARTH M.Comprehensive modal emissions model(CMEM),version 3.01[EB/OL].[2017-03-10].https://www.cert.ucr.edu/cmem/docs/CMEM_User_Guide_v3.01d.pdf.
[24]XIAO Y,KONAK A.The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J].Transportation Research Part E:Logistics and Transportation Review,2016,88:146-166.
[25]BENT R,VAN HENTENRYCK P.A two-stage hybrid local search for the vehicle routing problem with time windows[J].Transportation Science,2004,38(4):515-530.
[26]TAVAKKOLI-MOGHADDAM R,SAFAEI N,GHOLI-POUR Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length[J].Applied Mathematics and Computation,2006,176(2):445-454.
[27]MU Dong,WANG Chao,WANG Shengchun,et al.Solving TDVRP based on parallel-simulated annealing algorithm[J].Computer Integrated Manufacturing Systems,2015,21(6):1626-1636(in Chinese).[穆东,王超,王胜春,等.基于并行模拟退火算法求解时间依赖型车辆路径问题[J].计算机集成制造系统,2015,21(6):1626-1636.]
[28]QIAN Xiaoming,SUN Ying,LIU Jian.Solving the watthour meter distribution vehicle routing problem based onhybrid simulated annealing algorithm[J].Computer Integrated Manufacturing Systems,2017,23(11):2553-2560(in Chinese).[钱晓明,孙颖,刘建.基于混合模拟退火算法求解电表配送车辆路径问题[J].计算机集成制造系统,2017,23(11):2553-2560.]
[29]LUNDY M,MEES A.Convergence of an annealing algorithm[J].Mathematical Programming,1986,34(1):111-124.
[30]LEE D H,CAO Zhi,MENG Qiang.Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm[J].International Journal of Production Economics,2007,107(1):115-124.
[31]YANG T,PETERS B A,TU Mingan.Layout design for flexible manufacturing systems considering single-loop directional flow patterns[J].European Journal of Operational Research,2005,164(2):440-455.
[2]DANIELE V,PAOLO T.Vehicle routing problems,methods and applications[M].Philadelphia,Pa.,USA:Society for Industrial and Applied Mathematics,2014.
[3]DEMIR E,BEKTA爦T,LAPORTE G.A comparative analysis of several vehicle emission models for road freight transportation[J].Transportation Research Part D:Transport and Environment,2011,16(5):347-357.
[4]FIGLIOZZI M.Vehicle routing problem for emissions minimization[J].Transportation Research Record:Journal of the Transportation Research Board,2010,2197(1):1-7.
[5]KUO Y.Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J].Computers&Industrial Engineering,2010,59(1):157-165.
[6]FRANCESCHETTI A,HONHON D,VAN WOENSEL T,et al.The time-dependent pollution-routing problem[J].Transportation Research Part B:Methodological,2013,56:265-293.
[7]SOYSAL M,BLOEMHOF-RUWAARD J M,BEKTA爦T.The time-dependent two-echelon capacitated vehicle routing problem with environmental considerations[J].International Journal of Production Economics,2015,164:366-378.
[8]HUANG Yixiao,ZHAO Lei,VAN WOENSEL T,et al.Time-dependent vehicle routing problem with path flexibility[J].Transportation Research Part B:Methodological,2017,95:169-195.
[9]GARAIX T,ARTIGUES C,FEILLET D,et al.Vehicle routing problems with alternative paths:an application to on-demand transportation[J].European Journal of Operational Research,2010,204(1):62-75.
[10]SETAK M,HABIBI M,KARIMI H,et al.A time-dependent vehicle routing problem in multigraph with FIFO property[J].Journal of Manufacturing Systems,2015,35:37-45.
[11]QIAN Jiani,EGLESE R.Fuel emissions optimization in vehicle routing problems with time-varying speeds[J].European Journal of Operational Research,2016,248(3):840-848.
[12]ZHANG Junping,WANG Feiyue,WANG Kunfeng,et al.Data-driven intelligent transportation systems:a survey[J].IEEE Transactions on Intelligent Transportation Systems,2011,12(4):1624-1639.
[13]LU Huapu,SUN Zhiyuan,QU Wencong.Big data and its applications in urban intelligenttransportation system[J].Journal of Transportation Systems Engineering and Information Technology,2015,15(5):45-52(in Chinese).[陆化普,孙智源,屈闻聪.大数据及其在城市智能交通系统中的应用综述[J].交通运输系统工程与信息,2015,15(5):45-52.]
[14]LYU Yisheng,DUAN Yanjie,KANG Wenwen,et al.Traffic flow prediction with big data:a deep learning approach[J].IEEE Transactions on Intelligent Transportation Systems,2015,16(2):865-873.
[15]WANG Jingyuan,GU Qian,WU Junjie,et al.Traffic speed prediction and congestion source exploration:a deep learning method[C]//Proceedings of the 16th IEEE International Conference on Data Mining.Washington,D.C.,USA:IEEE,2016:499-508.
[16]KIM G,ONG Y S,CHEONG T,et al.Solving the dynamic vehicle routing problem under traffic congestion[J].IEEETransactions on Intelligent Transportation Systems,2016,17(8):2367-2380.
[17]EHMKE J F,CAMPBELL A M,THOMAS B W.Datadriven approaches for emissions-minimized paths in urban areas[J].Computers&Operations Research,2016,67:34-47.
[18]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.
[19]GHIANI G,GUERRIERO E.A note on the Ichoua,Gendreau,and Potvin(2003)travel time model[J].Transportation Science,2014,48(3):458-462.
[20]HICKMAN J,HASSEL D,JOUMARD R,et al.Methodology for calculating transport emissions and energy consumption[EB/OL].[2017-03-10].http://www.transport-research.info/sites/default/files/project/documents/meet.pdf.
[21]KOURIDIS C,GKATZOFLIAS D,KIOUTSIOUKIS I,et al.Uncertainty estimates and guidance for road transport emission calculations[EB/OL].[2017-03-10].https://webdosya.csb.gov.tr/db/necen/editordosya/file/NEC/COPERT_Training/9_Uncertainty_Estimation_EN.pdf.
[22]NAM E K,GIANNELLI R.Fuel consumption modeling of conventional and advanced technology vehicles in the physical emission rate estimator(PERE)[R].Washington,D.C.,USA:Environmental Protection Agency,2005.
[23]SCORA G,BARTH M.Comprehensive modal emissions model(CMEM),version 3.01[EB/OL].[2017-03-10].https://www.cert.ucr.edu/cmem/docs/CMEM_User_Guide_v3.01d.pdf.
[24]XIAO Y,KONAK A.The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion[J].Transportation Research Part E:Logistics and Transportation Review,2016,88:146-166.
[25]BENT R,VAN HENTENRYCK P.A two-stage hybrid local search for the vehicle routing problem with time windows[J].Transportation Science,2004,38(4):515-530.
[26]TAVAKKOLI-MOGHADDAM R,SAFAEI N,GHOLI-POUR Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length[J].Applied Mathematics and Computation,2006,176(2):445-454.
[27]MU Dong,WANG Chao,WANG Shengchun,et al.Solving TDVRP based on parallel-simulated annealing algorithm[J].Computer Integrated Manufacturing Systems,2015,21(6):1626-1636(in Chinese).[穆东,王超,王胜春,等.基于并行模拟退火算法求解时间依赖型车辆路径问题[J].计算机集成制造系统,2015,21(6):1626-1636.]
[28]QIAN Xiaoming,SUN Ying,LIU Jian.Solving the watthour meter distribution vehicle routing problem based onhybrid simulated annealing algorithm[J].Computer Integrated Manufacturing Systems,2017,23(11):2553-2560(in Chinese).[钱晓明,孙颖,刘建.基于混合模拟退火算法求解电表配送车辆路径问题[J].计算机集成制造系统,2017,23(11):2553-2560.]
[29]LUNDY M,MEES A.Convergence of an annealing algorithm[J].Mathematical Programming,1986,34(1):111-124.
[30]LEE D H,CAO Zhi,MENG Qiang.Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm[J].International Journal of Production Economics,2007,107(1):115-124.
[31]YANG T,PETERS B A,TU Mingan.Layout design for flexible manufacturing systems considering single-loop directional flow patterns[J].European Journal of Operational Research,2005,164(2):440-455.