VRPTW: OR-Tools does not return a feasible solution in a very simple case

I've been working with or-tools for a few months now but have recently experienced the following miss:

Model:

2 vehicles, each one has a start location s0, s1 and an end location t0, t1.
2 locations to visit x0, x1.

Time windows:

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

Durations matrix:

[
   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]
]

Where horizon = 86760 - this is just a large value to dismiss this potential assignment.

I get None when I pass it to the solver. Not sure why the solver doesn't return the trivial feasible solution which is s_i -> x_i -> t_i for i=0, 1

Remarks:

I'm using PARALLEL_CHEAPEST_INSERTION as it gives better solutions for my purposes than PATH_CHEAPEST_ARC but the ladder returns the correct solution.
After some more juggling with it, it seems that the problem is not in the close time window to the start location, but in the duration to the end location. I.e., if the first two rows would be:
```
[
   x0: [0, horizon, horizon, horizon, a, a], 
   x1: [horizon, 0, horizon, horizon, b, b], 
...
```
for any b >= a the solver will find the correct assignment.

If I restrict the vehicles to the correct locations, i.e.

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

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

I get the correct assignment (it means that the original model is indeed feasible).

Code example:

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)

Recommended topics

Hot tags