A matheuristic approach for the pollution-routing problem.

*(English)*Zbl 1346.90143Summary: This paper deals with the Pollution-Routing Problem (PRP), a Vehicle Routing Problem (VRP) with environmental considerations, recently introduced in the literature by T. Bektaş and G. Laporte [“The pollution-routing problem”, Transp. Res. B: Methodological 45, No. 8, 1232–1250 (2011)]. The objective is to minimize operational and environmental costs while respecting capacity constraints and service time windows. Costs are based on driver wages and fuel consumption, which depends on many factors, such as travel distance and vehicle load. The vehicle speeds are considered as decision variables. They complement routing decisions, impacting the total cost, the travel time between locations, and thus the set of feasible routes. We propose a method which combines a local search-based metaheuristic with an integer programming approach over a set covering formulation and a recursive speed-optimization algorithm. This hybridization enables to integrate more tightly route and speed decisions. Moreover, two other “green” VRP variants, the Fuel Consumption VRP (FCVRP) and the Energy Minimizing VRP (EMVRP), are addressed, as well as the VRP with time windows (VRPTW) with distance minimization. The proposed method compares very favorably with previous algorithms from the literature, and new improved solutions are reported for all considered problems.

##### Keywords:

combinatorial optimization; green logistics; vehicle routing; time windows; speed optimization
PDF
BibTeX
XML
Cite

\textit{R. Kramer} et al., Eur. J. Oper. Res. 243, No. 2, 523--539 (2015; Zbl 1346.90143)

Full Text:
DOI

##### References:

[1] | Alvarenga, G.; Mateus, G.; de Tomi, G., A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows, Computers & Operations Research, 34, 6, 1561-1584, (2007) · Zbl 1163.90357 |

[2] | Baldacci, R.; Mingozzi, A.; Roberti, R., New route relaxation and pricing strategies for the vehicle routing problem, Operations Research, 59, 5, 1269-1283, (2011) · Zbl 1233.90059 |

[3] | Barth, M.; Boriboonsomsin, K., Real-world carbon dioxide impacts of traffic congestion, Transportation Research Record, 1, 2058, 163-171, (2008) |

[4] | Barth, M.; Younglove, T.; Scora, G., Development of a heavy-duty diesel modal emissions and fuel consumption model, Technical Report, (2005), California Partners for Advanced Transit and Highways (PATH) UC Berkeley |

[5] | Bektaş, T.; Laporte, G., The pollution-routing problem, Transportation Research Part B: Methodological, 45, 8, 1232-1250, (2011) |

[6] | Christofides, N.; Mingozzi, A.; Toth, P., Combinatorial optimization, 315-338, (1979), Wiley Chinchester, UK |

[7] | Dekker, R.; Bloemhof, J.; Mallidis, I., Operations research for Green logistics—an overview of aspects, issues, contributions and challenges, European Journal of Operational Research, 219, 3, 671-679, (2012) |

[8] | Demir, E., Models and algorithms for the pollution-routing problem and its variations, (2012), University of Southampton, School of Management United Kingdom, (Ph.D. thesis) |

[9] | Demir, E.; Bektaş, T.; Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, European Journal of Operational Research, 223, 2, 346-359, (2012) · Zbl 1292.90045 |

[10] | Demir, E.; Bektaş, T.; Laporte, G., The bi-objective pollution-routing problem, European Journal of Operational Research, 232, 3, 464-478, (2014) · Zbl 1305.90053 |

[11] | Demir, E.; Bektaş, T.; Laporte, G., A review of recent research on Green road freight transportation, European Journal of Operational Research, 237, 3, 775-793, (2014) · Zbl 1338.90004 |

[12] | Figliozzi, M. A., The impacts of congestion on time-definitive urban freight distribution networks CO_2 emission levels: results from a case study in Portland, oregon, Transportation Research Part C: Emerging Technologies, 19, 5, 766-778, (2011) |

[13] | Franceschetti, A.; Honhon, D.; van Woensel, T.; Bektaş, T.; Laporte, G., The time-dependent pollution-routing problem, Transportation Research Part B: Methodological, 56, 265-293, (2013) |

[14] | Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I.-M., Fleet management and logistics, 33-56), (1998), Kluwer Boston |

[15] | Hvattum, L. M.; Norstad, I.; Fagerholt, K.; Laporte, G., Analysis of an exact algorithm for the vessel speed optimization problem, Networks, 62, 2, 132-135, (2013) · Zbl 1338.68107 |

[16] | ICF (2006). Assessment of greenhouse gas analysis techniques for transportation projects. NCHRP Project 25-25 Task 17, ICF Consulting. |

[17] | Jabali, O.; Van Woensel, T.; de Kok, A., Analysis of travel times and CO_2 emissions in time-dependent vehicle routing, Production and Operations Management, 21, 6, 1060-1074, (2012) |

[18] | Kara, I.; Kara, B. Y.; Yetis, M. K., Energy minimizing vehicle routing problem, (Dress, A.; Xu, Y.; Zhu, B., Proceedings of the combinatorial optimization and applications, Lecture Notes in Computer Science, Vol. 4616, (2007), Springer Berlin Heidelberg), 62-71 · Zbl 1175.90333 |

[19] | Kara, I.; Kara, B. Y.; Yetis, M. K., Vehicle routing problem, (Tonic, C.; Hrvoje, G., Commulative vehicle routing problems, (2008), InTech), 85-98 |

