Learning Combined Set Covering and Traveling Salesman Problem
This addresses scalability issues in combinatorial optimization for real-world applications like logistics, though it is incremental as it builds on existing MIP methods.
The paper tackles the combined Set Covering and Traveling Salesman Problem, which is computationally challenging, by proposing a machine learning approach that learns from historical optimal solutions to reduce the need for repetitive solving via mixed integer programming, with a case study on vaccine distribution in sub-Saharan Africa showing practical application.
The Traveling Salesman Problem is one of the most intensively studied combinatorial optimization problems due both to its range of real-world applications and its computational complexity. When combined with the Set Covering Problem, it raises even more issues related to tractability and scalability. We study a combined Set Covering and Traveling Salesman problem and provide a mixed integer programming formulation to solve the problem. Motivated by applications where the optimal policy needs to be updated on a regular basis and repetitively solving this via MIP can be computationally expensive, we propose a machine learning approach to effectively deal with this problem by providing an opportunity to learn from historical optimal solutions that are derived from the MIP formulation. We also present a case study using the vaccine distribution chain of the World Health Organization, and provide numerical results with data derived from four countries in sub-Saharan Africa.