7

我已经使用 or-tools 几个月了，但最近遇到了以下问题：

模型：

  • 2辆车，每辆车都有一个起始位置s0, s1和一个结束位置t0, t1。
  • 2个参观地点x0, x1。

时间窗口：

[[5400, 5820], [9000, 9420], [5520, 39719], [6420, 43319], [5521, 39720], [6421, 43320]]

持续时间矩阵：

[
   x0: [0, horizon, horizon, horizon, 5400, 5400], 
   x1: [horizon, 0, horizon, horizon, 1800, 1800], 
   s0: [0, 0, horizon, horizon, 0, horizon], 
   s1: [0, 0, horizon, horizon, horizon, 0], 
   t0: [horizon, horizon, horizon, horizon, horizon, horizon],
   t1: [horizon, horizon, horizon, horizon, horizon, horizon]
]

哪里horizon = 86760- 这只是一个很大的价值，可以忽略这个潜在的任务。

None当我将它传递给求解器时，我得到了。不知道为什么求解器不返回简单可行的解决s_i -> x_i -> t_i方案i=0, 1

评论：

  • 我正在使用PARALLEL_CHEAPEST_INSERTION它，因为它为我的目的提供了更好的解决方案，PATH_CHEAPEST_ARC但梯子返回了正确的解决方案。

  • 经过一番折腾，似乎问题不在于开始位置的关闭时间窗口，而在于结束位置的持续时间。即，如果前两行是：

    [
   x0: [0, horizon, horizon, horizon, a, a], 
   x1: [horizon, 0, horizon, horizon, b, b], 
...

    对于任何 b >= a求解器都会找到正确的分配。

  • 如果我将车辆限制在正确的位置，即

    index = manager.NodeToIndex(0)
routing.VehicleVar(index).SetValues([0])

index = manager.NodeToIndex(1)
routing.VehicleVar(index).SetValues([1])

    我得到了正确的分配（这意味着原始模型确实可行）。

代码示例：

from ortools.constraint_solver import pywrapcp, routing_enums_pb2


def add_durations(manager, routing, data):
    def duration_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["durations_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(duration_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    routing.AddDimension(
        transit_callback_index,
        data["horizon"],  # allow waiting time
        data["horizon"],  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        "Duration"
    )
    duration_dimension = routing.GetDimensionOrDie('Duration')

    # Add time window constraints for each location except start/end locations
    for location_idx in range(data["num_locations"]):
        index = manager.NodeToIndex(location_idx)
        duration_dimension.CumulVar(index).SetRange(data["time_windows"][location_idx][0], data["time_windows"][location_idx][1])
        routing.AddToAssignment(duration_dimension.SlackVar(index))

    # Add time window constraints for each vehicle start and end locations
    for vehicle_id in range(data["num_vehicles"]):
        st_index = routing.Start(vehicle_id)
        end_index = routing.End(vehicle_id)
        duration_dimension.CumulVar(st_index).SetRange(data["time_windows"][data["num_locations"] + vehicle_id][0],
                                                       data["time_windows"][data["num_locations"] + vehicle_id][1])
        duration_dimension.CumulVar(end_index).SetRange(data["time_windows"][data["num_locations"] + data["num_vehicles"] + vehicle_id][0],
                                                        data["time_windows"][data["num_locations"] + data["num_vehicles"] + vehicle_id][1])

def print_solution(data, manager, routing, assignment):
    """Prints assignment on console."""
    time_dimension = routing.GetDimensionOrDie('Duration')
    total_time = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            plan_output += '{0} Time({1},{2}) -> '.format(
                manager.IndexToNode(index), assignment.Min(time_var),
                assignment.Max(time_var))
            index = assignment.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
                                                    assignment.Min(time_var),
                                                    assignment.Max(time_var))
        plan_output += 'Time of the route: {}min\n'.format(
            assignment.Min(time_var))
        print(plan_output)
        total_time += assignment.Min(time_var)
    print('Total time of all routes: {}min'.format(total_time))


def run_vrp(a, b):
    """Solve the VRP with time windows."""
    data = {}

    data["num_vehicles"] = 2
    data["num_locations"] = 2
    data["time_windows"] = [[5400, 5820], [9000, 9420], [5520, 39719], [6420, 43319], [5521, 39720], [6421, 43320]]

    horizon = 86760

    data["horizon"] = horizon

    data["durations_matrix"] = [
        [0, horizon, horizon, horizon, a, a],
        [horizon, 0, horizon, horizon, b, b],
        [0, 0, horizon, horizon, 0, horizon],
        [0, 0, horizon, horizon, horizon, 0],
        [horizon, horizon, horizon, horizon, horizon, horizon],
        [horizon, horizon, horizon, horizon, horizon, horizon]
    ]

    num_all_locations = len(data["durations_matrix"])

    start_locations_indices = [2, 3]
    end_locations_indices = [4, 5]

    manager = pywrapcp.RoutingIndexManager(
        data["num_locations"] + 2 * data["num_vehicles"], data["num_vehicles"], start_locations_indices, end_locations_indices
    )

    routing = pywrapcp.RoutingModel(manager)

    add_durations(manager, routing, data)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION

    assignment = routing.SolveWithParameters(search_parameters)

    if assignment:
        print_solution(data, manager, routing, assignment)
    else:
        print("Assignment is None")

    return assignment

if __name__ == '__main__':
    # doesn't work
    a = 5000
    b = 4000
    assert run_vrp(a, b) is None

    # works, because b > a
    a = 3000
    assert run_vrp(a, b)
4

0 回答 0