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.
LI Jin, FU Pei-hua, LI Xiu-lin, ZHANG Jiang-hua, ZHU Dao-li
. Study on Vehicle Routing Problem and Tabu Search Algorithmunder Low-carbon Environment[J]. Chinese Journal of Management Science, 2015
, 23(10)
: 98
-106
.
DOI: 10.16381/j.cnki.issn1003-207x.2015.10.011
[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.
