具有额外约束条件的旅行商问题的启发式解决方案思路

Question

我正在尝试提出一种快速且相对最优的算法来解决以下TSP /汉密尔顿路径类问题：

一个交货车需要执行多个装卸货物的任务：

每次交货时，取件必须在放件之前发生。

该车体积较小，包裹大小各异。总载重不能超过某个上限（例如1立方米）。每次交货都有截止日期。

规划师可以在途中运行，因此车辆将从已拾取的许多作业和已占用的一些挂载空间开始。

近似最优的解决方案应当将每个路标之间的总成本（为简单起见，距离）最小化。如果由于时间限制而不存在解决方案，则需要找到具有最少延迟交货的解决方案。这是一个例子问题和非最优但有效的解决方案的一些说明：

我目前正在使用贪心最佳优先搜索，限制回溯到100个分支。如果它无法找到及时交货的解决方案，我会在一秒钟内随机生成尽可能多的解决方案，并选择延迟交货最少的方案。我尝试了线性规划，但无法理解它 - 而且我认为它不适用于频繁运行的需求。我还尝试了需要变异巡游的算法，但问题是变异巡游几乎总是由于容量限制和优先级而使其无效。有没有人能想到更好的启发式方法来解决这个问题？非常感谢！

- drspa44

---

为什么有1秒限制？这是实际问题（实际交付计划或至少是某个实时游戏）还是理论问题（分配或竞赛）？ - Dialecticus

此外，表格中的数字似乎与图形不对应。假设蓝点是当前位置，向上箭头是取货点，向下箭头是交货点，则只应该有一个距离最近的交货点更近的取货点（5.764公里），但实际上有7个。 - Dialecticus

感谢您的回复。这是一个本科项目模拟，需要在几周的模拟时间内运行。由于交通状况不断变化，每5分钟需要重新规划。直接路线列有点误导，我应该将其裁剪掉。它是从接送点到目的地节点的路线。 - drspa44

不错的问题。问题是：是否存在一种可能的情况，其中规划额外行程更便宜？ - wildplasser

Answer 1

安全移动

以下是一些关于如何安全地变异一个现有的可行解决方案的想法：

1. 如果两个连续的停靠点都是取货点或者都是配送点，那么它们总是可以交换的。对于“都是配送点”的情况显然是正确的；对于“都是取货点”的情况：如果你有足够的空间来取货 A，然后在中间没有交付任何东西就取货 B，那么你就有足够的空间先取 B，然后再取 A。 （实际上还可能存在更一般的规则：在任何纯配送或纯取货序列中，连续的停靠点都可以任意重新排列。但是对于长序列枚举所有可能会变得很困难，只考虑成对的停靠点也应该能够获得大部分的好处。）
2. 如果 A 的取货时间在 B 被取货之后，而 A 的交付时间在 B 的原始交付时间之后，那么 A 的取货可以与任何后来的其他物品 B 的交付 交换位置，前提是 A 原来的取货时间在 B 之后。特殊情况是，如果 A 的取货紧接着 B 的交付，它们总是可以交换位置。
3. 如果有一件大小为 d 的物品的交付后跟着一件大小为 p 的物品的取货，则它们可以交换位置，前提是有足够的额外空间：具体来说，前面的空闲空间 f >= p，其中 f 是交付前可用的自由空间。（我们已经知道 f + d >= p，否则原始计划就不可行——这是一个提示，要寻找适用于小交付的规则。）

如果你从完全随机生成的计划开始，那么简单地尝试所有可能的变化，贪婪地选择最好的，应用它，然后重复直到没有更多的移动可以改善，应该会大大提高质量！

评分解决方案

有一种方法可以对解决方案进行评分，以便对它们进行排序，这非常有用。评分的好处在于它很容易融入重要性级别：就像两位数的第一位比第二位更重要一样，您可以设计评分，使更重要的事情（例如违反期限）比不那么重要的事情（例如总旅行时间或距离）获得更大的权重。我建议使用类似于 1000 * num_deadline_violations + total_travel_time 这样的评分。（当然，这假设总旅行时间的单位将保持在 1000 以下。）我们将尝试最小化这个值。

管理解决方案

与其将一个解决方案并尝试所有上述可能的移动，我建议使用存储在最小堆中的 k 个解决方案（例如，k = 10000）的池。这允许您在 O(log k) 时间内提取池中的最佳解决方案，并以相同的时间插入新解决方案。

您可以首先使用随机生成的可行解填充池; 然后在每个步骤中，您将从池中提取最佳解，在其上尝试所有可能的操作以生成子解，并将任何优于其父级的子解插入回池中。每当池大小加倍时，请将前k个解（即最佳解）取出并用它们创建一个新的小根堆，丢弃旧的解。（这样做可以保持摊销时间复杂度不变，因为堆增长到常数倍数的大小后执行此步骤具有良好的性质。）

可能发生的情况是对解决方案X进行某些移动产生了子解Y，该子解已经在池中。这会浪费内存，这很不幸，但小根堆方法的一个好处是，当重复出现在堆顶部时，可以至少廉价地处理这些重复：所有重复都具有相同的分数，因此当从堆的顶部提取解时，它们将全部连续出现。因此，为了避免重复的解产生重复的孩子“通过几代”，只需检查新的堆顶部是否与刚提取的解不同，然后继续提取和丢弃解，直到满足条件为止。

关于保留较差解的说明：保留子解即使它们比其父级稍微差一些可能是有价值的（甚至可能必要以找到绝对最佳解），但这样做会产生一个不好的后果：它意味着可能从一个解到其子解并再次返回（或可能更长）。这会浪费我们已经访问过的解的CPU时间。

- j_random_hacker

---

谢谢。我明天会试一下的。 :) - drspa44

Answer 2

你基本上是将背包问题与旅行商问题结合起来。

你的主要问题似乎实际上是背包问题，而不是旅行商问题，因为它有一个硬性限制（最大交付量）。也许尝试将背包问题的解决方案与旅行商结合起来。

如果你真的只有一秒钟的计算时间，那么回溯贪心算法可能是你能得到的最佳解决方案之一。

- Dakkaron

---

我想使用某种贪心算法，但是由于n！个分支的无限回溯是不切实际的，并且从经验上看，如果主分支失败，它的100个邻居也会失败，因为只有最后几个点被重新排列。 - drspa44

基本上，你被困在局部最大值中，没有能力（时间上）走出来。你可以尝试的是，如果你被困在局部最大值上，不要试图回溯，而是从一个随机的新解决方案开始。贪心地重复这个过程，直到你有时间为止。在时间结束时输出你找到的最佳解决方案。 - Dakkaron