The bi-objective pollution-routing problem.

*(English)*Zbl 1305.90053Summary: The bi-objective Pollution-Routing Problem is an extension of the Pollution-Routing Problem (PRP) which consists of routing a number of vehicles to serve a set of customers, and determining their speed on each route segment. The two objective functions pertaining to minimization of fuel consumption and driving time are conflicting and are thus considered separately. This paper presents an adaptive large neighborhood search algorithm (ALNS), combined with a speed optimization procedure, to solve the bi-objective PRP. Using the ALNS as the search engine, four a posteriori methods, namely the weighting method, the weighting method with normalization, the epsilon-constraint method and a new hybrid method (HM), are tested using a scalarization of the two objective functions. The HM combines adaptive weighting with the epsilon-constraint method. To evaluate the effectiveness of the algorithm, new sets of instances based on real geographic data are generated, and a library of bi-criteria PRP instances is compiled. Results of extensive computational experiments with the four methods are presented and compared with one another by means of the hypervolume and epsilon indicators. The results show that HM is highly effective in finding good-quality non-dominated solutions on PRP instances with 100 nodes.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C29 | Multi-objective and goal programming |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

vehicle routing; fuel consumption; CO\(_2\) emissions; multicriteria optimization; heuristics##### Software:

COPERT
PDF
BibTeX
XML
Cite

\textit{E. Demir} et al., Eur. J. Oper. Res. 232, No. 3, 464--478 (2014; Zbl 1305.90053)

Full Text:
DOI

##### References:

[1] | Apaydin, O.; Gonullu, M. T., Emission control with route optimization in solid waste collection process: A case study, Sadhana, 33, 2, 71-82, (2008) |

[2] | Barth, M.; Boriboonsomsin, K., Real-world CO_2 impacts of traffic congestion, Transportation Research Record: Journal of the Transportation Research Board, 2058, 1, 163-171, (2008) |

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

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

[5] | Bowyer, D. P.; Biggs, D. C.; Akçelik, R., Guide to fuel consumption analysis for urban traffic management, Australian Road Research Board Transport Research, 32, (1985) |

[6] | Chankong, V.; Haimes, Y. Y., Optimization-based methods for multiobjective decision-making: an overview, Large Scale Systems, 5, 1, 1-33, (1983) · Zbl 0525.90085 |

[7] | Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, 568-581, (1964) |

[8] | Coello, C. A.C.; Lamont, G. B.; Van Veldhuizen, D. A., Evolutionary algorithms for solving multi-objective problems, (2002), Kluwer Dordrecht · Zbl 1130.90002 |

[9] | Crainic, T. G., Service network design in freight transportation, European Journal of Operational Research, 122, 2, 272-288, (2000) · Zbl 0961.90010 |

[10] | Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), Wiley Chichester, UK · Zbl 0970.90091 |

[11] | Deb, K.; Chaudhuri, S., I-mode: an interactive multi-objective optimization and decision-making using evolutionary methods, Lecture Notes in Computer Science, 4403, 788-802, (2007) |

[12] | Demir, E.; Bektaş, T.; Laporte, G., A comparative analysis of several vehicle emission models for road freight transportation, Transportation Research Part D: Transport and Environment, 6, 5, 347-357, (2011) |

[13] | 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 |

[14] | Eglese, R. W.; Maden, W.; Slater, A., A road timetable™ to aid vehicle routing and scheduling, Computers and Operations Research, 33, 12, 3508-3519, (2006) · Zbl 1094.90006 |

[15] | Ehrgott, M.; Gandibleux, X., Multiple criteria optimization: state of the art annotated bibliographic surveys, (2002), Kluwer Dordrecht · Zbl 1024.00020 |

[16] | Ehrgott, M.; Ryan, D. M., Constructing robust crew schedules with bicriteria optimization, Journal of Multi-Criteria Decision Analysis, 11, 3, 139-150, (2002) · Zbl 1027.90030 |

[17] | Figliozzi, M. A., Vehicle routing problem for emissions minimization, Transportation Research Record: Journal of the Transportation Research Board, 2197, -1, 1-7, (2010) |

