旅行商问题及其解决方法

一、说明

旅行商问题 (TSP)是指一位上门推销员在给定的时间段内（通常是一个工作日）试图找到最短和/或最快的路线来服务他所访问的所有站点。虽然这曾经是销售人员的问题，但如今面临这个问题的工人要多得多。近年来，电子商务和网上购物的蓬勃发展使得直接送货上门的商品比以往任何时候都多。对于送货司机来说，这意味着每天要送货到 100 多个地点。

因此，解决旅行商问题至关重要！

在本文中，我们将更详细地研究这个问题，并讨论它对快递员和最后一英里承运商等各个行业的重要性。如果您在为销售人员或送货团队安排路线方面遇到困难，那么我们可以为您提供解决方案。我们还将研究该问题的一些解决方案，并讨论哪种路线优化软件最适合解决您自己的 TSP 问题。

二、什么是旅行商问题？

旅行商问题( TSP) 指的是在地图上找到任意多个站点之间的最短路线的挑战。它的名字源于上门推销员面临的历史挑战，他们需要在尽可能短的时间内拜访尽可能多的潜在客户，以增加销售量。

TSP 已成为物理学、计算机科学等研究领域以及后来的物流和运筹学中著名的算法问题。

三、旅行商问题为何重要？

对于商业而言，时间就是金钱，无论您从事什么行业，如果涉及乘车辆在多个地点之间往返，您都需要确保以最有效的方式进行。

考虑一下：
根据路线顾问的数据，美国的联邦快递地面司机每天平均行驶 100 英里或更少，每天停靠 150-230 次，其中包括取件。

信不信由你，每个站点都有数万亿（是的，数万亿）种独特的服务方式。当然，其中一些显然不是最有效的路线，但实际上确定哪一条是最有效的路线可能是一个挑战，这仍然超出了人类的实际能力。

很久以前，这仅仅是一个现场销售问题，如今已成为供应链物流行业一个非常现实的问题。对于任何拥有多辆汽车的企业来说，确保它们都以最高效的方式运送货物可能是其是否拥有可行的商业模式的关键。

通过尝试解决 TSP，我们可以找到送货司机在路上最有效的路线。这样可以减少行驶距离、减少燃料消耗和减少驾驶时间。这意味着任何基于送货的业务运营的资产负债表都会获得双重奖励。

但旅行商问题 (TSP) 不仅对企业的财务可行性很重要。随着减少碳足迹的重要性日益增加，减少旅行距离直接导致化石燃料的燃烧量。我们每个人都应尽一份力，通过解决问题来实现如此重要的变革的能力对整个社会来说也是一种福利。事实上，最近为减少政治家访问英国所花费的时间而做出的努力表明了这个问题有多么困难。

解决这一问题 (TSP) 的好处也会惠及依赖及时高效送货的客户。无论他们是需要送货来经营自己的业务，还是依赖按时送货来治疗个人疾病，它都会对依赖它的每个人产生现实影响。信不信由你，客户体验（或者在最后一英里正确称为“送货体验”）是 TSP 如此重要的另一个重要原因。

四、旅行商问题的可能解决方案

实际上，有整本书都在尝试解决 TSP 问题，因此需要注意的是，我们下面列出的是“可能”的解决方案，而不是“实际的解决方案”。TSP 是所谓的“NP 难”问题，这意味着实际上没有已知的解决方案。

然而，针对该问题的一些更值得注意或更实际的答案如下：

4.1.“暴力”检查

旅行商问题 (TSP) 的问题在于，从技术上讲，它是可以解决的。你只需要计算出可以为多个站点提供服务的所有可能顺序。对吗？

嗯，当然，但可能的路线数量增长如此之快，以至于即使是最强大的现代算法计算机也无法完成这项任务。为 10 个站点创建优化路线的问题不是问题本身，而是快速创建路线。

好吧，这就是蛮力法的尝试，或者也称为“天真方法”。它计算所有可能的排列，找到最短的可能排列，然后选择实际上最短的路线。

4.2. 分支限界法

分支定界方法注重寻找剩余路径的最低可能成本，这些路径是强力方法等初始阶段提供的。

有时也称为并行 TSP，它假设我们不想尝试每一条“可能”的路线。即使使用常识，也可能会将范围缩小一些。例如，我们不会先去最远的下车点，然后再返回离仓库最近的下车点。通过使用节点并为每个节点附加“成本”，该算法可以估算给定选择导致问题解决方案的可能性。

4.3.最近邻法

使用最近邻方法时，算法从路线的起始位置开始，然后添加最接近该位置的站点。已访问的站点列表已提供服务，如果某个站点已提供服务，则跳过该站点并添加下一个站点。到达最后一个站点后，您将再次返回起始位置。

最近邻法的优点是执行速度相对较快，而且比上述其他两种方法更实用。然而，缺点是它在提供优化路线方面并不总是像其他两种方法那样准确。

五、如何切实解决旅行商问题

好吧，如果你已经读到这里，你就会知道这个答案从字面意义上来说是无法解决的，但从实际意义上来说，它是无法解决的！

虽然算法可能无法每次都为您提供最快或最便宜的路线，但它们的效率远高于人脑。正如我们在最近邻方法中看到的那样，可以利用计算能力自动消除大部分显然效率不高的路线。此外，同样的计算机还可以从剩余的选项中选择哪条路线最快（或者从数学角度来说成本最低）。

随着技术的进步，机器学习和自动化变得比以往任何时候都更加强大，路线规划和优化可以在几秒钟内完成。基本上有两个过程是完整的：数学方程和最佳路线的自动选择。这对公路运输行业来说是一个巨大的改变，特别是近年来大量包装货物以较少数量进行配送。

六、SmartRoutes 如何解决旅行商问题

SmartRoutes 是所谓的配送管理软件。作为一套完整的配送软件解决方案，它可以帮助企业管理从订单管理和履行到配送司机路线规划以及为最终客户获取配送证明等所有事务。

然而，解决方案的核心是路线优化。这意味着我们在开发解决方案时有一个明确的总体目标：

在技​​术允许的范围内尽快创建最快捷、最有效的公路货物运输路线。

正如我们所讨论的，旅行商问题并没有一劳永逸的解决方案。但在 SmartRoutes，我们采用了被认为是最佳的方法，添加了最佳技术，然后开始考虑在送货车辆送货过程中发挥作用的所有其他因素。

其中最明显的因素包括车队规模、道路类型、实时驾驶员分析，以及根据现场测试，停车间隔时间或停车间隔距离是否是更好的效率指标。

然而，我们在自己的算法中也考虑了一些不太明显的因素。例如，对于美国和英国的用户，我们的算法会优先选择右转次数较少的路线。

为什么？因为在运送大量货物时，穿越交通确实很浪费时间。通过左转，司机不必等待对面的车辆通过即可继续行驶。当然，这对司机来说也更安全，这也是我们在路线算法中采用这种方式的另一个原因。