The Chinese Postman Problem with load-dependent costs

Angel Corberan, Güneş Erdoğan, Gilbert Laporte, Isaac Plana, Jose Maria Sanchis

Research output: Contribution to journal › Article

Abstract

In this paper we introduce an interesting variant of the well-known Chinese Postman Problem (CPP). While in the CPP the cost of traversing an edge is a constant (representing its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment the edge is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two different formulations and propose two metaheuristics for its solution. Extensive computational experiments show the extraordinary difficulty of this problem.
LanguageEnglish
Pages370-385
JournalTransportation Science
Volume52
Issue number2
DOIs
StatusPublished - 1 Mar 2018

Fingerprint

Pollution
costs
Costs
Computational complexity
Experiments
travel
experiment

Cite this

Corberan, A., Erdoğan, G., Laporte, G., Plana, I., & Sanchis, J. M. (2018). The Chinese Postman Problem with load-dependent costs. Transportation Science, 52(2), 370-385. https://doi.org/10.1287/trsc.2017.0774

The Chinese Postman Problem with load-dependent costs. / Corberan, Angel; Erdoğan, Güneş; Laporte, Gilbert; Plana, Isaac; Sanchis, Jose Maria.

In: Transportation Science, Vol. 52, No. 2, 01.03.2018, p. 370-385.

Research output: Contribution to journal › Article

Corberan, A, Erdoğan, G, Laporte, G, Plana, I & Sanchis, JM 2018, 'The Chinese Postman Problem with load-dependent costs', Transportation Science, vol. 52, no. 2, pp. 370-385. https://doi.org/10.1287/trsc.2017.0774
Corberan A, Erdoğan G, Laporte G, Plana I, Sanchis JM. The Chinese Postman Problem with load-dependent costs. Transportation Science. 2018 Mar 1;52(2):370-385. https://doi.org/10.1287/trsc.2017.0774
Corberan, Angel ; Erdoğan, Güneş ; Laporte, Gilbert ; Plana, Isaac ; Sanchis, Jose Maria. / The Chinese Postman Problem with load-dependent costs. In: Transportation Science. 2018 ; Vol. 52, No. 2. pp. 370-385.
@article{332b87a03ada41f3b41ad5e1c0541165,
title = "The Chinese Postman Problem with load-dependent costs",
abstract = "In this paper we introduce an interesting variant of the well-known Chinese Postman Problem (CPP). While in the CPP the cost of traversing an edge is a constant (representing its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment the edge is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two different formulations and propose two metaheuristics for its solution. Extensive computational experiments show the extraordinary difficulty of this problem.",
author = "Angel Corberan and G{\"u}neş Erdoğan and Gilbert Laporte and Isaac Plana and Sanchis, {Jose Maria}",
year = "2018",
month = "3",
day = "1",
doi = "10.1287/trsc.2017.0774",
language = "English",
volume = "52",
pages = "370--385",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "2",

}

TY - JOUR

T1 - The Chinese Postman Problem with load-dependent costs

AU - Corberan, Angel

AU - Erdoğan, Güneş

AU - Laporte, Gilbert

AU - Plana, Isaac

AU - Sanchis, Jose Maria

PY - 2018/3/1

Y1 - 2018/3/1

N2 - In this paper we introduce an interesting variant of the well-known Chinese Postman Problem (CPP). While in the CPP the cost of traversing an edge is a constant (representing its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment the edge is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two different formulations and propose two metaheuristics for its solution. Extensive computational experiments show the extraordinary difficulty of this problem.

AB - In this paper we introduce an interesting variant of the well-known Chinese Postman Problem (CPP). While in the CPP the cost of traversing an edge is a constant (representing its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment the edge is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two different formulations and propose two metaheuristics for its solution. Extensive computational experiments show the extraordinary difficulty of this problem.

U2 - 10.1287/trsc.2017.0774

DO - 10.1287/trsc.2017.0774

M3 - Article

VL - 52

SP - 370

EP - 385

JO - Transportation Science

T2 - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 2

ER -

Access to Document