python - 根据到最近的未服务点的距离选择算法的起点

Question

我写了一个关于最近邻算法的变体，它从 6 个不同的起点创建多条路线，其工作原理如下：

• 步骤 0：将所有客户端节点标记为“未服务”。转到步骤 1。
• 第 1 步：如果所有客户端节点都已标记为“已服务”，则停止。否则，在其中一个中心（或“仓库”）开始有一名新员工，将该员工的工作持续时间初始化为零，然后转到步骤 2。
• 第 2 步：从当前节点中，选择“未服务”的最近邻居客户端节点 j。如果当前工作时长和到 j 的步行距离加起来超过 25200，则该员工已完成轮班，转步骤 1，否则转步骤 3。
• 步骤 3：将 j 的步行距离以及 j 处的任务持续时间添加到当前工作持续时间。将节点 j 的标签从“未服务”更新为“已服务”。如果更新的工作时长超过 7 小时，则该员工已完成轮班，执行步骤 1。否则，执行步骤 2。

该算法接受如下距离矩阵

A = np.array([[      0,       4,      38, ...,    8360,    8507,    8545],
             [      4, 9999999,    1280, ...,     777,    1025,    1017],
             [     38,    1280, 9999999, ...,    1408,    1515,    1433],
             ...,
             [   8360,     777,    1408, ..., 9999999,    1530,    1449],
             [   8507,    1025,    1515, ...,    1530, 9999999,      82],
             [   8545,    1017,    1433, ...,    1449,      82, 9999999]])

每个节点的工作持续时间如下：

C = np.array([   0,    0],       
             [   4,  540],
             [  38,  480],
             ...,
             [8360, 1320],
             [8507, 1620],
             [8545, 1020]])

我目前有一个使用以下代码的算法的工作版本：

A = A
start = 2
wait = C

depots = [3,7,14,104,185,220] # starting points of routes
routes = []
routes_cost = []
path = [start]
cost = 0
N = A.shape[0]
mask = np.ones(N, dtype=bool)  # boolean values indicating which 
                               # locations have not been served
mask[start] = False
staff_count = 1
max_cost_per_staff = 7*60*60   # 7 hours in seconds

while True in mask:
  for i in range(N-1):
    last = path[-1]
    lastw = path[0]
    next_ind = np.argmin(A[last][mask]) # find minimum of remaining locations
    next_loc = np.arange(N)[mask][next_ind] # convert to original location
    path.append(next_loc)
    mask[next_loc] = False
    cost += sum(A[last, next_loc] + wait[lastw]) # adds distance between nodes and
                                                 # wait time for each node to cost
    unserved = np.where(mask == True)[0]
    if cost >= max_cost_per_staff:
      staff_count += 1
      routes_cost.append(cost)
      routes.append(path)
      cost = 0
      if unserved.size == 0:
        print("routes are complete")
        print(routes)
      else:
        start = random.choice(depots)
        path = [start]

这有效并返回了几条路线，唯一的问题是在一条路线的末端，下一条路线的起点是随机选择的。有没有办法可以修改它，以便它选择最接近未服务点的仓库？

标签： pythonalgorithmoptimizationnearest-neighbor