[18] | 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, 766-778, (2011) |

[19] | Fonseca, C. M.; Fleming, P. J., An overview of evolutionary algorithms in multiobjective optimization, Evolutionary Computation, 3, 1, 1-16, (1995) |

[20] | Forkenbrock, D. J., External costs of intercity truck freight transportation, Transportation Research Part A: Policy and Practice, 33, 7-8, 505-526, (1999) |

[21] | Forkenbrock, D. J., Comparison of external costs of rail and truck freight transportation, Transportation Research Part A, 35, 4, 321-337, (2001) |

[22] | Fowkes, T.; Whiteing, T., The value of freight travel time savings and reliability improvements - recent evidence from great britain, (European Transport Conference (ETC), (2006), Association for European Transport Strasbourg, France) |

[23] | Grodzevich, O., & Romanko, O. (2006). Normalization and other topics in multi-objective optimization. In Proceedings of the Fields MITACS Industrial Problems Workshop, Toronto. |

[24] | Hickman, J., Hassel, D., Joumard, R., Samaras, Z., & Sorenson, S. (1999). MEET-methodology for calculating transport emissions and energy consumption. European Commission, DG VII. Technical report, ISBN 92-828-6785-4, Luxembourg, 362 p. <http://www.transport-research.info/Upload/Documents/200310/meet.pdf> Accessed 05.05.13. |

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

[26] | Jozefowiez, N.; Semet, F.; Talbi, E. G., From single-objective to multi-objective vehicle routing problems: motivations, case studies, and methods, (Golden, B. L.; Raghavan, S.; Wasil, E. A., The vehicle routing problem: Latest advances and new challenges, (2008), Springer New York), 445-471 · Zbl 1187.90056 |

[27] | Jozefowiez, N.; Semet, F.; Talbi, E. G., Multi-objective vehicle routing problems, European Journal of Operational Research, 189, 2, 293-309, (2008) · Zbl 1148.90338 |

[28] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680, (1983) · Zbl 1225.90162 |

[29] | Laumanns, M.; Thiele, L.; Zitzler, E., An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European Journal of Operational Research, 169, 3, 932-942, (2006) · Zbl 1079.90122 |

[30] | Maden, W.; Eglese, R. W.; Black, D., Vehicle routing and scheduling with time-varying data: A case study, Journal of the Operational Research Society, 61, 3, 515-522, (2009) · Zbl 1196.90070 |

[31] | Mavrotas, G., Effective implementation of the [epsilon]-constraint method in multi-objective mathematical programming problems, Applied Mathematics and Computation, 213, 2, 455-465, (2009) · Zbl 1168.65029 |

[32] | McKinnon, A. (2007). CO_2 Emissions from Freight Transport in the UK. Report prepared for the Climate Change Working Group of the Commission for Integrated Transport. |

[33] | Miettinen, K., Nonlinear multiobjective optimization, (1999), Kluwer Norwell · Zbl 0949.90082 |

[34] | Ntziachristos, L., & Samaras, Z. (2000). COPERT III computer programme to calculate emissions from road transport: methodology and emission factors (version 2.1). Technical report, European Environment Agency, Copenhagen, Denmark. <http://lat.eng.auth.gr/copert/files/tech50.pdf> Accessed 05.05.13. |

[35] | Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles. PhD thesis, Cranfield University, Bedford, United Kingdom. |

[36] | Paquette, J.; Cordeau, J.-F.; Laporte, G.; Pascoal, M. M.B., Combining multicriteria analysis and tabu search for dial-a-ride problems, Transportation Research Part B: Methodological, 52, 1-16, (2013) |

[37] | Pitera, K.; Sandoval, F.; Goodchild, A., Evaluation of emissions reduction in urban pickup systems, Transportation Research Record: Journal of the Transportation Research Board, 2224, 1, 8-16, (2011) |

[38] | PSRC (2010). Chapter 6 air quality and climate change. Technical report, Puget Sound Regional Council, Washington. |

