algorithm - 启发式地解决有额外约束的旅行推销员的想法

Question

我正试图提出一个快速而合理的优化算法来解决以下TSP/哈密顿路径问题：
送货车上有许多取货和卸货需要
执行：
每次送货，都要在
下车。
车很小，包裹大小不一。
总运载量不能超过某个上限（例如1立方
米）。每次交货都有最后期限。
计划者可以在中途行驶，因此车辆将从一些已完成的作业和一些已完成的容量开始。
一个接近最优的解决方案应该最小化每个航路点之间的总成本（为简单起见，距离）如果一个解决方案不存在，因为时间限制，我需要找到一个解决方案，有最少数量的后期交付。示例问题和非最优但有效的解决方案的一些示例：
我目前正在使用贪婪的最佳第一次搜索，回溯范围为100个分支。如果它找不到准时交货的解决方案，我会在一秒钟内随机生成尽可能多的（我能抽出的最多计算时间）并选择延迟交货次数最少的一个。我已经研究过线性规划，但是我无法理解它，而且我认为它是不合适的，因为它需要经常运行。我也尝试过需要改变巡更的算法，但问题是，由于容量限制和优先级，改变巡更几乎总是使其无效。有人能想出更好的启发式方法来解决这个问题吗非常感谢！

Answer 1

安全移动
这里有一些关于安全地改变现有可行解决方案的想法：
如果两个站点都是取货站，或者都是送货站，则任何两个连续的站点都可以交换。显然，对于“两次送货”的情况是这样的；对于“两次送货”的情况是这样的：如果你有空间取A，那么在两次送货之间没有任何东西的情况下取B，那么你有空间先取B，然后再取A。（事实上，一个更普遍的规则是可能的：在任何纯送货或连续停站的纯送货序列中，停止可以任意重新排列。但是列举所有的可能性对于长序列来说可能会变得非常困难，而且您应该能够通过考虑成对来获得最大的好处。）
如果A的最初取货是在B被取货之后，而A自己的交货是在B的最初交货之后，那么A的取货可以与其他B的任何后续交货交换。在特殊情况下，A的取货紧接着B的交货，它们总是可以互换的。
如果在交付尺寸为D的物品之后，又取回尺寸为P的物品，那么只要有足够的额外空间，就可以交换这些物品：具体地说，只要F>=P，其中F是交付前可用的空闲空间。（我们已经知道f+d>=p，否则原始计划将不可行——这是一个寻找小规模交付应用此规则的提示。）
如果你是从纯粹随机产生的时间表开始，那么简单地尝试所有可能的行动，贪婪地选择最好的，应用它，然后重复，直到没有更多的行动产生改善，应该会给你一个大质量的促进！
评分解决方案
这是非常有用的，有一种方法来评分一个解决方案，以便他们可以订购。分数的好处是很容易包含重要性级别：正如两位数的第一个数字比第二个数字更重要一样，您可以设计分数，使更重要的事情（如违反截止日期）比不重要的事情（如总旅行时间或距离）获得更大的权重。我建议你做些类似于1000 * num_deadline_violations + total_travel_time的事情。（当然，这是假设总旅行时间单位将保持在1000以下）然后我们会尽量减少这一点。
管理解决方案
我建议使用存储在amin-heap中的k个解决方案池（比如k=10000），而不是采用一个解决方案并尝试上面所有可能的操作。这允许您在o（log k）时间内提取池中的最佳解决方案，同时插入新的解决方案。
最初，您可以用随机生成的可行解决方案填充池；然后，在每个步骤中，您将提取池中的最佳解决方案，尝试对其进行所有可能的操作以生成子解决方案，并将任何比其父解决方案更好的子解决方案插入池中。每当池的大小加倍时，拿出第一个（即最好的）k解决方案，并用它们创建一个新的最小堆，丢弃旧的。（在堆增长到其原始大小的常数倍数之后，执行此步骤具有良好的属性，使未经修正的时间复杂度保持不变）。
可能发生的情况是，对解决方案X的某些移动会生成已在池中的子解决方案Y。这会浪费内存，这是不幸的，但是min heap方法的一个很好的特性是，当这些副本到达堆的前面时，您至少可以廉价地处理它们：所有的副本都有相同的分数，因此它们在从堆的顶部提取解决方案时都会连续出现。因此，为了避免让重复的解决方案在“下一代”中生成重复的子级，只需检查新的堆顶与刚刚提取的解决方案是否不同，并继续提取和丢弃解决方案，直到找到为止。
关于保留更差的解决方案的说明：看起来保留子解决方案是值得的，即使子解决方案比父解决方案差一点，而且这可能是有用的（甚至是找到绝对最优解决方案所必需的）。但这样做有一个令人讨厌的后果：它意味着有可能从一个解决方案循环到它的孩子，然后再循环（或者可能是更长的循环）。这会浪费我们已经访问过的解决方案的CPU时间。