The bi-objective Pollution-Routing Problem

Emrah Demir, Tolga Bektaş, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

346 Citations (SciVal)


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.

Original languageEnglish
Pages (from-to)464-478
Number of pages15
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 1 Feb 2014


  • Fuel consumption CO emissions
  • Heuristics
  • Multicriteria optimization
  • Vehicle routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'The bi-objective Pollution-Routing Problem'. Together they form a unique fingerprint.

Cite this