OR-tools find no solution regarding VRPCTW with the example data

[Ding Feng]

Hi there,

  I've been playing around with the OR-tools(python) for couple of days now, and I appreciate all the effort the team put in to make it. I used it to solve all the examples and out of curiosity I wanted  to see if I can manage to solve VRPCTW use the tool. 

  

  So basically what I did was simply copy and paste all the example data and constrains and sort of merged them altogether. And the first time I ran the program, it says solver status 3, no solution. I thought maybe is because the veichles are not enough to make all the deliveries, so I added one veichle with 15 capacities. And after running the program, it found a solution, but the veichle I added was not used at all. Below is a snip of the output..

I was unsure what causes this behavior, so I start to investigate a liitle bit, what I found was I have to add a dummy veichle with capacity 4 (no less) for the algorithm to find a solution. And I also tried first solution stradegy with both CHEAPEST ARC and MOST CONSTARINED ARC, neither stradegy is able to find a solution with 4 vechiles.

I'm dying to know the reason for this behavior and what should I do to make the algorithm run with just enough veichles! Any help is greatly appreciated!

I'm currently using python 3.9.4 and my ortools library is up-to-date.

My code with just 4 vechiles are provided below... Also attched it.

Thanks!!!

######################################################

#######################my code #########################

#######################################################

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

def create_data_model():

    """Stores the data for the problem."""

    data = {}

    data['time_matrix'] = [

        [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],

        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],

        [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],

        [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],

        [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],

        [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],

        [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],

        [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],

        [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],

        [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],

        [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],

        [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],

        [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],

        [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],

        [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],

        [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],

        [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],

    ]

    data['distance_matrix'] = [

        [

            0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,

            468, 776, 662

        ],

        [

            548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,

            1016, 868, 1210

        ],

        [

            776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164,

            1130, 788, 1552, 754

        ],

        [

            696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,

            1164, 560, 1358

        ],

        [

            582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,

            1050, 674, 1244

        ],

        [

            274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,

            514, 1050, 708

        ],

        [

            502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,

            514, 1278, 480

        ],

        [

            194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320,

            662, 742, 856

        ],

        [

            308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662,

            320, 1084, 514

        ],

        [

            194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388,

            274, 810, 468

        ],

        [

            536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,

            730, 388, 1152, 354

        ],

        [

            502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114,

            308, 650, 274, 844

        ],

        [

            388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194,

            536, 388, 730

        ],

        [

            354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0,

            342, 422, 536

        ],

        [

            468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536,

            342, 0, 764, 194

        ],

        [

            776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274,

            388, 422, 764, 0, 798

        ],

        [

            662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730,

            536, 194, 798, 0

        ],

    ]

    data['time_windows'] = [

        (0, 5),  # depot

        (7, 12),  # 1

        (10, 15),  # 2

        (16, 18),  # 3

        (10, 13),  # 4

        (0, 5),  # 5

        (5, 10),  # 6

        (0, 4),  # 7

        (5, 10),  # 8

        (0, 3),  # 9

        (10, 16),  # 10

        (10, 15),  # 11

        (0, 5),  # 12

        (5, 10),  # 13

        (7, 8),  # 14

        (10, 15),  # 15

        (11, 15),  # 16

    ]

    data['num_vehicles'] = 4

    data['depot'] = 0

    data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]

    data['vehicle_capacities'] = [15, 15, 15, 15]

    return data

def print_solution(data, manager, routing, solution):

    def distance_callback(from_index, to_index):

        """Returns the distance between the two nodes."""

        # Convert from routing variable Index to distance matrix NodeIndex.

        from_node = manager.IndexToNode(from_index)

        to_node = manager.IndexToNode(to_index)

        return data['distance_matrix'][from_node][to_node]

    """Prints solution on console."""

    time_dimension = routing.GetDimensionOrDie('Time')

    total_time = 0

    total_distance = 0

    total_load = 0

    for vehicle_id in range(data['num_vehicles']):

        route_time = 0

        route_distance = 0

        route_load = 0

        index = routing.Start(vehicle_id)

        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)

        while not routing.IsEnd(index):

            node_index = manager.IndexToNode(index)

            route_load += data['demands'][node_index]

            time_var = time_dimension.CumulVar(index)

            slack_var = time_dimension.SlackVar(index)

            plan_output += '{0} Time({1},{2}) Load ({3}) Slack({4},{5}) -> '.format(

                manager.IndexToNode(index),

                solution.Min(time_var),

                solution.Max(time_var),

                route_load,

                solution.Min(slack_var),

                solution.Max(slack_var))

            previous_index = index

            index = solution.Value(routing.NextVar(index))

            route_time += routing.GetArcCostForVehicle(

                previous_index, index, vehicle_id)

            route_distance += distance_callback(previous_index, index)

        time_var = time_dimension.CumulVar(index)

        slack_var = time_dimension.SlackVar(index)

        plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),

                                                    solution.Min(time_var),

                                                    solution.Max(time_var))

        plan_output += 'Time of the route: {0}min\n'.format(

            solution.Min(time_var))

        plan_output += 'Distance of the route:{}m\n'.format(route_distance)

        plan_output += 'Load of the route:{}\n'.format(route_load)

        print(plan_output)

        total_time += solution.Min(time_var)

        total_distance += route_distance

        total_load += route_load

    print('Total time of all routes: {}min'.format(total_time))

    print('Total distance of all routes: {}m'.format(total_distance))

    print('Total load of all routes: {}'.format(total_load))

