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.
Original language | English |
---|---|
Pages (from-to) | 370-385 |
Number of pages | 16 |
Journal | Transportation Science |
Volume | 52 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Mar 2018 |
Keywords
- Arc-routing problems
- Chinese postman problem
- Pollution routing
ASJC Scopus subject areas
- Civil and Structural Engineering
- Transportation
Fingerprint
Dive into the research topics of 'The Chinese Postman Problem with load-dependent costs'. Together they form a unique fingerprint.Profiles
-
Gunes Erdogan
- Management - Professor
- Information, Decisions & Operations - Director of Studies MSc in Business Analytics
- Centre for Healthcare Innovation and Improvement
- Institute for Mathematical Innovation (IMI)
- Smart Warehousing and Logistics Systems
Person: Research & Teaching, Researcher
Equipment
-
Balena High Performance Computing (HPC) System
Facility/equipment: Equipment
-
High Performance Computing (HPC) Facility
Chapman, S. (Manager)
University of BathFacility/equipment: Facility