带单路径时长限制的TSP近邻算法优化技术问询

• 场景需求：餐饮配送路径优化，每条配送路径累计时长需低于60分钟，考虑交付时间后实际限制为40分钟，避免食物变凉。
• 当前实现：基于**最近邻算法（Nearest Neighbor）**生成全访问TSP路径，再将路径拆分为符合时长限制的短段，最后通过排列调整各段节点顺序优化，但该方案并非最优解。
• 优化思路设想：采用递归方式——先生成时长≤40分钟的TSP路径，移除对应节点后重复执行直至所有节点完成分配。
• 需求：针对当前代码及方案，提出非暴力的优化方向。

当前实现代码 #

import itertools 

def tsp_nn(nodes):
    """
    输入节点间的距离二维数组，用最近邻启发式算法生成遍历路径，
    再将路径拆分为时长不超过60的分段，返回路径分段及各段距离。
    """
    if len(nodes) == 1:
        return 0
    
    unvisited = set(range(len(nodes)))
    solution = [0]
    current_node = 0
    total_distance = 0

    # 寻找最近邻节点构建路径
    while unvisited:
        nearest_neighbor = min(unvisited, key=lambda node: nodes[current_node][node])
        solution.append(nearest_neighbor)
        unvisited.remove(nearest_neighbor)
        total_distance += nodes[current_node][nearest_neighbor]
        current_node = nearest_neighbor


    # 将路径拆分为时长不超过60的分段
    path_segments, segment_distances = split_into_segments(solution, nodes)
    print(path_segments)
    # 打印结果
    print(f"Total distance: {total_distance}")
    for i in range(len(path_segments)):
        print(f"Segment {i}: {path_segments[i]}, distance: {segment_distances[i]}")
    # 返回路径分段和分段距离
    return path_segments, segment_distances


def calculate_distance(nodes, solution):
    """
    输入节点集合和路径，计算路径的总距离。
    """
    distance = 0
    for i in range(len(solution) - 1):
        distance += nodes[solution[i]][solution[i+1]]
    if len(solution)==1:
        distance=nodes[0][solution[0]]
    return distance


def split_into_segments(solution, nodes):
    """
    输入路径和节点间距离，将路径拆分为最长不超过60的分段，返回分段及各段距离。
    """
    path_segments = []
    segment_distances = []
    unvisited = list(range(len(nodes)))
    while solution:
        # 寻找最长的、距离≤40的子路径
        max_distance = 0
        max_path = None
        for i in range(len(solution)):
            for j in range(i+1, len(solution)):
                distance = calculate_distance(nodes, solution[i:j+1])
                if distance <= 40 and distance > max_distance:
                    max_distance = distance
                    max_path = (i, j)

        if max_path is None:
            break

        # 从原路径中移除该子路径的节点
        i, j = max_path
        path_segments.append(solution[i:j+1])
        for k in range(i,j+1):
            try:
                unvisited.remove(solution[k])
            except:
                pass

        segment_distances.append(max_distance)
        solution = solution[:i] + solution[j+1:]
    if len(unvisited)>0:
        path_segments.append(unvisited) 
        segment_distances.append(calculate_distance(nodes,unvisited))
    return path_segments, segment_distances

def valid(candidate):
    """
    输入候选路径分段，生成每段节点的所有排列，返回每段的最短距离路径。
    """
    final = []
    
    for k in candidate:
        possible=[]
        # 移除路径中的0节点
        while 0 in k:
            k.remove(0)
        li=list(itertools.permutations(k))
        for i in li:
            weight=calculate_distance(nodes,i)
            possible.append((weight,i))
    
        final.append(sorted(possible)[0])
            
    for i in final:
        print(f"Segment {i[1]}: distance: {i[0]}")


