6533b82ffe1ef96bd12947d2

RESEARCH PRODUCT

The Chinese Postman Problem with Load-Dependent Costs

ÁNgel CorberánJosé M. SanchisGüneş ErdoğanGilbert LaporteIsaac Plana

subject

050210 logistics & transportationMathematical optimization021103 operations researchTraverse/dk/atira/pure/subjectarea/asjc/2200/2205Computational complexity theory05 social sciencesPerspective (graphical)0211 other engineering and technologiesArc-routing problemsTransportation02 engineering and technologyMoment (mathematics)Route inspection problemChinese postman problem/dk/atira/pure/subjectarea/asjc/3300/33130502 economics and businessPollution routingEnhanced Data Rates for GSM EvolutionConstant (mathematics)MATEMATICA APLICADAMetaheuristicCivil and Structural EngineeringMathematics

description

[EN] 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.

10.1287/trsc.2017.0774https://hdl.handle.net/10251/105283