启发式解决带有额外约束的旅行商的想法
Ideas for heuristically solving travelling salesman with extra constraints
我正在尝试提出一种快速且合理的最佳算法来解决以下 TSP/hamiltonian-path-like 问题：
一辆送货车辆需要进行多次接送
执行：
对于每次派送，取件需要在
下车。
车辆很小，包裹大小不一。
总运输量不能超过某个上限（例如 1 立方
仪表）。每次交付都有截止日期。
计划者可以 运行 中途，因此车辆将在开始时已经完成一些工作并且已经占用了一些容量。
接近最优的解决方案应该最小化每个航路点之间的总成本（为简单起见，距离）。如果由于时间限制不存在解决方案，我需要找到延迟交付次数最少的解决方案。示例问题和非最佳但有效解决方案的一些说明：
我目前正在使用回溯限制为 100 个分支的贪婪最佳优先搜索。如果找不到准时交货的解决方案，我会在一秒钟内（我可以节省最多的计算时间）随机生成尽可能多的解决方案，并选择延迟交货次数最少的解决方案。我已经研究过线性规划，但无法理解它 - 而且我认为它不合适，因为它需要非常频繁地 运行。我也尝试过需要改变游览的算法，但问题是由于容量限制和优先级，改变游览几乎总是使其无效。谁能想出更好的启发式方法来解决这个问题？非常感谢！
您基本上是将背包问题与旅行商问题结合起来。
你这里的主要问题似乎实际上是背包问题，而不是旅行商问题，因为它有一个硬限制（最大交货量）。也许尝试将背包问题的解决方案与旅行商结合起来。
如果您真的只有一秒的最大时间用于计算，那么带有回溯的贪婪算法实际上可能是您可以获得的最佳解决方案之一。
安全移动
这里有一些安全改变现有可行解决方案的想法：
- 任何两个连续的停靠点如果都是取件或都是送货，则始终可以互换。 "both deliveries" 的情况显然是这样；对于 "both pickups" 的情况：如果你有空间拿起 A，然后拿起 B 而中间没有交付任何东西，那么你就有空间先拿起 B，然后再拿起 A。（实际上是一个更一般的规则是可能的：在任何 pure-delivery 或 pure-pickup 连续停靠点序列中，停靠点可以任意重新排列。但是对于长序列来说，枚举所有可能性可能变得令人望而却步，你应该能够获得大部分只考虑成对受益。）
- A 的提货可以与 其他东西B 的任何稍后交付交换，前提是 A 的原始提货在 B 被提货之后，并且 A 自己的交付在 B 的之后原装发货。在 A 的提货紧接着 B 的交付的特殊情况下，它们总是可以交换。
- 如果先交付一件尺寸为 d 的物品，然后取件为尺寸为 p 的物品，那么只要有足够的额外空间，就可以交换它们：具体来说，前提是 f >= p，其中f 是发货前可用的免费space。 （我们已经知道 f + d >= p，否则原始计划将不可行——这是寻找小交付以应用此规则的提示。）
如果您从纯随机生成的时间表开始，那么只需尝试所有可能的动作，贪婪地选择最好的，应用它然后重复直到没有更多动作产生改进应该会给您带来很大的质量提升！
评分解决方案
有一种对解决方案进行评分的方法非常有用，这样就可以对它们进行排序。分数的好处在于它很容易包含重要性级别：正如 two-digit 数字的第一位数字比第二位数字更重要一样，您可以设计分数以便更重要的事情（例如截止日期）违规）比不太重要的事情（例如总旅行时间或距离）获得更大的权重。我会建议像 1000 * num_deadline_violations + total_travel_time 这样的东西。 （这当然假设 total_travel_time 的单位将保持在 1000 以下。）然后我们会尝试将其最小化。
管理解决方案
我建议使用 池 的 k 个解决方案（例如，k = 10000）存储在min-heap。这允许您在 O(log k) 时间内提取池中的最佳解决方案，并同时插入新的解决方案。
您最初可以使用随机生成的可行解决方案来填充池；然后在每一步中，您将提取池中的最佳解决方案，尝试对其进行所有可能的移动以生成 child 解决方案，并插入任何 child 解决方案都比他们parent回池。每当池的大小增加一倍时，取出第一个（即最好的）k 个解决方案并用它们制作一个新的 min-heap，丢弃旧的。 （在堆增长到其原始大小的常量 倍数 之后执行此步骤，这样可以很好地 属性 保持摊销时间复杂度不变。）
解决方案 X 的某些移动可能会产生 child 解决方案 Y，该解决方案 Y 已经在池中。这会浪费内存，这是不幸的，但是 min-heap 方法的一个好处 属性 是，当它们到达堆的前端时，您至少可以廉价地处理这些重复项：所有重复项都将具有相同的分数, 所以在从堆顶抽取解的时候都会连续出现。因此，为了避免重复的解决方案生成重复的 children "down through the generations"，只需检查新的堆顶是否与 just-extracted 解决方案不同，并继续提取和丢弃解决方案，直到这个持有。
关于保留较差解决方案的注意事项：似乎值得保留 child 解决方案，即使它们比 parent 稍差，实际上这可能是有用的（甚至是找到绝对最优解所必需的），但这样做会带来令人讨厌的后果：这意味着可以 循环 从一个解决方案到它的 child 并再次返回（或可能是更长的周期）。这在我们已经访问过的解决方案上浪费了 CPU 时间。
我正在尝试提出一种快速且合理的最佳算法来解决以下 TSP/hamiltonian-path-like 问题：
一辆送货车辆需要进行多次接送 执行：
对于每次派送，取件需要在 下车。
车辆很小，包裹大小不一。 总运输量不能超过某个上限（例如 1 立方 仪表）。每次交付都有截止日期。
计划者可以 运行 中途，因此车辆将在开始时已经完成一些工作并且已经占用了一些容量。
接近最优的解决方案应该最小化每个航路点之间的总成本（为简单起见，距离）。如果由于时间限制不存在解决方案，我需要找到延迟交付次数最少的解决方案。示例问题和非最佳但有效解决方案的一些说明：
我目前正在使用回溯限制为 100 个分支的贪婪最佳优先搜索。如果找不到准时交货的解决方案，我会在一秒钟内（我可以节省最多的计算时间）随机生成尽可能多的解决方案，并选择延迟交货次数最少的解决方案。我已经研究过线性规划，但无法理解它 - 而且我认为它不合适，因为它需要非常频繁地 运行。我也尝试过需要改变游览的算法，但问题是由于容量限制和优先级，改变游览几乎总是使其无效。谁能想出更好的启发式方法来解决这个问题？非常感谢！
您基本上是将背包问题与旅行商问题结合起来。
你这里的主要问题似乎实际上是背包问题，而不是旅行商问题，因为它有一个硬限制（最大交货量）。也许尝试将背包问题的解决方案与旅行商结合起来。
如果您真的只有一秒的最大时间用于计算，那么带有回溯的贪婪算法实际上可能是您可以获得的最佳解决方案之一。
安全移动
这里有一些安全改变现有可行解决方案的想法：
- 任何两个连续的停靠点如果都是取件或都是送货，则始终可以互换。 "both deliveries" 的情况显然是这样；对于 "both pickups" 的情况：如果你有空间拿起 A，然后拿起 B 而中间没有交付任何东西，那么你就有空间先拿起 B，然后再拿起 A。（实际上是一个更一般的规则是可能的：在任何 pure-delivery 或 pure-pickup 连续停靠点序列中，停靠点可以任意重新排列。但是对于长序列来说，枚举所有可能性可能变得令人望而却步，你应该能够获得大部分只考虑成对受益。）
- A 的提货可以与 其他东西B 的任何稍后交付交换，前提是 A 的原始提货在 B 被提货之后，并且 A 自己的交付在 B 的之后原装发货。在 A 的提货紧接着 B 的交付的特殊情况下，它们总是可以交换。
- 如果先交付一件尺寸为 d 的物品，然后取件为尺寸为 p 的物品，那么只要有足够的额外空间，就可以交换它们：具体来说，前提是 f >= p，其中f 是发货前可用的免费space。 （我们已经知道 f + d >= p，否则原始计划将不可行——这是寻找小交付以应用此规则的提示。）
如果您从纯随机生成的时间表开始，那么只需尝试所有可能的动作，贪婪地选择最好的，应用它然后重复直到没有更多动作产生改进应该会给您带来很大的质量提升！
评分解决方案
有一种对解决方案进行评分的方法非常有用，这样就可以对它们进行排序。分数的好处在于它很容易包含重要性级别：正如 two-digit 数字的第一位数字比第二位数字更重要一样，您可以设计分数以便更重要的事情（例如截止日期）违规）比不太重要的事情（例如总旅行时间或距离）获得更大的权重。我会建议像 1000 * num_deadline_violations + total_travel_time 这样的东西。 （这当然假设 total_travel_time 的单位将保持在 1000 以下。）然后我们会尝试将其最小化。
管理解决方案
我建议使用 池 的 k 个解决方案（例如，k = 10000）存储在min-heap。这允许您在 O(log k) 时间内提取池中的最佳解决方案，并同时插入新的解决方案。
您最初可以使用随机生成的可行解决方案来填充池；然后在每一步中，您将提取池中的最佳解决方案，尝试对其进行所有可能的移动以生成 child 解决方案，并插入任何 child 解决方案都比他们parent回池。每当池的大小增加一倍时，取出第一个（即最好的）k 个解决方案并用它们制作一个新的 min-heap，丢弃旧的。 （在堆增长到其原始大小的常量 倍数 之后执行此步骤，这样可以很好地 属性 保持摊销时间复杂度不变。）
解决方案 X 的某些移动可能会产生 child 解决方案 Y，该解决方案 Y 已经在池中。这会浪费内存，这是不幸的，但是 min-heap 方法的一个好处 属性 是，当它们到达堆的前端时，您至少可以廉价地处理这些重复项：所有重复项都将具有相同的分数, 所以在从堆顶抽取解的时候都会连续出现。因此，为了避免重复的解决方案生成重复的 children "down through the generations"，只需检查新的堆顶是否与 just-extracted 解决方案不同，并继续提取和丢弃解决方案，直到这个持有。
关于保留较差解决方案的注意事项：似乎值得保留 child 解决方案，即使它们比 parent 稍差，实际上这可能是有用的（甚至是找到绝对最优解所必需的），但这样做会带来令人讨厌的后果：这意味着可以 循环 从一个解决方案到它的 child 并再次返回（或可能是更长的周期）。这在我们已经访问过的解决方案上浪费了 CPU 时间。