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


11

累積旅行商問題(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 -> 00 -> 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
3

This is a heuristic approach to the problem you describe using OR tools. Consider a procedure in which you “guess” what the maximum route duration is (across all routes), and will find this in a binary search fashion. Your guess, $G$, is between $L$ and $U$, and for a particular iteration, set it to $G=\frac{U+L}{2}$. At iteration 0, $L=0$and $U=\texttt{max duration vrp}$ (45 in your example). Now add a constraint to the problem using routing.AddDimension() that says that routes should have a duration less or equal to $G$. If the problem is feasible, then $U=G$ and update $G$. Otherwise, $L=G$ and update $G$. You do this until the $L$ and $U$ are arbitrarily close. Note that every time you update $G$, you need to update the constraint you added to the routing object (or create a new object from scratch).