优化的旅程计划规划

Question

我有一个问题要解决。

问题陈述：

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

这将由推销员完成。

我想生成N个优化的旅程计划，以便每个销售人员能够在8小时内覆盖最大商店数量。

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

两个推销员都不应该去同一家商店。

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

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

需要最终结果：

尽量减少行程计划的数量，以覆盖所有商店

我有什么：

商店到商店的距离矩阵。 每个商店之间覆盖的距离和花费的时间

查兰格： 我没有关于推销员的任何信息(即我没有他们的地理位置)，这使得很难为每个旅程计划选择起点。

我最初的想法：

我正在考虑通过聚类将商店划分为不同的区域。 然后为每个集群形成旅程计划(优化路线)。

我将用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)，因此您可以"关闭"路径，这意味着您可以丢弃两端的链接，如果这可以节省您的时间(取决于确切的实现)， 在步骤 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秒。显然是YMMV，但它不会运行数小时或数分钟。