基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。
From a new perspective of saving energy and reducing emissions, a vehicle routing problem under low-carbon environment is studied, in which transportation services are provided by a third party. The costs of energy, carbon emissions and vehicle leasing are considered simultaneously, which depend not only on distance, but also on client demands and vehicle speed. An energy consumption calculation method is proposed taking into account the vehicle weight and speed. Using the peddling shipment strategy, a low-carbon routing model named LCRP is built. Then, a tabu search algorithm named RS-TS using routes splitting method is designed to solve this model. This algorithm introduces a novel routes encoding and decoding algorithms named WSS, and adopts three neighborhood search methods. Computational results of benchmark instances verify that this algorithm is effective to search the satisfactory solutions, which also shed light on the tradeoffs of distance, energy, travel time and other parameters. Experimental analysis shows that the low-carbon routing arrangement is more economic and environmentally friendly, and selecting medium or low traffic speed is better to save energy consumption and reduce carbon emissions.
[1] Dantzig G, Ramser J. The truck dispathing problem[J]. Management Science, 1959, 6(1):80-91.
[2] Lee DH,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.
[3] Bish EK. A multiple-crane-constrained scheduling problem in a container terminal[J]. European Journal of Operational Research, 2003,144(1):83-107.
[4] 潘震东,唐加福,韩毅.带货物权重的车辆路径问题及遗传算法[J].管理科学学报, 2007, 10(3):23-29.
[5] Biskup D. Single-machine scheduling with learing considerations[J]. European Journal of Operational Research, 1999, 115(1):173-178.
[6] 王晓博,李一军.多车型单配送中心混合装卸车辆路径问题研究[J]. 系统工程学报, 2010,25(5):629-636.
[7] 张景玲, 赵燕伟, 王海燕, 等. 多车型动态需求车辆路径问题建模及优化[J]. 计算机集成制造系统, 2010, 16(3):543-550.
[8] Cafaro C, Cerdá J. Dynamic scheduling of multi-product pipelines with multiple delivery due dates[J]. Computers and Chemical Engineering, 2008, 23(4-5):728-753.
[9] Sbihi A, Eglese R W. Combinatorial optimization and green logistics[J]. 4OR:A Quarterly Journal of Operations Research, 2007,5(2), 99-116.
[10] Palmer A. The development of an integrated routing and carbon dioxide emissions model for goods vehicles[D]. Cranfield,Bedfordshire,England:, Cranfield University, 2007.
[11] Fagerholt K, Laporte G, Norstad I. Reducing fuel emissions by optimizing speed on shipping routes[J]. Journal of the Operational Research Society, 2010,61(3), 523-529.
[12] Maden W, Eglese RW, Black D. Vehicle routing and scheduling with time varying data:a case study[J]. Journal of the Operational Research Society, 2010,61(3),515-522.
[13] Hsu CI, Hung SF, Li H C. Vehicle routing problem with time-windows for perishable food delivery[J]. Journal of Food Engineering, 2007,80(2), 465-475.
[14] Bauer J, Bektas T, Crainic T G. Minimizing greenhouse gas emissions in intermodal freight transport:an application to rail service design[J]. Journal of the Operational Research Society, 2010,61(3),530-542.
[15] 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.
[16] Price R,Thornton S,Nelson S. The social cost of carbon and the shadow price of carbon:what they are, and how to use them in economic appraisal in the UK[R]. Working Paper.Department for Environment, Food, and Rural Affairs-Economics Group,2007.
[17] 李进,傅培华. 基于能耗的带时间窗车辆路径问题建模与仿真[J].系统仿真学报, 2013,25(6):1147-1154.
[18] Demir E, Bektas T, Laporte G. The bi-objective pollution-routing problem[J]. European Journal of Operational Research, 2014,232(3):464-478.
[19] 李建,达庆利,何瑞银.多车次同时集散货物路径问题研究[J].管理科学学报,2010,13(10):1-7.
[20] Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem[J]. Management Science,1994,40(10):1276-1290.
[21] Potvin JY. Genetic algorithms for the traveling salesman problem[J]. Annals of Operations Research, 1996, 63(1):339-370.
[22] Beasley JE. Route first cluster second methods for vehicle routing[J]. Omega, 1983,11(4):403-408.
[23] Christian P. A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers & Operations Research,2004, 31(12):1985-2002.
[24] Kim KH, Chung W J, Hwang H, et al. A distributed dispatching method for the brokerage of truckload freights[J]. International Journal of Production Economics, 2005, 98(2):150-161.
[25] Kuo Y, Chang C C, Chuang P Y.Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds[J]. Computers and Industrial Engineering, 2009, 57(4):1385-1392.
[26] Christofides N, Eilon S. An algorithm for the vehicle dispatching problem[J]. Operational Research Quarterly,1969,20(3):309-318.
