论文标题
学习组合集覆盖和旅行推销员问题
Learning Combined Set Covering and Traveling Salesman Problem
论文作者
论文摘要
旅行推销员问题是由于其现实世界应用程序范围及其计算复杂性，因此研究最深入研究的组合优化问题之一。当与设置覆盖问题结合使用时，它会引发更多与障碍性和可伸缩性有关的问题。我们研究组合的涵盖和旅行推销员问题，并提供混合整数编程公式来解决问题。由需要定期更新最佳策略并通过MIP重复解决此问题的应用程序在计算上可能很昂贵，我们提出了一种机器学习方法来有效地解决此问题，通过提供机会从MIP公式中得出的历史最佳解决方案学习。我们还使用世界卫生组织的疫苗分销链提出了一项案例研究，并通过来自撒哈拉以南非洲四个国家的数据提供数值结果。
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.