[20] | Kopfer, H.; Schnberger, J.; Kopfer, H., Reducing greenhouse gas emissions of a heterogeneous vehicle fleet, Flexible Services and Manufacturing Journal, 26, 1-2, 221-248, (2014) |

[21] | Kuo, Y., Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem, Computers & Industrial Engineering, 59, 1, 157-165, (2010) |

[22] | Kuo, Y.; Wang, C.-C., Optimizing the VRP by minimizing fuel consumption, Management of Environmental Quality: An International Journal, 22, 4, 440-450, (2011) |

[23] | Labadi, N.; Prins, C.; Reghioui, M., A memetic algorithm for the vehicle routing problem with time windows, RAIRO—Operations Research, 42, 415-431, (2008) · Zbl 1152.90334 |

[24] | Lin, C.; Choy, K.; Ho, G.; Chung, S.; Lam, H., Survey of Green vehicle routing problem: past and future trends, Expert Systems with Applications, 41, 4, 1118-1138, (2014) |

[25] | (Maniezzo, V.; Stützle, T.; Voß, S., (2009), Springer New York) |

[26] | Muter, I.; Birbil, S. I.; Sahin, G., Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems, INFORMS Journal on Computing, 22, 4, 603-619, (2010) · Zbl 1243.90257 |

[27] | Norstad, I.; Fagerholt, K.; Laporte, G., Tramp ship routing and scheduling with speed optimization, Transportation Research Part C-Emerging Technologies, 19, 5, SI, 853-865, (2011) |

[28] | Palmer, A., The development of an integrated routing and carbon dioxide emissions model for goods vehicles, (2007), Cranfield University. School of Management United Kingdom, (Ph.D. thesis) |

[29] | Peng, Y.; Wang, X., Research on a vehicle routing schedule to reduce fuel consumption, Proceedings of the 2009 international conference on measuring technology and mechatronics automation: Vol. 3, ICMTMA ’09, 825-827, (2009), IEEE Computer Society Washington, DC, USA |

[30] | Penna, P. H.V.; Subramanian, A.; Ochi, L. S., An iterated local search heuristic for the heterogeneous fleet vehicle routing problem, Journal of Heuristics, 19, 201-232, (2013) |

[31] | Røpke, S. (2012). Branching decisions in branch-and-cut-and-price algorithms for vehicle routing problems. Presentation in International Workshop on Column Generation. Available at http://www.gerad.ca/colloques/ColumnGeneration2012/presentations/session7/Ropke.pdf. |

[32] | Saberi, M.; Verbas, I. O., Continuous approximation model for the vehicle routing problem for emissions minimization at the strategic level, Journal of Transportation Engineering-ASCE, 138, 11, 1368-1376, (2012) |

[33] | Salimifard, K.; Shahbandarzadeh, H.; Raeesi, R., Green transportation and the role of operation research, Proceedings of 2012 international conference on traffic and transportation engineering, Vol. 26, (2012), IACSIT Press Singapore |

[34] | Scora, M.; Barth, M., Comprehensive modal emission model (CMEM), version 3.01, user’s guide, Technical Report, (2006), Center for Environmental Research and Technology University of California, Riverside |

[35] | Scott, C.; Urquhart, N.; Hart, E., Influence of topology and payload on CO_2 optimised vehicle routing, (Chio, C.; Brabazon, A.; Caro, G.; Ebner, M.; Farooq, M.; Fink, A.; Grahl, J.; Greenfield, G.; Machado, P.; O’Neill, M.; Tarantino, E.; Urquhart, N., Applications of evolutionary computation, Lecture Notes in Computer Science, Vol. 6025, (2010), Springer Berlin Heidelberg), 141-150 |

[36] | Solomon, M., Algorithms for the vehicle-routing and scheduling problems with time window constraints, Operations Research, 35, 2, 254-265, (1987) · Zbl 0625.90047 |

[37] | Subramanian, A., Heuristic, exact and hybrid approaches for vehicle routing problems, (2012), Universidade Federal Fluminense Niterói, Rio de Janeiro, Brazil, (Ph.D. thesis) |

[38] | Subramanian, A.; Drummond, L. M.A.; Bentes, C.; Ochi, L. S.; Farias, R., A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 37, 11, 1899-1911, (2010) · Zbl 1188.90041 |

[39] | Subramanian, A.; Uchoa, E.; Ochi, L. S., A hybrid algorithm for a class of vehicle routing problems, Computers & Operations Research, 40, 10, 2519-2531, (2013) · Zbl 1348.90132 |

[40] | Subramanian, A.; Penna, P. H.V.; Uchoa, E.; Ochi, L. S., A hybrid algorithm for the heterogeneous fleet vehicle routing problem, European Journal of Operational Research, 221, 2, 285-295, (2012) · Zbl 1253.90054 |

[41] | Ubeda, S.; Arcelus, F.; Faulin, J., Green logistics at eroski: A case study, International Journal of Production Economics, 131, 1, 44-51, (2011) |

[42] | Vidal, T.; Crainic, T.; Gendreau, M.; Prins, C., Heuristics for multi-attribute vehicle routing problems: a survey and synthesis, European Journal of Operational Research, 231, 1, 1-21, (2013) · Zbl 1317.90006 |

[43] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research, 40, 1, 475-489, (2013) · Zbl 1349.90137 |

[44] | Xiao, Y.; Zhao, Q.; Kaku, I.; Xu, Y., Development of a fuel consumption optimization model for the capacitated vehicle routing problem, Computers & Operations Research, 39, 7, 1419-1431, (2012) · Zbl 1251.90063 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.