algorithm - 优化旅程计划规划

Question

我有一个问题要解决。

问题陈述:

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

这将由销售人员完成。

我想生成 N 个优化的旅程计划，这样每个销售人员都能覆盖最多 no. 8 小时内的商店。

即在旅程计划中，参观所有商店所花费的时间不应超过 8 小时。

并且任何两个推销员都不应访问同一家商店。

即在另一个旅程计划中不应再次访问一家商店。

在这种情况下，No. of journey plans generated 间接等于 no。需要销售人员。

需要最终结果:

尽量减少编号。覆盖所有门店的行程计划

我有什么:

商店到商店的距离矩阵。每个商店之间都有距离和时间

挑战:我没有关于推销员的任何信息(即我没有他们的地理位置)，因此很难为每个旅程计划选择起点。

我的初步想法:

我想通过聚类的方式把门店划分到不同的区域。然后为每个集群制定旅程计划(优化路线)。

我将在 python 中开发它。

关于什么是尝试和处理此类问题的最佳方法的任何想法。

Answer 1

这里有一个启发式的想法:

1. 从每家商店一名推销员开始。每个销售员都存储覆盖路径(例如商店 ID 列表)，该路径仅从他们的初始商店开始，并且他们从花费 0 时间开始。
2. 选择两个商店之间最短的未覆盖链接，s1和 s2 , 时间成本为 t .
3. 寻找一对推销员a1和 a2这样他们的路径开始或结束于 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除非它们是 a1 路径中的唯一元素或 a2 .例如，如果我正在查看商店之间的链接 1和 2我正在合并路径 [1, 3, 4]和 [2] (导致 [2, 1, 3, 4] 或 [4, 3, 1, 2] )，我可以删除所有剩余的商店链接 1 ，因为现在它在一条路径的中间，但不是来自 2 ，因为它仍然在合并路径的一端，因此可以连接。
• 合并时a1和 a2 , 如果 T - t_sum < t那么这个推销员将不可能再被合并(因为每个剩余链接的成本至少是 t )，所以你可以“关闭”路径，这意味着你可以丢弃每一端的链接，如果这样的话节省你的时间(取决于具体的实现)，你可以跳过a1和 a2在第 3 步的下一次执行中搜索时。
• 事实上，如果图形非常密集，您可以节省检查每次迭代或每隔几次迭代的时间，如果 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 秒。显然是 YMMV，但它不会运行数小时或数分钟。