如何在python中使用or-tools解決累積旅行商問題？

累積旅行商問題（CTSP）的目標是最大程度地減少到達客戶的總時間，而不是總的旅行時間。這不同於最小化總旅行時間。例如，如果一個人有無限制的車輛（＃個車輛與位置中的＃個相同）並且目標是使到達位置的總時間最小化，則每個位置將發送一輛車輛，因為這是滿足上述需求的最快方法。可以看到，or-tools路由模塊主要集中在最小化總體旅行時間（而不是到達位置的時間）上。有沒有一種解決CTSP的方法，甚至更好的是，在最小化到位置的時間與最小化旅行時間之間取得平衡（也許使用權重）？

讓我展示一個分析示例。假設我們有一個倉庫（0）和兩個客戶（1和2）。讓我們考慮以下時間矩陣：

[[0, 10, 20],
[10, 0, 15],
[20, 15, 0]]

假設我們的車輛數量等於地點數量（2輛）。讓我們考慮以下兩種情況：

目標1：如果我們想使總體旅行時間最短

解決方案是0 -> 1 -> 2 -> 0（使用一輛車），其中：

• 旅行時間為45。0 -> 1：10 + 1 -> 2：15 + 2 -> 0：20 = 10 + 15 + 20 =45。
• 位置時間為35。對於位置1：0 -> 1：10。對於位置2（請注意，我們必須經過位置1）：0 -> 1：10 + 1 -> 2：15。總而言之，我們有：10 + 10 + 15 =35。

目標2：如果我們想減少到達地點的時間

解決方案是0 -> 1 -> 0和0 -> 10（使用兩輛車），其中：

• 行駛時間為60。對於車輛1：0 -> 1：10 + 0 -> 12：10。對於車輛2：0 -> 13：20 + 2 -> 0：20。總而言之，我們的0 -> 15 =60。
• 位置時間是30。對於位置1：0 -> 1：10.對於位置2（請注意，我們 不必經過位置1）：0 -> 13：20總之，我們有：0 -> 18 = 30.

所以...可以做到嗎？一個可以解決CTSP（目標2）嗎？是否有可能具有一個目標功能，以便我們可以平衡這兩個目標（即0 -> 19，使得1 -> 20和1 -> 21為權重）。非常感謝 Python 代碼。謝謝！

目標1的工作代碼

"""Vehicles Routing Problem (VRP)."""

from __future__ import print_function

from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = [
        [0, 10, 20],
        [10, 0, 15],
        [20, 15, 0]
    ]
    data['num_vehicles'] = 2
    data['depot'] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    max_route_time = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_time = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_time += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'time of the route: {}\n'.format(route_time)
        print(plan_output)
        max_route_time = max(route_time, max_route_time)
    print('Maximum of the route times: {}'.format(max_route_time))


def main():
    """Solve the CVRP problem."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data['time_matrix']), data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['time_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)


if __name__ == '__main__':
    main()

上述代碼的結果

Route for vehicle 0:
 0 -> 0
time of the route: 0

Route for vehicle 1:
 0 ->  1 ->  2 -> 0
time of the route: 45

Maximum of the route times: 45