Set a max travel time

[lucasmengual92]

After I got my CVRP model working, I wanted to add a constraint to output the routingModel based on max travel time. I read through issue #685, and I´m just wondering if this could apply to my model but with slight modifications.

• For example I wouldnt need an initial min_dur #direct travel time but only a max_dur.
• Such as setting max_dur = 30 #minutes and sending that to the routingModel.

I´ve got already the callback to make the time_matrix:

def distance_api(lat1, long1, lat2, long2):
    
    gmaps = googlemaps.Client(key='XXXX')
    
    now = datetime.now()
    directions_result = gmaps.directions((str(lat1),str(long1)),
                                         (str(lat2),str(long2)),
                                         mode="driving",
                                         avoid="ferries",
                                         departure_time=now
                                         )
    
    distance = directions_result[0]['legs'][0]['distance']['value']/1000.0 #Distance A-B in kilometers
    time = directions_result[0]['legs'][0]['duration']['value']/60.0 #Time between A-B in minutes    
    return distance, time

#Distance and Time Callback
class CreateCallback(object):
    """Create callback to calculate distances between points."""

    def __init__(self):
        
    # Latitudes and longitudes of selected parkingmeters
        locations = lat_long_parquimetros

        """Create the distance/time matrix."""
        size = len(locations)
        self.distance_matrix = {}
        self.time_matrix = {}

        for from_node in xrange(size):
            self.distance_matrix[from_node] = {}
            self.time_matrix[from_node] = {}
            
            for to_node in xrange(size):
                if from_node == to_node:
                    self.distance_matrix[from_node][to_node] = 0
                    self.time_matrix[from_node][to_node] = 0
                else:             
                    x1 = locations[from_node][0]
                    y1 = locations[from_node][1]
                    x2 = locations[to_node][0]
                    y2 = locations[to_node][1]
                    self.distance_matrix[from_node][to_node], self.time_matrix[from_node][to_node]  = distance_api(x1, y1, x2, y2)
    
    #Calling distance from_node-TO-to_node
    def Distance(self, from_node, to_node):
        return int(self.distance_matrix[from_node][to_node])
    
    #Calling time from_node-TO-to_node
    def Time(self, from_node, to_node):
        return int(self.time_matrix[from_node][to_node])

[bertop89]

Check the issue #724 I opened recently. Basically, you need to create a new 'duration' dimension and restrict it to 30 minutes max.

[Mizux]

you can also restrict time_dimension.CumulVar for each Vehicle end node to max 30min.
This is useful if you have vehicles with different 'Max" value.
e.g. in java:

import java.util.ArrayList;
// Latest time at which each vehicle must end its tour.
private List<Integer> vehicleEndTime = new ArrayList();
...
for (int vehicle = 0; vehicle < numberOfVehicles; ++vehicle) {
  ...
  model.cumulVar(model.end(vehicle), "time").setMax(vehicleEndTime.get(vehicle));

note: Max value must be equal or inferior of "MaxCapacity" when creating the dimension.

src: https://github.com/google/or-tools/blob/master/examples/com/google/ortools/samples/CapacitatedVehicleRoutingProblemWithTimeWindows.java#L220

[lucasmengual92]

Thanks will check it out.
Soin my case will be:

dist_time_between_nodes = CreateCallback()
duration = "Duration"
routing.AddDimension(dist_time_between_nodes.Time,
                             30, #minutes
                             30, #minutes
                             True,
                             duration)

duration_dimension = routing.GetDimensionOrDie("Duration")
for v_idx in len(data.num_vehicles):
    routing.solver().Add(duration_dimension.CumulVar(routing.End(v_idx) <= int(25)))

With 30 set as max (in minutes), and the solver before the routing.SolveWithParameters part right?

[Mizux]

Yes,

So in your example the "default" is 30min+30min(slack aka waiting) route but then you further restrict to 25min some vehicle's route (here all of them).

note1: cumulVar(next) = cumulVar(curent) + transit(current, next) + slackVar(current)
note2: SlackVar is not defined for end node, since it's useless, so it will crash if you try to access it (cf #708 to access it in the solution)

[lucasmengual92]

So currently is giving me this error, when running the Solver() function:

AttributeError: 'RoutingModel' object has no attribute 'Solver'

def main():
    """Entry point of the program"""
    # Instantiate the data problem.
    data = DataProblem()

    # Create Routing Model
    routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.depot)
    for node in xrange(data.num_locations):
        routing.AddDisjunction([node], data.penalties[node])
    
    #######################################
    ###ADDING MAX TRAVEL TIME CONSTRAINT###
    #######################################
    
    dist_time_between_nodes = CreateCallback()
    duration = "Duration"
    routing.AddDimension(dist_time_between_nodes.Time, 30, 30, True, duration)
    duration_dimension = routing.GetDimensionOrDie(duration)  
    routing.Solver().Add(duration_dimension.CumulVar(routing.Start(1) <= int(25))) 
    
    # Create the distance/time callback, which takes two arguments (the from and to node indices)
    # and returns the distance or time between these nodes.
    #dist_time_between_nodes = CreateCallback()
    dist_time_callback = dist_time_between_nodes.Time #dist_between_nodes.Distance
    routing.SetArcCostEvaluatorOfAllVehicles(dist_time_callback)
    
    # Add Capacity constraint
    demand_evaluator = CreateDemandEvaluator(data).demand_evaluator
    add_capacity_constraints(routing, data, demand_evaluator)

    # Setting first solution heuristic (cheapest addition).
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    
    # Solve the problem.
    assignment = routing.SolveWithParameters(search_parameters)
    printer = ConsolePrinter(data, routing, assignment)
    printer.imprimir(dist_time_between_nodes.distance_matrix, dist_time_between_nodes.time_matrix)

