The incorporation of emissions minimization in the vehicle routing problem (VRP) is of critical importance to enterprise practice. Focusing on the tractor and semitrailer routing problem with full truckloads between any two terminals of the network, this paper proposes a mathematical programming model with the objective of minimizing emissions per ton-kilometer. A simulated annealing (SA) algorithm is given to solve practical-scale problems. To evaluate the performance of the proposed algorithm, a lower bound is developed. Computational experiments on various problems generated randomly and a realistic instance are conducted. The results show that the proposed methods are effective and the algorithm can provide reasonable solutions within an acceptable computational time. 1. Introduction and Problem Description Along with the growth of the demand for goods, transportation volume is increasing rapidly. For door-to-door transportation, the most widely used mode is road transportation. However, road transportation has some negative impact on the environment because of the land use, energy resource consumption, and so forth. Road transportation accounts for almost 80% of total energy demands from transportation [1]. Fossil fuels are the main energy sources of transportation and is emitted during the combustion of fossil fuels. As a dominant mode of freight movement, road transportation accounts for the largest share of the freight-related emissions [2]. The percentages of road freight transportation emissions compared to the entire transportation sector from 1985 to 2007 in China were between 29% and 34% [3]. More and more tons of are released into the environment annually and the road freight transportation emissions are likely to keep growth. Recent studies on freight transportation have focused not only on cost minimization or profit maximization for a freight company but also on carbon reduction to enhance the corporate social responsibility for the company [4]. The fuel consumption is the most expensive variable cost of the transportation process to road freight transportation enterprises [5]. The efficient use of trucks and road networks becomes more and more important. Compared with costly network infrastructure modifications, optimized routing strategies have been proven to be more efficient in enhancing network capacity [6]. Optimized vehicle routing can reduce the number of trucks and utilize the network better by reducing vehicle movements. The optimization problem has been extensively studied in the literature, known as the vehicle routing
References
[1]
GFEI, “Improving vehicle fuel economy in the ASEAN region,” 2010, http://www.globalfueleconomy.org/Documents/Publications/wp1_asean_fuel_economy.pdf.
[2]
A. C. McKinnon and M. I. Piecyk, “Measurement of CO2 emissions from road freight transport: a review of UK experience,” Energy Policy, vol. 37, no. 10, pp. 3733–3742, 2009.
[3]
H. Q. Li, Y. Lu, J. Zhang, and T. Y. Wang, “Trends in road freight transportation carbon dioxide emissions and policies in China,” Energy Policy, vol. 57, pp. 99–106, 2013.
[4]
D. Y. Lin and K. H. Ng, “The impact of collaborative backhaul routing on carbon reduction in the freight industry,” Transportation Research Part D, vol. 17, no. 8, pp. 626–628, 2012.
[5]
R. Ba？os, J. Ortega, C. Gil, A. Fernández, and F. Toro, “A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows,” Expert Systems with Applications, vol. 40, no. 5, pp. 1696–1707, 2013.
[6]
X. J. Zhang, Z. S. He, Z. He, and L. Rayman-Bacchus, “Probability routing strategy for scale-free networks,” Physica A, vol. 392, no. 4, pp. 953–958, 2013.
[7]
G. Laporte, “Fifty years of vehicle routing,” Transportation Science, vol. 43, no. 4, pp. 408–416, 2009.
[8]
R. Baldacci, P. Toth, and D. Vigo, “Recent advances in vehicle routing exact algorithms,” 4OR, vol. 5, no. 4, pp. 269–298, 2007.
[9]
Y. Kuo, “Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem,” Computers & Industrial Engineering, vol. 59, no. 1, pp. 157–165, 2010.
[10]
L. Pradenas, B. Oportus, and V. Parada, “Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling,” Expert Systems with Applications, vol. 40, no. 8, pp. 2985–2991, 2013.
[11]
M. Drexl, “Applications of the vehicle routing problem with trailers and transshipments,” European Journal of Operational Research, 2012.
[12]
H. Q. Li and Y. Lu, “Tractor and semi-trailer transportation’s effect on the reduction of CO2 emission in China,” in Proceeding of the 7th Advanced Forum on Transportation of China (AFTC ’11), B. H. Mao, S. J. Yang, and L. L. Yang, Eds., pp. 232–237, The Institution of Engineering and Technology: Systems Science and Transportation Development, Beijing, China, 2011.
[13]
E. V. Ierland, C. Graveland, and R. Huiberts, “An environmental economic analysis of the new rail link to european main port Rotterdam,” Transportation Research Part D, vol. 5, no. 3, pp. 197–209, 2000.
[14]
V. C. Hemmelmayr, J. F. Cordeau, and T. G. Crainic, “An adaptive large neighborhood search heuristic for Two-Echelon vehicle routing problems arising in city logistics,” Computers and Operations Research, vol. 39, no. 12, pp. 3215–3228, 2012.
[15]
P. C. Pop, I. Kara, and A. H. Marc, “New mathematical models of the generalized vehicle routing problem and extensions,” Applied Mathematical Modelling, vol. 36, no. 1, pp. 97–107, 2012.
[16]
C. Contardo, V. Hemmelmayr, and T. G. Crainic, “Lower and upper bounds for the two-echelon capacitated location-routing problem,” Computers & Operations Research, vol. 39, no. 12, pp. 3185–3199, 2012.
[17]
I. M. Chao, “A tabu search method for the truck and trailer routing problem,” Computers and Operations Research, vol. 29, no. 1, pp. 33–51, 2002.
[18]
F. Semet and E. Taillard, “Solving real-life vehicle routing problems efficiently using tabu search,” Annals of Operations Research, vol. 41, no. 4, pp. 469–488, 1993.
[19]
J. C. Gerdessen, “Vehicle routing problem with trailers,” European Journal of Operational Research, vol. 93, no. 1, pp. 135–147, 1996.
[20]
M. Caramia and F. Guerriero, “A milk collection problem with incompatibility constraints,” Interfaces, vol. 40, no. 2, pp. 130–143, 2010.
[21]
S. Scheuerer, “A tabu search heuristic for the truck and trailer routing problem,” Computers and Operations Research, vol. 33, no. 4, pp. 894–909, 2006.
[22]
K. C. Tan, Y. H. Chew, and L. H. Lee, “A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems,” European Journal of Operational Research, vol. 172, no. 3, pp. 855–885, 2006.
[23]
S. W. Lin, V. F. Yu, and S. Y. Chou, “Solving the truck and trailer routing problem based on a simulated annealing heuristic,” Computers & Operations Research, vol. 36, no. 5, pp. 1683–1692, 2009.
[24]
J. G. Villegas, C. Prins, C. Prodhon, A. L. Medaglia, and N. Velasco, “A GRASP with evolutionary path relinking for the truck and trailer routing problem,” Computers & Operations Research, vol. 38, no. 9, pp. 1319–1334, 2011.
[25]
J. G. Villegas, C. Prins, C. Prodhon, A. L. Medaglia, and N. Velasco, “GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots,” Engineering Applications of Artificial Intelligence, vol. 23, no. 5, pp. 780–794, 2010.
[26]
S. W. Lin, V. F. Yu, and S. Y. Chou, “A note on the truck and trailer routing problem,” Expert Systems with Applications, vol. 37, no. 1, pp. 899–903, 2010.
[27]
S. W. Lin, V. F. Yu, and C. C. Lu, “A simulated annealing heuristic for the truck and trailer routing problem with time windows,” Expert Systems with Applications, vol. 38, no. 12, pp. 15244–15252, 2011.
[28]
U. Derigs, M. Pullmann, and U. Vogel, “Truck and trailer routing—problems, heuristics and computational experience,” Computers & Operations Research, vol. 40, no. 2, pp. 536–546, 2013.
[29]
V. Pureza, R. Morabito, and M. Reimann, “Vehicle routing with multiple deliverymen: modeling and heuristic approaches for the VRPTW,” European Journal of Operational Research, vol. 218, no. 3, pp. 636–647, 2012.
[30]
L. Bodin, A. Mingozzi, R. Baldacci, and M. Ball, “The rollon-rolloff vehicle routing problem,” Transportation Science, vol. 34, no. 3, pp. 271–288, 2000.
[31]
U. Derigs, M. Pullmann, and U. Vogel, “A short note on applying a simple LS/LNS-based metaheuristic to the rollon-rolloff vehicle routing problem,” Computers & Operations Research, vol. 40, no. 3, pp. 867–872, 2013.
[32]
J. Wy, B-I. Kim, and S. Kim, “The rollon-rolloff waste collection vehicle routing problem with time windows,” European Journal of Operational Research, vol. 224, no. 3, pp. 466–476, 2013.
[33]
R. Baldacci, L. Bodin, and A. Mingozzi, “The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem,” Computers and Operations Research, vol. 33, no. 9, pp. 2667–2702, 2006.
[34]
R. W. Hall and V. C. Sabnani, “Control of vehicle dispatching on a cyclic route serving trucking terminals,” Transportation Research Part A, vol. 36, no. 3, pp. 257–276, 2002.
[35]
P. Francis, G. M. Zhang, and K. Smilowitz, “Improved modeling and solution methods for the multi-resource routing problem,” European Journal of Operational Research, vol. 180, no. 3, pp. 1045–1059, 2007.
[36]
Y. R. Cheng, B. Liang, and M. H. Zhou, “Optimization for vehicle scheduling in iron and steel works based on semi-trailer swap transport,” Journal of Central South University of Technology, vol. 17, no. 4, pp. 873–879, 2010.
[37]
U. Derigs, R. Kurowsky, and U. Vogel, “Solving a real-world vehicle routing problem with multiple use of tractors and trailers and EU-regulations for drivers arising in air cargo road feeder services,” European Journal of Operational Research, vol. 213, no. 1, pp. 309–319, 2011.
[38]
H. Q. Li, Y. Lu, J. Zhang, and T. Y. Wang, “Solving the tractor and semi-trailer routing problem based on a heuristic approach,” Mathematical Problems in Engineering, vol. 2012, Article ID 182584, 12 pages, 2012.
[39]
D. S. H. Hashemi and A. Seifi, “Lower and upper bounds for location-arc routing problems with vehicle capacity constraints,” European Journal of Operational Research, vol. 224, no. 1, pp. 189–208, 2013.
[40]
S. Almoustafa, S. Hanafi, and N. Mladenovi？, “New exact method for large asymmetric distance-constrained vehicle routing problem,” European Journal of Operational Research, vol. 226, no. 3, pp. 386–394, 2013.
[41]
O. Braysy and M. Gendreau, “Vehicle routing problem with time windows, part I: route construction and local search algorithms,” Transportation Science, vol. 39, no. 1, pp. 104–118, 2005.
[42]
L. C. Coelho, J. F. Cordeau, and G. Laporte, “Consistency in multi-vehicle inventory-routing,” Transportation Research Part C, vol. 24, pp. 270–287, 2012.
[43]
J. W. Escobar, R. Linfati, and P. Toth, “A two-phase hybrid heuristic algorithm for the capacitated location-routing problem,” Computers & Operations Research, vol. 40, no. 1, pp. 70–79, 2013.
[44]
European Environment Agency, “Transport at a crossroads—TERM 2008: indicators tracking transport and environment in the European Union,” Tech. Rep., Office for Official Publications of the European Communities, Luxembourg, 2009.