[39] | Qian, F.; Gribkovskaia, I.; Laporte, G.; Halskau, Ø., Passenger and pilot risk minimization in offshore helicopter transportation, Omega, 40, 5, 584-593, (2011) |

[40] | Rangaiah, G. P., Multi-objective optimization: Techniques and applications in chemical engineering, Vol. 1, (2009), World Scientic Singapore |

[41] | Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40, 4, 455-472, (2006) |

[42] | Scora, M., & Barth, G. (2006). Comprehensive modal emission model (CMEM), version 3.01, user’s guide. Technical report. |

[43] | Scott, C.; Urquhart, N.; Hart, E., Influence of topology and payload on CO_2 optimised vehicle routing, Applications of Evolutionary Computation, 141-150, (2010) |

[44] | Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, (Proceedings of the 4th International conference on principles and practice of constraint programming, (1998), Springer New York), 417-431 |

[45] | Tavares, G.; Zsigraiova, Z.; Semiao, V.; Carvalho, M. G., Optimisation of MSW collection routes for minimum fuel consumption using 3D GIS modelling, Waste Management, 29, 3, 1176-1185, (2009) |

[46] | Tavares, G.; Zsigraiova, Z.; Semiao, V.; da Graça Carvalho, M., A case study of fuel savings through optimisation of MSW transportation routes, Management of Environmental Quality: An International Journal, 19, 4, 444-454, (2008) |

[47] | Tight, M. R.; Bristow, A. L.; Pridmore, A.; May, A. D., What is a sustainable level of CO_2 emissions from transport activity in the UK in 2050?, Transport Policy, 12, 3, 235-244, (2005) |

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

[49] | The Government of the United Kingdom (2013). Speed limits, May. <https://www.gov.uk/speed-limits>. |

[50] | Urquhart, N.; Hart, E.; Scott, C., Building low CO_2 solutions to the vehicle routing problem with time windows using an evolutionary algorithm, (Evolutionary computation (CEC), 2010 IEEE congress, (2010), IEEE), 1-6 |

[51] | Urquhart, N.; Scott, C.; Hart, E., Using an evolutionary algorithm to discover low CO_2 tours within a travelling salesman problem, Applications of Evolutionary Computation, 421-430, (2010) |

[52] | Veldhuizen, D. A.V.; Lamont, G. B., Multiobjective evolutionary algorithms: analyzing the state-of-the-art, Evolutionary Computation, 8, 2, 125-147, (2000) |

[53] | Vicente, A. S. (2011). Laying the foundations for greener transport. term 2011: Transport indicators tracking progress towards environmental targets in Europe. EEA Report 7/2011, European Environment Agency, Copenhagen, Denmark. |

[54] | Wierzbicki, A. P., Reference point approach, (Multicriteria decision making: Advances in MCDM models, algorithms, theory, and applications, (1999), Kluwer Dordrecht), 9-39 |

[55] | Wright, L. A.; Kemp, S.; Williams, I., Carbon footprinting: towards a universally accepted definition, Carbon, 2, 1, 61-72, (2011) |

[56] | Zhou, A.; Qu, B. Y.; Li, H.; Zhao, S. Z.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: A survey of the state-of-the-art, Swarm and Evolutionary Computation, 1, 1, 32-49, (2011) |

[57] | Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evolutionary Computation, 8, 2, 173-195, (2000) |

[58] | Zitzler, E., & Thiele, L. (1998a). An evolutionary algorithm for multiobjective optimization: The strength pareto approach. Technical report, TIK Report, Zurich. |

[59] | Zitzler, E., & Thiele, L. (1998b). Multiobjective optimization using evolutionary algorithms: A comparative case study. In 1998: Proceedings on parallel problem solving from nature-PPSN V: 5th international conference, Amsterdam, The Netherlands, September 27-30 (number 1498, p. 292). Amsterdam: Springer-Verlag. |

[60] | Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; da Fonseca, V. G., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Transactions on Evolutionary Computation, 7, 2, 117-132, (2003) |

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.