优化旅行计划规划

Question

我有一个问题需要解决。

问题陈述：

我有一组大约5000个带有地理坐标的商店。每个商店都必须被访问一次，以收集订单收据。

这将由推销员完成。

我想生成N个优化的旅行计划，使得每个推销员能够在8小时内覆盖最多的商店。

即在旅行计划中，访问所有商店所需的时间不应超过8个小时。

而且，没有两个推销员应该访问同一个商店。

也就是说，一旦商店被访问，就不应在另一个旅行计划中再次访问。

在这种情况下，生成的旅行计划数量间接等于所需的推销员数量。

需要的最终结果：

最小化覆盖所有商店所需的旅行计划数量

我的资料：

商店之间的距离矩阵。其中包含每个商店之间覆盖的距离和所需的时间。

挑战： 我没有任何有关推销员的信息（即我没有他们的地理位置），这使得为每个旅行计划选择起点变得困难。

我的初步想法：

我正在考虑通过聚类将商店分成不同的区域，然后为每个区域形成旅行计划（以获得最优路径）。

我将使用Python开发此应用程序。

对于这种类型的问题，有什么最好的尝试和进行的方法吗？

- Shubham R

---

当销售员完成一次旅行计划时，他的下一个旅行计划是否有任何限制？或者我们可以在地图上的任何地方安排他的下一个旅行吗？此外，是否应考虑拜访商店的时间？ - SaiBot

@SaiBot 我在这里考虑一个销售员只会访问一个旅程计划。也就是说，生成的旅程计划数量等于销售员数量。因此，我们可以从任何地方开始下一个旅程计划。 - Shubham R

@SaiBot 没有特定的时间去商店。 - Shubham R

啊，抱歉，我没听清楚。你的问题中已经很好地解释了。 - SaiBot

这不是多旅行商问题（mTSP）的一个实例吗？ - גלעד ברקן

Answer 1

这是一个启发式的想法：

1. 每个商店都有一个销售员。每个销售员存储其覆盖路径（例如商店ID列表），该路径仅以其初始商店为起点，并且他们的初始时间为0。
2. 选择两个商店之间最短的未覆盖链接，s1和s2，其时间成本为t。
3. 查找一对销售员a1和a2，使得他们的路径始于s1和s2或者结束于s1和s2。如果找不到这样的一对销售员（因为商店已经在现有路径中间，或者s1和s2是一个销售员路径的起点和终点），则放弃该链接并返回步骤2。
4. 让t_sum为a1花费的时间、a2花费的时间和t的总和。如果t_sum小于每个销售员可以花费的最大时间T（8小时），则放弃该链接并返回步骤2。
5. 将a1和a2合并为单个销售员。这个过程根据具体情况有所不同，但应该相当简单。例如，如果a1在s1结束，a2在s2开始，则可以将它们的路径连接起来，但是如果a1在s1开始，a2也在s2开始，则必须（例如）反转a1的路径，然后将它们连接起来。新的销售员花费的时间为t_sum。
6. 返回步骤2并重复，直到没有未探索的链接为止。

这是基本思路。有些空间可以决定使用什么数据结构，影响你如何查找下一个最短的链接，如何查找 a1 和 a2 以及如何跟踪已覆盖/丢弃的链接。还有一些可以包括的改进或优化：

当你合并 a1 和 a2 时，除非它们是路径中唯一的元素，否则可以丢弃所有指向 s1 和 s2 的链接。例如，如果我正在查看商店 1 和 2 之间的链接，并且我正在合并路径 [1, 3, 4] 和 [2]（结果为 [2, 1, 3, 4] 或 [4, 3, 1, 2]），我可以删除商店 1 的所有剩余链接，因为现在它位于路径中间，但不能从 2 中删除，因为它仍然处于合并路径的一端，因此可以连接。

当你合并 a1 和 a2 时，如果 T - t_sum < t，那么这个销售员将不可能再被进一步合并（因为每个剩余链接的成本至少为 t），因此你可以“关闭”路径，意味着你可以丢弃每端的链接，并且如果这可以节省时间（取决于确切的实现），你可以在下一次执行步骤 3 时跳过 a1 和 a2。

事实上，如果图形非常密集，你可以在每次迭代或每隔几次迭代时节省时间，检查当前“活动”代理中任何一个的剩余时间与 T 的差异是否小于上一个值 t，如果是，则“关闭”它。

编辑：

这里有一个Python的概念证明。我避免使用NumPy或任何其他外部包，尽管由于算法大多是迭代的，我不确定你能否使它更快。

def make_journeys(dists, max_dist):
    n = len(dists)
    ds = sorted((dists[i][j], i, j) for i in range(n) for j in range(i + 1, n))
    starts = list(range(n))
    ends = list(range(n))
    salesmen = [([i], 0) for i in range(n)]
    for d, i, j in ds:
        if starts[i] is not None and starts[j] is not None:
            si, sj = starts[i], starts[j]
            reverse_i, reverse_j = True, False
        elif starts[i] is not None and ends[j] is not None:
            si, sj = starts[i], ends[j]
            reverse_i, reverse_j = True, True
        elif ends[i] is not None and starts[j] is not None:
            si, sj = ends[i], starts[j]
            reverse_i, reverse_j = False, False
        elif ends[i] is not None and ends[j] is not None:
            si, sj = ends[i], ends[j]
            reverse_i, reverse_j = False, True
        else:
            continue
        if si == sj:
            continue
        (pi, di) = salesmen[si]
        (pj, dj) = salesmen[sj]
        dt = d + di + dj
        if dt > max_dist:
            continue
        starts[pi[0]] = None
        ends[pi[-1]] = None
        starts[pj[0]] = None
        ends[pj[-1]] = None
        if reverse_i:
            pi = list(reversed(pi))
        if reverse_j:
            pj = list(reversed(pj))
        pt = pi + pj
        starts[pt[0]] = si
        ends[pt[-1]] = si
        salesmen[si] = (pt, dt)
        salesmen[sj] = None
    return [s for s in salesmen if s]

该函数返回一个元组列表，其中包含存储ID的路径和旅程的总时间。以下是一个测试：

def random_symmetric(N, min, max):
    # Build a random symmetric matrix
    dists = [[random.randint(1, 9) if i != j else 0 for j in range(N)] for i in range(N)]
    return [[(dists[i][j] + dists[j][i]) // 2 for j in range(N)] for i in range(N)]

random.seed(100)

# This takes long!
distances = random_symmetric(5000, 1, 9)
max_distance = 100

journeys = make_journeys(distances, max_distance)
print('{} journeys computed.'.format(len(journeys)))

输出：

50 journeys computed.

在上面的测试中，生成随机距离矩阵需要相当长的时间（如果使用NumPy会快得多）。在我的电脑上，调用make_journeys花费了约16秒。显然，你的情况可能不同，但它不会运行数小时或数分钟。

- jdehesa