Abstract
Language | English |
---|---|
Pages | 370-385 |
Journal | Transportation Science |
Volume | 52 |
Issue number | 2 |
DOIs | |
Status | Published - 1 Mar 2018 |
Fingerprint
Cite this
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
}
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 -