VRPTW cp solver failed

[Mithun Shenoy]

data['time_matrix'] = [

  [ 0, 13, 37, 23, 21 ],

  [ 13, 0, 25, 10, 8 ],

  [ 38, 27, 0, 18, 24 ],

  [ 24, 16, 19, 0, 10 ],

  [ 22, 7, 24, 9, 0 ]

]

    data['time_windows'] = [(540 , 660) , (1300 , 1500) , (720 , 820) , (900 , 1100) , (1150 , 1200)]

If the above is my time matrix and time window. My solver is failing. So i'm not understanding if my units in time matrix is in minutes then I'm also converting my timing window to minutes 

As you can see for location 0 timing window is 540-660 which is from 9 - 11 in hours. So in this case my solver is failing. Can anyone help me with this thing ?

[blind.line]

Well, there are a countably infinite set of things that you might have done wrong. Without your code, it is difficult to guess. 

But yes, your time window and your time matrix look good. So show what might be wrong…

James

On Apr 30, 2021, at 22:48, Mithun Shenoy <shenoym...@gmail.com> wrote:



--
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/5be96763-08a5-40bb-b960-335cec275f99n%40googlegroups.com.

[Mithun Shenoy]

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

import sys , json

def create_data_model():

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

    data = {}

    data['time_matrix'] = [

  [ 0, 13, 37, 23, 21 ],

  [ 13, 0, 25, 10, 8 ],

  [ 38, 27, 0, 18, 24 ],

  [ 24, 16, 19, 0, 10 ],

  [ 22, 7, 24, 9, 0 ]

]

    data['time_windows'] = [(0,120) , (540 , 600) , (180,240) , (780 , 840) , (360,420)]

    data['maxValue'] = max(data['time_windows'])[1]

    print(data['maxValue'])

    data['num_vehicles'] = 1

    data['depot'] = 0

    return data

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

    """Prints solution on console."""

    time_dimension = routing.GetDimensionOrDie('Time')

    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), solution.Min(time_var),

                solution.Max(time_var))

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

        time_var = time_dimension.CumulVar(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: {}min\n'.format(

            solution.Min(time_var))

        print(plan_output)

        total_time += solution.Min(time_var)

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

def get_cumul_data(solution, routing, dimension , manager):

  """Get cumulative data from a dimension and store it in an array."""

  # Returns an array cumul_data whose i,j entry contains the minimum and

  # maximum of CumulVar for the dimension at the jth node on route :

  # - cumul_data[i][j][0] is the minimum.

  # - cumul_data[i][j][1] is the maximum.

  cumul_data = []

  for route_nbr in range(routing.vehicles()):

    route_data = []

    index = routing.Start(route_nbr)

    dim_var = dimension.CumulVar(index)

    route_data.append([solution.Min(dim_var), solution.Max(dim_var)])

    while not routing.IsEnd(index):

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

      dim_var = dimension.CumulVar(index)

      route_data.append([manager.IndexToNode(index) ,solution.Min(dim_var), solution.Max(dim_var)])

    cumul_data.append(route_data)

  return route_data

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 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,

        100,  # allow waiting time

        data['maxValue'],  # 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])

    # 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])

    # 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_CHEAPEST_ARC)

    # print(search_parameters.first_solution_strategy)

    # Solve the problem.

    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.

    if solution:

        # print_solution(data, manager, routing, solution)

        routes = get_cumul_data(solution, routing, time_dimension , manager)

        print(routes)

    else:

        # print(solution)

        print("Solution does not exist")

if __name__ == '__main__':

    main()

------------------------------------------

Hi this is my code. I'm not getting any solutions for this

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

Hi Mithun,

The problem is the slack variable, plus the fact that you did not have
disjunctions turned on.

So without disjunctions, the solver *must* go to every node. However,
it is impossible to get to all of the nodes given your quick travel
time, and small slack values.

For the time dimension, you coded:

```python

# Add Time Windows constraint.
time = 'Time'
routing.AddDimension(
transit_callback_index,
100, # allow waiting time
data['maxValue'], # maximum time per vehicle
False, # Don't force start cumul to zero.
time)
time_dimension = routing.GetDimensionOrDie(time)

```

Note the slack value of 100.

Now consider your time windows and travel times.

```python

data['time_windows'] = [(0,120) , (540 , 600) , (180,240) , (780 , 840) , (360,420)]

```

Look at node zero, the depot.

120 + 100 is 220. The only node that is close is node 2. Given the
travel time from 0 to 2 of 37, you can leave as early as 43 I think
and with the slack of 100 you can get to node 2 after the start of the
time window.

But from node 2, it is impossible to get anywhere but node 4. The
latest you can leave the home depot is 120, plus 100 plus 37 puts you
at 257, which is outide the time window. So the latest you can leave
from node 2 is 240, but 240 + 100 is 340...the only time window close
is node 4 at 360. With the travel time of 24 from 2 to 4, the latest
you can arrive at 4 is 240 + 100 + 24 which is 364.

with a starting time of 364 at node 4, the extra slack of 100 puts
that at 464. but none of the other nodes are possible (earliest
arrival times of 540 and 780)

If you add disjunctions, the the solver can drop nodes:

```python
#################################################################
# Add disjunction
#################################################################

# Add penalty for dropping route nodes

for location_idx, time_window in enumerate(data['time_windows']):
if location_idx == data['depot']:
continue
index = manager.NodeToIndex(location_idx)

print(f"adding disjunction for route node {location_idx} (index {index})")
routing.AddDisjunction([index], 1000)
```

then the solver finds a solution:

```
:~$ python timewindow_question.py
840
adding disjunction for route node 1 (index 1)
adding disjunction for route node 2 (index 2)
adding disjunction for route node 3 (index 3)
adding disjunction for route node 4 (index 4)
[[99, 99], [2, 236, 236], [4, 360, 360], [0, 382, 382]]
```

Hope that helps,

James

> > <https://groups.google.com/d/msgid/or-tools-discuss/5be96763-08a5-40bb-b960-335cec275f99n%40googlegroups.com?utm_medium=email&utm_source=footer>
> > .

> >
> >
>
> --
> 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/26f05f19-897b-4016-8871-a447179b3918n%40googlegroups.com.


--

James E. Marca
Activimetrics LLC