if __name__ == '__main__':
    main()

[Mizux]

you should try routing.solver() instead

[kagacins]

Following along with this thread to try to accomplish the same goal, I try to run the code from here, verbatim, after creating my time_callback, adding the duration dimension, etc.

duration_dimension = routing.GetDimensionOrDie("Duration")
for v_idx in len(data.num_vehicles):
    routing.solver().Add(duration_dimension.CumulVar(routing.End(v_idx) <= int(25)))

...and I receive this error message...

TypeError: in method 'Solver_AddConstraint', argument 2 of type 'operations_research::Constraint *const'

...which is triggered deep within the solver here...

  --> 328         return _pywrapcp.Solver_AddConstraint(self, c)

I've tried a bunch of things and I keep coming back to this type error. Any insight would be massively appreciated.

[Mizux]

Wrong parenthesis, you must use:

solver = routing.solver()
for v_idx in range(data.num_vehicles):
        solver.Add(duration_dimension.CumulVar(routing.End(v_idx)) <= int(25))

As I said before, you can also use SetMax(), and you don't need to access the underlying solver:

 for v_idx in range(data.num_vehicles):
        duration_dimension.CumulVar(routing.End(v_idx)).SetMax(25)

note: you must use range() not len() in the for

[kagacins]

Thanks @Mizux! - would you recommend using SetMax over accessing the underlying solver? I've seen a couple different opinions about this. I ask because I was able to (seemingly - no error thrown) add a constraint to the solver using both methods you highlight, but the code seems to hang when I try to find assignment. I've had the code work nicely using time windows where I set the maximum total horizon for all trucks and unique truck capacity for each truck, so it seems I've set up most dimensions correctly. However, when I try to set a truck-specific time constraint as we've been discussing here, I don't get past the assignment line of code.

When I remove the call to the function that tries to add the unique duration constraint per vehicle and turn back on the function that calls my time window approach (i.e. same duration for each truck), assignment works fine, so it feels like it has to be something from the code below. I've also read that I should try different FirstSolutionStrategy when things hang, so I've tried that as well but continue to run into the same hang issue when trying to find assignment. Finally, as one more data point, I tried a third approach where I tried to use AddDimensionWithVehicleCapacity with the node evaluator being my time_callback and passing in a list of different durations by vehicle (like what I do when setting actual vehicle capacity using my demand_callback), but that also hangs at the assignment line.

Here is the exact code I'm trying to use right now (including setting the Duration dimension). I've ensured that each unique max_time is less than 12 * 60 * penalty_scale (from the dimension).

    duration = "Duration"
    routing.AddDimension(time_callback,
                         12 * 60 * penalty_scale,
                         12 * 60 * penalty_scale,
                         True,
                         duration)
    duration_dimension = routing.GetDimensionOrDie(duration)
    max_times = data["durations"]
    for v_idx in range(data["num_vehicles"]):
        max_time = int(max_times[v_idx])
        duration_dimension.CumulVar(routing.End(v_idx)).SetMax(max_time)

