6533b82ffe1ef96bd12947d2
RESEARCH PRODUCT
The Chinese Postman Problem with Load-Dependent Costs
ÁNgel CorberánJosé M. SanchisGüneş ErdoğanGilbert LaporteIsaac Planasubject
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 EngineeringMathematicsdescription
[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.
year | journal | country | edition | language |
---|---|---|---|---|
2018-03-01 |