The Chinese Postman Problem with Load-Dependent Costs
研究了中国邮递员问题的一个新变种，其中遍历边的成本不仅取决于长度，还取决于车辆当时的载重，受减少运输污染的启发，提出了两种数学规划模型和两种元启发式算法。
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.