The Chinese Postman Problem with Load-Dependent Costs

Ángel Corberán (), Güneş Erdoğan (), Gilbert Laporte (), Isaac Plana () and José M. Sanchis ()
Additional contact information
Ángel Corberán: Departamento de Estadística e Investigación Operativa, Universitat de València, 46100 Burjassot, Valencia, Spain
Güneş Erdoğan: School of Management, University of Bath, Bath BAZ 7AY, United Kingdom
Gilbert Laporte: HEC Montréal, Montréal, Québec H3T 2A7, Canada
Isaac Plana: Departamento de Matemáticas para la Economía y la Empresa, Universitat de València, 46100 Burjassot, Valencia, Spain
José M. Sanchis: Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, 460222 Valencia, Spain

Transportation Science, 2018, vol. 52, issue 2, 370-385

Abstract: 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 (equal to 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 it 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 mathematical programming formulations, and propose two metaheuristics for its solution. Extensive computational experiments reveal the extraordinary difficulty of this problem.

Keywords: Chinese postman problem; arc-routing problems; pollution routing (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0774 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:2:p:370-385

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().