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

Said Dabia, Emrah Demir, Tom Van Woensel

    Research output: Contribution to journalArticlepeer-review

    70 Scopus citations


    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 speedand 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 showthe value of the proposed algorithm.

    Original languageBritish English
    Pages (from-to)607-628
    Number of pages22
    JournalTransportation Science
    Issue number2
    StatePublished - 2017


    • Branch and price
    • Fuel consumption
    • Green vehicle routing
    • Vehicle routing problem


    Dive into the research topics of 'An exact approach for a variant of the pollution-routing problem'. Together they form a unique fingerprint.

    Cite this