def main():

    """Solve the VRP with time windows."""

    # 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 demand call back

    def demand_callback(from_index):

        """Returns the demand of the node."""

        # Convert from routing variable Index to demands NodeIndex.

        from_node = manager.IndexToNode(from_index)

        return data['demands'][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(

        demand_callback)

    routing.AddDimensionWithVehicleCapacity(

        demand_callback_index,

        0,  # null capacity slack

        data['vehicle_capacities'],  # vehicle maximum capacities

        True,  # start cumul to zero

        'Capacity')

    # Create and register a transit callback.

    def time_callback(from_index, to_index):

        """Returns the travel 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)

    # Add Time Windows constraint.

    time = 'Time'

    routing.AddDimension(

        transit_callback_index,

        300,  # allow waiting time

        300,  # maximum time per vehicle

        False,  # Don't force start cumul to zero.

        time)

    time_dimension = routing.GetDimensionOrDie(time)

    # Add time window constraints for each location except depot.

    for location_idx, time_window in enumerate(data['time_windows']):

        if location_idx == data['depot']:

            continue

        index = manager.NodeToIndex(location_idx)

        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

        routing.AddToAssignment(time_dimension.SlackVar(index))

    # Add time window constraints for each vehicle start node.

    depot_idx = data['depot']

    for vehicle_id in range(data['num_vehicles']):

        index = routing.Start(vehicle_id)

        time_dimension.CumulVar(index).SetRange(

            data['time_windows'][depot_idx][0],

            data['time_windows'][depot_idx][1])

        routing.AddToAssignment(time_dimension.SlackVar(index))

    # Instantiate route start and end times to produce feasible times.

    for i in range(data['num_vehicles']):

        routing.AddVariableMinimizedByFinalizer(

            time_dimension.CumulVar(routing.Start(i)))

        routing.AddVariableMinimizedByFinalizer(

            time_dimension.CumulVar(routing.End(i)))

    # Setting first solution heuristic.

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    search_parameters.first_solution_strategy = (

        routing_enums_pb2.FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC)

    search_parameters.local_search_metaheuristic = (

        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

    search_parameters.time_limit.FromSeconds(15)

    # Solve the problem.

    solution = routing.SolveWithParameters(search_parameters)

    print("Solver status: ", routing.status())

    # Print solution on console.

    if solution:

        print_solution(data, manager, routing, solution)

    else:

        print('no solution')

if __name__ == '__main__':

    main()

[Mizux Seiha]

One explanation, is during the initial search, solve find a  solution with 5 vehicles, then the local search manages to reduce it to 4 vehicles.

[Ding Feng]

Hi there,

Thanks for the explanation! I can wrap my head around that.

But is there a way to avoid this? Can we somehow empower the initial search a little bit more?

[Laurent Perron]

Initial search can become extremely hard if the problem is too tight. 

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/792e562c-4f07-497f-8c16-e37bff95e846n%40googlegroups.com.

[blind.lin...@gmail.com]

Hi,

Another thing to try is to add disjunctions on all nodes with a really
really high penalty. I added the following and the solver got over
the hump in milliseconds:

```python
for event_node in range(1, len(data['time_windows'])):
event_index = manager.NodeToIndex(event_node)
routing.AddDisjunction([event_index], 1000000000)
```

This allows the solver to "drop" any node other than the depot, and so
it will do so to get the first solution, then it will quickly improve
that solution to add all the nodes back in.

hope that helps,
James

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/56c335d2-cb13-4158-855d-9fb174de495dn%40googlegroups.com.

> """Vehicles Routing Problem (VRP) with Time Windows."""

--

James E. Marca
Activimetrics LLC

[Ding Feng]

Hi there,

Thanks so much for all the suggestions and helps! I found the adding penalty method works perfectly for the example!