An exact approach for a variant of the pollution-routing problem

S. Dabia, E. Demir, T. van Woensel

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)

Abstract

The pollution-routing problem (PRP) is a recently introduced green vehicle routing problem in the field of green logistics. It concerns routing a number of vehicles to serve a set of geographically dispersed customers within their time windows, jointly with determining their speed on each arc so as to minimize fuel and driving costs. Because of its complexity, all known solution methods are based on (meta-)heuristics. This paper presents an exact solution based on a branch-and-price algorithm for a variant of the PRP. The master problem is a set-partitioning problem, and the pricing problem is a speed- and start-time elementary shortest path problem with resource constraints, in which the speed and start time at the depot needs to be decided on for each individual route. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. New dominance criteria are developed to discard unpromising labels by exploiting the structure of the ready time and the fuel consumption functions. Extensive computational experiments show the value of the proposed algorithm.

Keywords: green vehicle routing; fuel consumption; vehicle routing problem; branch and price
LanguageEnglish
Pages607 - 628
Number of pages22
JournalTransportation Science
Volume51
Issue number2
DOIs
StatePublished - 1 May 2017

Fingerprint

Vehicle routing
Pollution
Fuel consumption
Costs
Labeling
Logistics
Labels
pricing
consumption function
Experiments
heuristics
customer
logistics

Cite this

@article{29a76b2156fd4f3fa54bf05d5a0b562a,
title = "An exact approach for a variant of the pollution-routing problem",
abstract = "The pollution-routing problem (PRP) is a recently introduced green vehicle routing problem in the field of green logistics. It concerns routing a number of vehicles to serve a set of geographically dispersed customers within their time windows, jointly with determining their speed on each arc so as to minimize fuel and driving costs. Because of its complexity, all known solution methods are based on (meta-)heuristics. This paper presents an exact solution based on a branch-and-price algorithm for a variant of the PRP. The master problem is a set-partitioning problem, and the pricing problem is a speed- and start-time elementary shortest path problem with resource constraints, in which the speed and start time at the depot needs to be decided on for each individual route. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. New dominance criteria are developed to discard unpromising labels by exploiting the structure of the ready time and the fuel consumption functions. Extensive computational experiments show the value of the proposed algorithm. Keywords: green vehicle routing; fuel consumption; vehicle routing problem; branch and price",
author = "S. Dabia and E. Demir and {van Woensel}, T.",
year = "2017",
month = "5",
day = "1",
doi = "10.1287/trsc.2015.0651",
language = "English",
volume = "51",
pages = "607 -- 628",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "2",

}

An exact approach for a variant of the pollution-routing problem. / Dabia, S.; Demir, E.; van Woensel, T.

In: Transportation Science, Vol. 51, No. 2, 01.05.2017, p. 607 - 628.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - An exact approach for a variant of the pollution-routing problem

AU - Dabia,S.

AU - Demir,E.

AU - van Woensel,T.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - The pollution-routing problem (PRP) is a recently introduced green vehicle routing problem in the field of green logistics. It concerns routing a number of vehicles to serve a set of geographically dispersed customers within their time windows, jointly with determining their speed on each arc so as to minimize fuel and driving costs. Because of its complexity, all known solution methods are based on (meta-)heuristics. This paper presents an exact solution based on a branch-and-price algorithm for a variant of the PRP. The master problem is a set-partitioning problem, and the pricing problem is a speed- and start-time elementary shortest path problem with resource constraints, in which the speed and start time at the depot needs to be decided on for each individual route. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. New dominance criteria are developed to discard unpromising labels by exploiting the structure of the ready time and the fuel consumption functions. Extensive computational experiments show the value of the proposed algorithm. Keywords: green vehicle routing; fuel consumption; vehicle routing problem; branch and price

AB - The pollution-routing problem (PRP) is a recently introduced green vehicle routing problem in the field of green logistics. It concerns routing a number of vehicles to serve a set of geographically dispersed customers within their time windows, jointly with determining their speed on each arc so as to minimize fuel and driving costs. Because of its complexity, all known solution methods are based on (meta-)heuristics. This paper presents an exact solution based on a branch-and-price algorithm for a variant of the PRP. The master problem is a set-partitioning problem, and the pricing problem is a speed- and start-time elementary shortest path problem with resource constraints, in which the speed and start time at the depot needs to be decided on for each individual route. The master problem is solved by means of column generation, and a tailored labeling algorithm is used to solve the pricing problem. New dominance criteria are developed to discard unpromising labels by exploiting the structure of the ready time and the fuel consumption functions. Extensive computational experiments show the value of the proposed algorithm. Keywords: green vehicle routing; fuel consumption; vehicle routing problem; branch and price

U2 - 10.1287/trsc.2015.0651

DO - 10.1287/trsc.2015.0651

M3 - Article

VL - 51

SP - 607

EP - 628

JO - Transportation Science

T2 - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 2

ER -