Abstract
In the context of global pandemics like COVID-19, logistics operations face unique challenges where traditional cost-minimization models fall short. This paper introduces the VRP4E (Vehicle Routing Problem for Epidemics) model, which incorporates "prevention costs"—such as quarantine and disinfection—alongside traditional travel costs. To solve this multi-objective problem, the authors propose MOACS4E, a multi-population ant colony system. By utilizing specialized colonies for each objective and a pheromone fusion mechanism, the algorithm effectively navigates the trade-offs between efficiency and safety. Experimental results on synthetic benchmarks and a real-world case study in the Beijing-Tianjin-Hebei region demonstrate that MOACS4E significantly outperforms existing multi-objective solvers.
Introduction: The Hidden Cost of Epidemic Logistics
Standard vehicle routing models typically assume that the cost of traversing an edge is static, based on distance or time. However, during an epidemic, visiting a high-risk area can trigger significant downstream costs. For instance, a driver entering a "hot zone" might be required to undergo a 14-day quarantine or the vehicle might need intensive disinfection before the next delivery.
As shown in the figure above, a route that takes only 4 days in normal conditions can balloon to over 15 days if a high-risk node is visited early in the sequence. This path-dependency creates a fundamental conflict: the shortest path is often no longer the most cost-effective when prevention measures are factored in.
The MOACS4E Algorithm
To address the conflicting objectives of minimizing travel cost and prevention cost, the authors developed the MOACS4E algorithm. Its architecture relies on three key components:
- Multi-Population Framework (MPMO): The system employs two distinct ant colonies. One colony is dedicated to minimizing travel distance, while the other focuses exclusively on minimizing prevention costs. This specialization allows the algorithm to find high-quality solutions at the extremes of the Pareto front.
- Pheromone Fusion-Based Solution Generation (PFSG): To explore the trade-offs between the two objectives, a third set of solutions is generated by "fusing" the pheromone trails from both specialist colonies. This encourages the discovery of balanced solutions that might be missed by single-objective approaches.
- Solution Quality Improvement (SQI): A local search heuristic specifically designed for epidemic routing. It reorders stops within a route to delay visits to high-risk areas as much as possible, thereby minimizing the number of subsequent stops affected by prevention protocols.
Key Insights: Quantifying the Conflict
A critical contribution of this research is the formalization of the "Confliction Probability" (CP). The authors demonstrate that travel and prevention costs are almost always in opposition.
As illustrated in the graph, the CP remains near 1.0 for a wide range of high-risk area densities. This confirms that a multi-objective approach is essential; optimizing for distance alone will almost certainly lead to excessive prevention costs, and vice-versa.
Results and Real-World Application
The MOACS4E algorithm was rigorously tested against six state-of-the-art multi-objective solvers, including NSGA-II and MOEA/D. Across 25 synthetic benchmarks, MOACS4E achieved superior Hypervolume (HV) scores in 72% of cases, indicating a better ability to find a diverse and high-quality set of trade-off solutions.
In a real-world case study of the Beijing-Tianjin-Hebei region using data from January 2021, the model successfully identified routes that balanced regional safety requirements with logistical efficiency. MOACS4E reduced the average "driver-days" lost to prevention measures by approximately 35% compared to standard genetic algorithms, proving its practical value for pandemic response.
Conclusion
The VRP4E model and MOACS4E algorithm provide a robust framework for logistics planning during public health crises. By treating prevention costs as a primary objective and leveraging multi-population ant colony optimization, the system offers a practical tool for maintaining supply chains while adhering to vital safety protocols. Future work will look to incorporate dynamic risk levels and specific delivery time windows to further enhance the model's real-world applicability.
Summary updated