Understanding time windows in VRP

[uni_r]

Hi, I have been trying to use or tools for days now, being completely new to this.

 I'm trying to implement some problems with time windows, but I don't really understand how to set time windows.

For example, if I want to set that at the depot I can go from midnight to midnight and at 4 other locations the time windows are:

[9 AM , 10 AM] (i can visit the location from 9 to 10 AM)

[11 AM , 13 AM]

[10 AM , 12 AM]

[8 AM, 11 AM]

How should I set the time windows?

I tried multiplying all the values * 60 but the compiler returns the following error: Exception: CP Solver fail

(Also, the time matrix values in the or tools examples are in minutes, right?)

Thank you!

[Laurent Perron]

everything is in whatever time unit you want.

Just be consistent.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
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/4050b379-2214-43f6-9323-1fcbcbc267can%40googlegroups.com.

[uni_r]

Hello and thank you!

But Which would be a consistent way then?

Because I thought it was consistent to set the time windows in minutes, for example set [11 AM ,13 AM ] as [660,780],  assuming that the values in the time matrix were in minutes. But the compiler gives me the error I wrote above and I don't understand....

[Vincent Furnon]

You define the time matrix, so make sure it's in minutes too. All time-related data must be in minutes.

BTW this is not a compiler error, it's just the solver letting you know the model is probably infeasible.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9de88f94-2e83-4fee-b214-114af3b72fcdn%40googlegroups.com.

[uni_r]

I used the same time matrix of the or tools example(but i removed some nodes for semplicity), this one:

  data['time_matrix'] = [

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

        [6, 0, 8, 3, 2, 6, 8, 4, 8],

        [9, 8, 0, 11, 10, 6, 3, 9, 5],

        [8, 3, 11, 0, 1, 7, 10, 6, 10],

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

        [3, 6, 6, 7, 6, 0, 2, 3, 2],

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

        [2, 4, 9, 6, 4, 3, 6, 0, 4],

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

    ]

    

and i set this time windows:

    data['time_windows'] = [

        (0, 1440),  # depot       [  0,    24]

        (480, 660),  # 1           [8 AM , 11 AM]

        (540, 720),  # 2  ..... 

        (660, 900),  # 3

        (600, 660),  # 4

        (600, 720),  # 5

        (720, 900),  # 6

        (660, 720),  # 7

        (600, 720),  # 8

   ]

By the way, the problem is a VRP with time windows,capacity and pick up and deliveries, so i also set this pickups and deliveries:

data['pickups_deliveries'] = [

        [1, 3],

        [2, 6],

        [4, 7],

        [5, 8],

     ]

Does this make sense?

I have also tried increasing the number of vehicles but it keeps giving me:  Exception: CP Solver fail

[Mizux Seiha]

Few things:

0. Could you share your source code or at least the part where you setup the Dimension etc...

1. Did you force your Time dimension to start at zero ? (IIRC fourth parameter to AddDimension(), the boolean one)

Yes True, vehicles will start at zero and have to wait at least ~470 min before trying to visit any node...
2. Do you have some Slack (i.e. waiting time) for each nodes so the vehicle may wait at location i to be on time at location i+1 ?

3. Why using 0 AM as starting time in your model ? if your vehicle start a 7h00 you can offset all values by 420 i.e. 0 will be 7h00, 60 8h00 etc...

and in the print function simply add this offset if you want to display time...

BTW do you have a gist or github repo with the "complete" source code ?
e.g. https://gist.github.com/Mizux/e737be82013ed787820309bca6de8c6e

[uni_r]

Hello Mizu, thank you again!

Im trying to do your 3 point, could you tell me how add the offset in the print function??Sorry but im totally new in python and or tools!

1. The parameter is false, should i change it in "true"??

2.mmmm i don't know, I have a vehicle that has to pick up some goods from some customers locations...I don't know if I have to set the waiting time

0. This is the part:

 # Add Capacity constraint.

    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')

    

    

     # Add Distance constraint.

    dimension_name = 'Distance'

    routing.AddDimension(

        transit_callback_index_distance,

        0,  # no slack

        3000,  # vehicle maximum travel distance

        True,  # start cumul to zero

        dimension_name)

    distance_dimension = routing.GetDimensionOrDie(dimension_name)

    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Define Transportation Requests.

    for request in data['pickups_deliveries']:

        pickup_index = manager.NodeToIndex(request[0])

        delivery_index = manager.NodeToIndex(request[1])

        routing.AddPickupAndDelivery(pickup_index, delivery_index)

        routing.solver().Add(

            routing.VehicleVar(pickup_index) == routing.VehicleVar(

                delivery_index))

        routing.solver().Add(

            distance_dimension.CumulVar(pickup_index) <=

            distance_dimension.CumulVar(delivery_index)) 

         

    

    # Add Time Windows constraint.

    time = 'Time'

    routing.AddDimension(

        transit_callback_index,

        999,  # allow waiting time

        999,  # 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)))

Thank you again!