def tsp_dp_approx_sol()

in archived/rl_traveling_salesman_vehicle_routing_coach/src/TSP_baseline_utils.py [0:0]

• 32 lines of code
• 17 McCabe index (conditional complexity)

def tsp_dp_approx_sol(res_xy, orders_xy):
    # This baseline is for the TSP problem,
    # a single agent traveling all orders starting and finishing at a single restaurant
    # assuming res_xy = (res_x, res_y), orders_xy = [(order1_x, order1_y), ...]

    all_xy = [res_xy] + orders_xy
    num_stops = len(all_xy)
    D = create_dist_matrix(all_xy, num_stops)

    # Best cost in stage i for each order
    DP = {i: {} for i in range(num_stops)}
    # Subsequent visits in the best route from stage i on for each order
    DP_will_visit = {i: {} for i in range(num_stops)}

    # DP solution, backwards
    for i in reversed(range(num_stops)):
        # This is the final visit to the restaurant
        if i == num_stops - 1:
            for o in range(1, num_stops):
                DP[i][o] = D[o][0]
                DP_will_visit[i][o] = [o]
        else:
            if i == 0:
                stop_list = [0]
            else:
                stop_list = range(1, num_stops)

            for o in stop_list:
                min_dist = np.inf
                min_o_next = None
                for o_next in range(1, num_stops):
                    if o_next in DP_will_visit[i + 1].keys():
                        if o not in DP_will_visit[i + 1][o_next]:
                            cost = D[o][o_next] + DP[i + 1][o_next]
                            if cost < min_dist:
                                min_o_next = o_next
                                min_dist = cost

                if min_o_next:
                    DP[i][o] = min_dist
                    DP_will_visit[i][o] = [o] + DP_will_visit[i + 1][min_o_next]

    print(DP)
    print(DP_will_visit)
    return DP[0], DP_will_visit[0][0] + [0]