# 示例输入
nodes = [
    [0, 17, 8, 7, 24, 21, 17, 31, 2, 9, 8, 15, 18, 26, 24, 14],
    [17, 0, 11, 22, 19, 22, 27, 30, 17, 14, 18, 17, 1, 16, 17, 11],
    [8, 11, 0, 11, 21, 19, 21, 26, 6, 5, 7, 12, 13, 21, 19, 9],     
    [7, 22, 11, 0, 26, 22, 11, 26, 6, 14, 10, 13, 24, 31, 28, 20], 
    [24, 19, 21, 26, 0, 15, 28, 19, 25, 26, 30, 19, 21, 26, 25, 25], 
    [21, 22, 19, 22, 15, 0, 22, 26, 18, 19, 21, 12, 19, 32, 28, 18], 
    [17, 27, 21, 11, 28, 22, 0, 30, 16, 24, 17, 17, 28, 32, 30, 24], 
    [31, 30, 26, 26, 19, 26, 30, 0, 29, 31, 34, 18, 34, 39, 38, 31], 
    [2, 17, 6, 6, 25, 18, 16, 29, 0, 9, 7, 14, 17, 26, 24, 14], 
    [9, 14, 5, 14, 26, 19, 24, 31, 9, 0, 11, 14, 14, 18, 17, 10], 
    [8, 18, 7, 10, 30, 21, 17, 34, 7, 11, 0, 19, 20, 21, 19, 13], 
    [15, 17, 12, 13, 19, 12, 17, 18, 14, 14, 19, 0, 19, 28, 26, 16], 
    [18, 1, 13, 24, 21, 19, 28, 34, 17, 14, 20, 19, 0, 16, 17, 11], 
    [26, 16, 21, 31, 26, 32, 32, 39, 26, 18, 21, 28, 16, 0, 6, 10], 
    [24, 17, 19, 28, 25, 28, 30, 38, 24, 17, 19, 26, 17, 6, 0, 11], 
    [14, 11, 9, 20, 25, 18, 24, 31, 14, 10, 13, 16, 11, 10, 11, 0]]


path_segments, segment_distances = tsp_nn(nodes)
print("===============================================")
valid(path_segments)

当前输出 #

Total distance: 175
Segment 0: [11, 3, 10, 6], distance: 40
Segment 1: [0, 0, 8, 2, 9, 15, 13, 14], distance: 39
Segment 2: [1, 12, 5, 4], distance: 35
Segment 3: [7], distance: 31
===============================================
Segment (10, 3, 6, 11): distance: 38
Segment (8, 2, 9, 15, 13, 14): distance: 37
Segment (1, 12, 5, 4): distance: 35
Segment (7,): distance: 31

代码及方案改进建议 #

1. 修复当前代码的基础问题 #

• 移除重复节点：输出可见Segment 1出现重复的0节点，原因是split_into_segments中维护的unvisited列表与原solution处理逻辑冲突，建议直接基于solution的剩余节点处理，无需额外维护unvisited，避免重复添加节点。
• 统一路径计算逻辑：明确每段路径的起点为配送站（0），计算时应包含从0出发到第一个节点、遍历所有节点后返回0的总距离，当前valid函数移除0的逻辑会导致路径起点缺失，需修正。

2. 替换暴力排列的优化方案 #

当前valid函数用全排列枚举所有可能，节点数超过5个就会性能爆炸，建议替换为：

• 小规模TSP动态规划：对每个拆分后的节点子集，用DP算法计算最优路径，时间复杂度O(n²2ⁿ)，对于n≤10的子集完全可行；
• 2-opt局部搜索：对生成的初始路径进行边调整，通过交换路径中的两条边减少总距离，同时保证时长不超过40分钟。

3. 实现递归式的路径生成（而非事后拆分） #

你提出的递归思路更贴合需求，应直接生成符合时长限制的路径，而非先生成全局TSP再拆分，步骤如下：

1. 每次从剩余节点中，以配送站（0）为起点，用带约束的最近邻算法生成最长的、总时长≤40分钟的路径；
2. 移除该路径中的节点（除0），递归处理剩余节点；
3. 对每段生成的路径，用2-opt或DP进行局部优化，确保该段是该节点子集的最优路径。

4. 贴合实际场景的约束补充 #

当前代码仅考虑路程时间，建议将固定交付时间（每个节点的配送耗时，比如5分钟）加入总时长计算，让结果更符合真实配送场景。

内容的提问来源于stack exchange，提问作者huntrese