办公室访问顾客最短路径问题解析：从3个到48个顾客的访问路径计算

aizixun8

如图1所示，从办公室（红框）出发，拜访三个客户（黑点），然后返回办公室，最短访问路径是多少？

图 1. 三个客户

图 2. 三个客户（最短路径）

这个问题的答案（如图2所示）并不难获得。如果三个客户分别为A、B、C，则有6种可能的访问路径：ABC、ACB、BAC、BCA、CAB、CBA。计算每条访问路径的长度并选择最短的一条。

如果需要访问6个客户，有多少种可能的访问路径？答案是720。

如果您需要拜访 12 位客户怎么办？答案是479,001,600！

如果您需要访问 24 个客户怎么办？答案是620,448,401,733,239,000,000,000！

如果需要拜访 48 个客户怎么办？答案是（1.2414

图 3 和图 4 显示了分别需要采访 15 名客户的示例和答案。你能尝试去做吗？

图 3. 15 个客户

图 4. 15 个客户（最短路径）

在运筹学中，这个问题被称为旅行商问题（ ），广泛应用于物流运输管理领域。例如：据中国物流与采购联合会统计，2017年，56%的配送人员每天配送超过80个包裹（相当于拜访80多个客户）。在美国，每个 UPS 司机平均每天递送 140-160 个包裹（2015 年）。旅行商问题有很多变体。例如，如果某些客户只允许在某个时间窗口内发货（京东的精准度），那么路线的选择就需要从空间和时间两个维度来考虑。

在实际应用中，设计算法解决上述问题时，需要考虑很多因素，例如：1）电子地图的准确性； 2）路径是否符合驾驶员的驾驶习惯（如图5）； 3）路径求解速度是否足够快；为此，UPS花费近3亿美元、10年时间完成了一个名为ORION（On Road and）的项目，分析其在美国小包裹投递业务中55,000名司机的“最后一英里”。取货/递送业务的优化取得了显著成效，每年为 UPS 节省 300-4 亿美元的成本和 1.6 亿公里的车辆行驶距离（等，2017）。

图 5. 避免频繁交叉路口的路径 (, 2016)

UPS ORION项目的成功充分展示了国际先进物流企业如何将运筹学方法与现代计算技术和企业业务实践相结合，从而为企业带来巨大的经济效益。

参考：

，C.，J.李维斯，R.，B.，J.。 2017 年。UPS。 47(1)8-23。