TY - JOUR
T1 - The bi-objective Pollution-Routing Problem
AU - Demir, Emrah
AU - Bektaş, Tolga
AU - Laporte, Gilbert
N1 - Funding Information:
The authors gratefully acknowledge funding provided by the University of Southampton School of Management and by the Canadian Natural Sciences and Engineering Research Council under Grant 39682-10 . Thanks are due to two anonymous reviewers for their useful comments and for raising interesting points for discussion.
PY - 2014/2/1
Y1 - 2014/2/1
N2 - 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.
AB - 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.
KW - Fuel consumption CO emissions
KW - Heuristics
KW - Multicriteria optimization
KW - Vehicle routing
UR - http://www.scopus.com/inward/record.url?scp=84884588729&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2013.08.002
DO - 10.1016/j.ejor.2013.08.002
M3 - Article
AN - SCOPUS:84884588729
SN - 0377-2217
VL - 232
SP - 464
EP - 478
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 3
ER -
