A hybrid metaheuristic algorithm for the robust pollution-routing problem

Document Type : Research Paper

Authors

1 School of Industrial Engineering, Iran University of Science and Technology

2 Cardiff University

Abstract

Emissions resulted from transportation activities may lead to dangerous effects on the whole environment and human health. According to sustainability principles, in recent years researchers attempt to consider the environmental burden of logistics activities in traditional logistics problems such as vehicle routing problems (VRPs). The pollution-routing problem (PRP) is an extension of the VRP which consists of routing a number of vehicles to serve a set of customers and determining their speed on each route segment so as to minimize a function of comprising fuel, emissions and driver costs. This paper proposes an adaptive large neighborhood search for the robust PRP (RPRP) under demand uncertainty. The achieved results indicate a premium performance of the solutions obtained by the proposed robust models. 

Keywords

Main Subjects

References

Adulyasak, Y., & Jaillet, P. (2015). Models and Algorithms for Stochastic and Robust Vehicle Routing with Deadlines.Transportation Science,50(2),608-626
Almoustafa, S., Hanafi, S., & Mladenović, N. (2013). New exact method for large asymmetric distance-constrained vehicle routing problem. European Journal of Operational Research, 226(3), 386-394.
Baldacci, R., Mingozzi, A., & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1), 1-6.
Barth, M., & Boriboonsomsin, K. (2008). Real-world carbon dioxide impacts of traffic congestion. Transportation Research Record: Journal of the Transportation Research Board, 2058(1), 163-171.
Barth, M., Younglove, T., & Scora, G. (2005). Development of a heavy-duty diesel modal emissions and fuel consumption model.
Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.
Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23(4), 769-805.
Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming, 88(3), 411-424.
Bertsimas, D., & Sim, M. (2003). Robust discrete optimization and network flows. Mathematical programming, 98(1-3), 49-71.
Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53.
Bertsimas, D. J., & Simchi-Levi, D. (1996). A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations research, 44(2), 286-304.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to anumber of delivery points. Operations Research, 12(4), 568–581.
Dabia, S., Demir, E., & Woensel, T. V. (2016). An exact approach for a variant of the pollution-routing problem. Transportation Science, 51(2), 607-628.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
De Jaegere, N., Defraeye, M., & Van Nieuwenhuyse, I. (2014). The vehicle routing problem: state of the art classification and review. FEB Research Report KBI_1415.
Demir, E., Bektaş, T., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the Pollution-Routing Problem. European Journal of Operational Research, 223(2), 346-359.
Demir, E., Bektaş, T., & Laporte, G. (2014). The bi-objective Pollution-Routing Problem. European Journal of Operational Research, 232(3), 464-478.
Drexl, M. (2014). Branch‐and‐cut algorithms for the vehicle routing problem with trailers and transshipments. Networks, 63(1), 119-133.
Eksioglu, B., Vural, A. V., & Reisman, A. (2009). The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4), 1472-1483.
Eshtehadi, R., Fathian, M., & Demir, E. (2017). Robust solutions to the pollution-routing problem with demand and travel time uncertainty. Transportation Research Part D: Transport and Environment, 51, 351-363.
Franceschetti, A., Demir, E., Honhon, D., Van Woensel, T., Laporte, G., & Stobbe, M. (2017). A metaheuristic for the time-dependent pollution-routing problem. European Journal of Operational Research, 259(3), 972-991.
Gendreau, M., G. Laporte, and R. Séguin, Stochastic vehicle routing. European Journal of Operational Research, 1996. 88(1): p. 3-12.
Golden, B. L., Raghavan, S., & Wasil, E. A. (2008). The Vehicle Routing Problem: Latest Advances and New Challenges: latest advances and new challenges (Vol. 43): Springer.
Juan, A., Faulin, J., Grasman, S., Riera, D., Marull, J., & Mendez, C. (2011). Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands. Transportation Research Part C: Emerging Technologies, 19(5), 751-765.
Kirkpatrick, S., Gelatt, C. D., Jr., & Vecchi, M. P. (1983). Optimization by simulatedannealing. Science, 220(4598), 671–680.
Knörr, W. (2008). EcoTransIT: Ecological Transport Information Tool Environmental, Methodology and Data. Update.
Kopfer, H. W., Schönberger, J., & Kopfer, H. (2014). Reducing greenhouse gas emissions of a heterogeneous vehicle fleet. Flexible Services and Manufacturing Journal, 26(1-2), 221-248.
Kwon, Y. J., Choi, Y. J., & Lee, D. H. (2013). Heterogeneous fixed fleet vehicle routing considering carbon emission. Transportation Research Part D: Transport and Environment, 23,81-89.‏‏
Li, X., Tian, P., & Leung, S. C. (2010). Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm. International Journal of Production Economics, 125(1), 137-145.
Li, H., Lv, T., & Li, Y. (2015). The tractor and semitrailer routing problem with many-to-many demand considering carbon dioxide emissions. Transportation Research Part D: Transport and Environment, 34, 68-82.‏
Lin, C., Choy, K., Ho, G., Chung, S., & Lam, H. (2014). Survey of Green Vehicle Routing Problem: Past and future trends. Expert Systems with Applications, 41(4), 1118-1138.
McKinnon, A. (2007). CO2 Emissions from Freight Transport in the UK. Report prepared for the Climate Change Working Group of the Commission for Integrated Transport.
Pishvaee, M., Razmi, J., & Torabi, S. A. (2012). Robust possibilistic programming for socially responsible supply chain network design: A new approach. Fuzzy sets and systems, 206, 1-20
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic forthe pickup and delivery problem with time windows. Transportation Science,40(4), 455–472.
Sbihi, A., & Eglese, R. W. (2007). Combinatorial optimization and green logistics. 4OR, 5(2), 99-116.
Scora, G., & Barth, M. (2006). Comprehensive modal emissions model (CMEM), version 3.01. User guide. Centre for Environmental Research and Technology. University of California, Riverside.
Soyster, A. L. (1973). Technical note—convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154-1157.
Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. Iie Transactions, 40(5), 509-523. 
Journal of Industrial and Systems Engineering
Volume 11, Issue 1
January 2018
Pages 244-257

Files

History

  • Receive Date: 07 October 2017
  • Revise Date: 03 November 2017
  • Accept Date: 03 December 2017

Share

How to cite

Statistics