[Mizux]

What is the delta between 12 * 60 * penalty_scale and max_time ?

Just out of curiosity if you pass 12 * 60 * penalty_scale instead of max_time (i.e. like if SetMax() make no change) did you still see the issue ?

Maybe your max_time is too aggressive ?

[kagacins]

12 * 60 * penalty scale = 720000 and max_times = [450000, 450000, 330000]

I also just tried to shrink 12 * 60 * penalty_scale down to 450000 (the highest of my max_times) and I'm still getting the solve hang with different first solution attempts. Is it something in the dimension? I used the time_callback successfully in that time window approach I mentioned earlier as well, so I think that should be working correctly.

@Mizux please let me know if I can provide any more detailed information about the assignment hang or if I can provide more code for context. Your input is always appreciated.

[kagacins]

I come ripe with details, a solution, confusion, and I hope for clarity. So as I mentioned earlier, I had initially tried to add time constraints for all my vehicles by cheating with time window constraints, and this worked great, as seen below. All vehicles were back to the depot by time horizon and assignment was found:

def add_time_window_constraints(routing, data, time_callback):
    """Add time window constraints."""
    time = "Time"
    horizon = int(route_time_constraint * 60 * penalty_scale)
    routing.AddDimension(
        time_callback,
        horizon, # allow waiting time
        horizon, # maximum time per vehicle
        False, # Don't force start cumul to zero. This doesn't have any effect in this example,
               # since the depot has a start window of (0, 0).
        time)    
    time_dimension = routing.GetDimensionOrDie(time)

OK so that was working good. Then, I tried to remove and replace the time window constraint from above with a duration per vehicle, like this:

def add_duration_constraints(routing, data, time_callback):
    duration = "Duration"
    routing.AddDimension(time_callback,
                         int(7.5 * 60 * penalty_scale),
                         int(7.5 * 60 * penalty_scale),
                         True,
                         duration)

    duration_dimension = routing.GetDimensionOrDie(duration)
    max_times = data["durations"]
    for v_idx in range(data["num_vehicles"]):
        max_time = int(max_times[v_idx])
        print('vehicle {0}, duration: {1}'.format(v_idx, max_time))                
        routing.solver().Add(duration_dimension.CumulVar(routing.End(v_idx)) <= int(max_time))

As described earlier in this threads, when trying add_duration_constraints alone, the code hung when trying to solve for assignment with no error message or progress.

A colleague randomly suggested I try both - adding the time window constraint first, then the individual duration constraints. Magically (and inexplicably as far as I can tell), assignment was found, the individual vehicles adhered to the requested duration time, and all was right with the world...

...except I can't understand why these two functions are both required for the solver to solve. I would have thought that duration alone would be sufficient, but that caused my program much distress as it refused to move past the assignment line of code (didn't even return infeasible, just returned nothing). Is this behavior that can be explained? These are the only two dimensions that reference time in any way. Thanks again for any ingenuity.

[veer5551]

Hello @kagacins and Team ,

I am working on a similar problem to set a max travel time.
I am trying to model CVRPTW - reload example and set max travel time on each vehicle.
I added the time and duration constraint both. But the model seems to disrespect the duration constraint and allocates maximum nodes to the vehicle with max capacity amongst all, underutilizing the other vehicles.

An example I am working:
Number of vehicles = 3
Capacities = [3,4,6]
Duplicate depots = 5 ( 1 to 5)
Nodes = 29 (including all depots).

Demands are the same for all nodes.

Solution : It is the list of lists having nodes assigned for each vehicle
[ [0, 17, 0],[0, 7, 8, 9, 13, 0],[0, 21, 25, 29, 28, 27, 24, 5, 16, 15, 14, 10, 11, 12, 4, 20, 23, 26, 22, 18, 19, 3, 0]]
Corrospnding to [ V1 , V2 , V3]

Could you suggest to me what am I missing here or what is possibly wrong in the modelling?
Attaching the code I am working on.
text3.txt

Any help is greatly appreciated.
Thanks a lot for your help in advance!