python - 如何使用Python中的or-tools解决累积旅行商问题？

Question

累积旅行商问题 (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 = 45。
• 位置时间为 35。对于位置 1:0 -> 1:10。对于位置 2(请注意，我们必须经过位置 1):0 -> 1: 10 + 1 -> 2: 15。总之，我们有:10 + 10 + 15 = 35。

目标 2:如果我们想尽量减少到达地点的时间

解决方案是 0 -> 1 -> 0 和 0 -> 2 -> 0(使用两辆车)，其中:

• 行程时间为 60。对于车辆 1:0 -> 1:10 + 1 -> 0:10。对于车辆 2 : 0 -> 2: 20 + 2 -> 0: 20. 总而言之，我们有 10 +
10 + 20 + 20 = 60。
• 位置时间为 30。对于位置 1:0 -> 1:10。对于位置 2(请注意，我们没有通过位置 1): 0 -> 2: 20。总之，我们有:10 + 20 = 30。

那么...这可以做到吗？能否解决 CTSP(目标 2)？是否可以有一个目标函数来平衡这两个目标(即 min alpha *overall_travel_time + beta *time_to_locations，这样 alpha 和 beta 是权重)。 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

Answer 1

尝试看一下 VRP Global Span 示例...即最小化全局跨度将尝试最小化最长的路线。来源:https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/doc/VRP.md#global-span-constraints

注意:如果您想要两条以上路线之间真正的差异最小化，目前尚未实现，请参阅 https://github.com/google/or-tools/issues/550有关详细信息...