Learning Combined Set Covering and Traveling Salesman Problem

Abstract

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.

arXiv comment38 pages, 1 figure, 5 tables

References in corpus (10)

• Geometric deep learning: going beyond Euclidean data
• Learning Combinatorial Optimization Algorithms over Graphs
• Neural Combinatorial Optimization with Reinforcement Learning
• Attention, Learn to Solve Routing Problems!
• Optimizing vaccine distribution networks in low and middle-income countries
• Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
• Learning Permutations with Sinkhorn Policy Gradient
• Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information
• Predicting Tactical Solutions to Operational Planning Problems under Imperfect Information
• An Iterative Cyclic Algorithm for Designing Vaccine Distribution Networks in Low and Middle-Income Countries