旅行售货员将折旧的物品运往不同市场

Question

5

什么样的启发式方法可以用来解决以下挑战？

Quality Blimps Inc.希望将销售扩展到其他城市（N），因此他们聘请您作为销售员飞往其他城市销售飞艇。飞艇的旅行费用可能很昂贵，因此您需要确定每次旅行携带多少个飞艇，并在何时返回总部获取更多飞艇。Quality Blimps拥有无限的飞艇供应。

您只能在访问的每个城市中销售一架飞艇，但您不需要访问每个城市，因为有些城市的旅行成本很高。每个城市都有初始价格，但随着销售数量的增加（和新奇感的消失），价格会下降一定百分比。找到一条好路线以最大化利润。

这个挑战类似于标准的旅行商问题，但有一些额外的变化：推销员需要跟踪他自己的旅行成本和飞艇的成本。每个城市的售价不同，但是这些价格会随着旅行而下降。有什么快速算法（即n log n）可以用来最大化利润？

以运输物品的价格方式使TSP更简单。如果推销员在A市，并想去B市，他可以比较直接去B市的成本与先返回总部取更多的飞艇的成本。即通过A市额外带一个飞艇到B市是否更便宜，还是在中间返回。这个检查将创建一系列循环旅行，推销员可以按最高收入的顺序进行。但是，确定这些循环的好方法是什么？

- Ari

1

@amit，如果P=NP，则TSP问题的O（nlogn）解决方案将让每个人都感到尴尬。 - Shahbaz

@Shahbaz，你只能在一个城市销售一台设备，因此你不能两次返回同一个城市。 - Ari

@amit，这只是一个大概的解决方案，我认为它需要在给定的时间内小于O(n^2)才能完成。 - Ari

@Ari，问题描述中将移动气球的成本（0.2-0.4）设定为推销员移动的成本（1.0）的较低值。因此，只要角BAC<90，同时访问两个目的地（其中A是起点，B是第一个目的地，C是第二个目的地）就应该是最优的。90度阈值是下限。 - ElKamina

@ElKamina，它是0.2 ≤ C ≤ 4。也就是说，气球可以比人的成本高出4倍。 - Ari

显示剩余2条评论

4个回答

3

这是一个搜索问题。假设网络比暴力破解还要庞大，最好的算法将是蒙特卡洛树搜索。

- Tyler Durden

0

我已经阅读了原始问题。由于城市数量很大，无法得到精确答案。近似算法是唯一的选择。正如@maniek所提到的，有许多AA的选择。如果您以前有AA的经验，那就最好了，您可以选择其中一个您熟悉的并获得近似答案。但是，如果您以前没有做过AA，也许您可以从带修剪的回溯开始。

至于这个问题，您可以轻松地获得以下修剪规则：

您甚至可以先应用KNN将几个位于附近的城市聚类。然后从总部开始，访问每个组。

总之，这确实是一个开放性问题。没有“最佳答案”。也许在情况1中，使用回溯法可以得到最佳答案，而在情况2中，模拟退火是最好的选择。只要计算出近似答案就足够了，而且有很多方法可以实现这个目标。总之，真正的“最佳方法”是尽可能多地编写AAs，然后比较这些结果并输出最佳结果。

- songlj

0

这看起来像是一个经典的优化问题，我知道可以用模拟退火算法来处理它（在上世纪80年代，我曾参与过模拟退火算法的商业应用，即Wintek电子CAD自动布局程序）。大多数优化算法都可以处理像你这样的多变量问题——问题在于正确设置适应度算法，以便获得最佳解决方案（在你的情况下，是最低成本）。

其他优化算法也值得一试——我只有实现模拟退火算法的经验。

（如果你选择使用模拟退火算法，你可能需要获取《模拟退火：理论和应用（数学及其应用）》一书，作者为P.J. van Laarhoven和E.H. Aarts，但你需要找到它，因为它已经绝版了（甚至可能是我在上世纪80年代使用的那本书）。）

- Mark Leighton Fisher

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- maniek · Accepted Answer

这类问题的算法通常是“多次运行解决方案，选择最佳解”的类型。此外，在选择下一个解决方案时，使用先前迭代的结果。

至于具体的算法，可以尝试使用剪枝回溯、模拟退火、禁忌搜索、遗传算法、神经网络（按相关性排序）。另外，Tyler Durden提出的蒙特卡罗树搜索思想看起来很酷。