A Hybrid Matheuristic Framework for the Chinese Postman Problem with Load-Dependent Costs

Technical Summary: A Hybrid Matheuristic Framework for the Chinese Postman Problem with Load-Dependent Costs

Problem Definition
This paper addresses the Chinese Postman Problem with Load-Dependent Costs (CPP-LC), a variant of the classical Arc Routing Problem (ARP). In the CPP-LC, the cost of traversing an edge is not solely a function of its length but also depends on the vehicle's gross weight (curb weight plus current payload) at the time of traversal. This formulation reflects real-world logistics where fuel consumption and emissions increase with vehicle load. Unlike the standard CPP, which is polynomially solvable, the CPP-LC is generally strongly NP-hard. The objective is to find a route starting and ending at a depot that services every edge in a connected graph at least once while minimizing the total load-dependent travel cost.

Methodology
The authors propose MaLD, a hybrid matheuristic framework that integrates metaheuristic search with mathematical programming to balance exploration and intensification. The framework operates through the following components:

1. Mathematical Formulation: The study utilizes an arc-routing Mixed-Integer Linear Programming (MILP) formulation (adapted from Corberán et al.) to model the problem. To enhance computational efficiency, the authors employ "reduced" MILP models that focus on specific subsequences of edges rather than the entire problem instance.
2. Local Search: An initial solution is generated using a Greedy Constructive Heuristic (GCH). This is refined via a local search procedure that employs a "general shift" move. In this move, a subset of edges is randomly removed and reinserted into the sequence at positions that minimize total cost, evaluated using a dynamic programming approach to determine optimal traversal directions.
3. Reordering Procedure: A critical preprocessing step ensures that the route satisfies the constraint that an edge is serviced the first time it is visited. If an edge is deadheaded (traversed without service) before being serviced, the sequence is reordered to service it earlier. This adjustment often reduces the vehicle's load sooner, lowering subsequent deadheading costs.
4. Intensification: Following local search and reordering, the algorithm enters an intensification phase. A subsequence of consecutive edges is selected, and a reduced MILP model is solved to find the optimal permutation of these edges while keeping the rest of the route fixed. This allows for deep exploration of specific neighborhoods that pure metaheuristics might miss.
5. Ant Colony Optimization (ACO): To provide a comprehensive comparison, the authors also implement an ACO metaheuristic. In this approach, artificial ants construct solutions by traversing states representing edges and their traversal directions. Pheromone trails are updated based on solution quality to guide future searches.

Key Contributions

• Hybrid Framework: The primary contribution is the design of MaLD, which effectively combines the speed of heuristic local search with the exactness of MILP-based intensification.
• Algorithmic Extension: While previous work (Corberán et al.) introduced Iterated Local Search (ILS) and Variable Neighborhood Search (VNS) for CPP-LC, this paper introduces ACO as a comparative metaheuristic and develops the MaLD framework to outperform existing methods.
• Scalability and Efficiency: The paper demonstrates that solving reduced MILP models on subsequences allows the framework to escape local optima found by pure metaheuristics, particularly in larger instances, without incurring the prohibitive time costs of solving the full MILP.

Experimental Results
The proposed methods were evaluated on three datasets ranging from small (8–10 edges) to large (up to 232 edges), covering Eulerian graphs and instances from Christofides and Hertz et al.

• Solution Quality: MaLD consistently achieved the highest solution quality. It found optimal solutions for all small instances where optima were known and outperformed ILS, VNS, and ACO on medium and large instances. Specifically, MaLD improved upon ILS and VNS solutions by approximately 6–7% for medium-sized instances and by an average of 1.35% for the largest instances.
• Computational Efficiency:
  • Small Instances: For very small instances, GCH was the fastest, and ILS/VNS were highly competitive. MaLD was slightly slower but still reached optimality.
  • Large Instances: ACO demonstrated strong scalability, often outperforming ILS and VNS in solution quality while maintaining significantly lower computational times due to its parallel execution capabilities. However, MaLD remained superior in solution quality, albeit with higher computational costs (e.g., ~1262 seconds for the largest group vs. ~14 seconds for ACO).
• Component Analysis: Sensitivity analysis revealed that the intensification component is critical for solution quality in larger instances, contributing more to cost reduction than the local search component in those scenarios. Removing intensification led to significant cost increases (e.g., ~211,000 units for the largest group).

Significance and Claims
The paper claims that the MaLD framework is an effective strategy for solving complex, load-dependent routing problems where travel costs are dynamic based on payload. The results highlight that hybrid optimization strategies, which bridge operations research (exact MILP) and intelligent computational methods (metaheuristics), are necessary to address the strong NP-hardness of the CPP-LC. While ACO proves to be a competitive and scalable alternative for large instances, the matheuristic approach provides the most robust solution quality. The authors note that their implementation and datasets are publicly available to facilitate further research in smart logistics and energy-aware routing.