Credit:Unsplash/CC0 Public Domain一种解决旅行推销员问题的新方法——计算机科学中最困难的问题之一——明显优于当前的方法。一个困扰了研究人员90年的臭名昭著的理论问题——旅行推销员问题也与当今的工业有着现实的关联。从本质上来说，这是一个关于如何最好地组合一系列任务的问题，以便以最快和最有效的方式执行这些任务，找到解决问题的好办法可以极大地帮助改善运输和物流等部门。
剑桥大学的研究人员开发了一种混合的、数据驱动的方法来解决这个问题，这种方法不仅能产生高质量的解决方案，而且比其他最先进的方法速度更快。他们的结果在本周的国际学习代表会议上发表。
领导这项研究的剑桥大学计算机科学与技术系的Amanda Prorok博士说:“在疫情期间，我们充分认识到了全球物流系统的重要性。“我们高度依赖这种基础设施来提高效率，我们的解决方案可以帮助实现这一点，因为它针对的是仓库内的物流，如机器人在仓库周围收集货物进行交付，以及仓库外的物流，如将货物运送给人。”
旅行推销员问题涉及一个名义上的送货司机，他必须在一次行程中拜访一定数量的城市，比如20、50或100个通过高速公路连接的城市。挑战在于找到在每个目的地停靠一次的最短可能路线，并快速找到它。
“这个问题有两个关键部分。我们想对停靠点进行排序，我们还想知道按顺序从一个停靠点到另一个停靠点的时间或距离成本。
二十年前，从仓库到目的地的路线可能是预先确定的。但随着今天实时交通信息的可用性，以及向司机发送消息以动态添加或删除送货地点的能力，路线现在可能会在旅程中发生变化。但尽量缩短其长度或持续时间仍然是关键。
等待最佳解决方案或必须做出决策的硬性期限通常会产生成本。例如，司机不能等待新的解决方案被计算出来，他们可能会错过交货，或者交通状况可能会再次发生变化。
这就是为什么需要在有限的计算时间内产生高质量解决方案的通用的、随时可用的组合优化算法。
剑桥开发的混合方法通过结合机器学习模型和“元启发式”工具来实现这一点，机器学习模型提供了关于以前最佳路线的信息，而“元启发式”工具使用这些信息来组合新路线。
“我们希望更快地找到好的解决方案，”该论文的第一作者本·哈德森说。“如果我是一家快递公司的司机，我必须在开车的时候决定下一个目的地。我等不起更好的解决方案。这就是为什么在我们的研究中，我们关注所需的计算时间和我们得到的解决方案的质量之间的权衡。”
为了做到这一点，Hudson提出了一种引导式本地搜索算法，可以区分从一个城市到另一个城市在时间或距离上昂贵的路线，以及包含在旅程中成本较低的路线。这使得研究人员能够快速确定高质量的解决方案，而不是最优的解决方案。
他们通过使用一种他们称之为“全局遗憾”的衡量标准来做到这一点，这种衡量标准是指在引导式局部搜索算法中，每条城市间的路线上，执行一个决定的成本相对于最优解决方案的成本。他们使用机器学习来得出这种“遗憾”的近似值。
“我们已经知道这些问题的正确解决方案，”哈德森说。“所以我们使用了一些机器学习技术，试图从这些解决方案中学习。基于此，我们试图了解一个新问题——不同位置的一组新城市——城市之间的哪些路径是有前途的。
“当我们获得这些信息时，它就会进入算法的下一部分——实际绘制路线的部分。它利用关于最佳路径的额外信息，以比其他方式更快的速度构建出一个好的解决方案。”
他们得出的结果令人印象深刻。他们的实验表明，对于旅行推销员问题，混合的数据驱动方法比最近三种基于学习的方法更快地收敛到最优解。
特别是，当试图解决100个城市的问题时，剑桥方法将平均最优差距从1.534%降至0.705%，提高了两倍。当从20个城市的问题路线推广到100个城市的问题路线时，该方法将最优性差距从18.845%减少到2.622%，提高了7倍。
“很多物流公司在现实生活中使用路线方法，”Hudson说。“我们这项研究的目标是改进这些方法，使它们产生更好的解决方案——导致更短的行驶距离，从而减少碳排放和对环境的影响的解决方案。”
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
