Limit max vehicles in list of nodes in time window

[ronenbh1]

Hello,
Is there a simple way to limit the number of vehicles visiting a list of nodes in a certain time window?
I want to model zone congestion control.
Thanks a lot,
Ronen

[ronenbh1]

I figured It. I will use additional nodes as zone entry/exit points.
Thank you guys for this great tool!

[Mizux]

Take a look at the resource constraint example: https://developers.google.com/optimization/routing/cvrptw_resources

# Add resource constraints.
your_node_list = [12,13,14,...]
solver = routing.solver()
intervals = []
for node in your_node_list:
  # Add time windows for each node
  intervals.append(
    solver.FixedDurationIntervalVar(
      time_dimension.CumulVar(manager.NodeToIndex(node)), # start time
      service_time, # duration
      f'node_{node}_interval'))

  # each node use 1 "token" of the resource
  resource_usage = [1 for i in range(len(intervals))]
  solver.Add(
    solver.Cumulative(
      intervals,
      resource_usage,
      number_of_token_available, # here 1  if we want one visit at a time 
      'congestion'))

[ronenbh1]

Thanks for your quick reply and sorry I missed your answer's notification :(
If I'm not mistaken, the interval helps when the resource is a specific node. In my case, the resource is a list of nodes representing a zone which I want to control the number of visits in it in any time window. I want to cumulate the visits globally for all routes.
I'm thinking of doing it using a global counter and using PARALLEL_CHEAPEST_INSERTION so I can count it simultaneously on all routes. I'm having difficulty adding a constraint that uses a variable I created outside the solver:

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

    return data


def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    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 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,
        30,  # allow waiting time
        30,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time)
    time_dimension = routing.GetDimensionOrDie(time)

    global glob_count
    glob_count = 0

    def glob_callback(from_index):
        if from_index in range(1, 4):
            glob_count += 1
        return 0

    glob_callback_index = routing.RegisterUnaryTransitCallback(glob_callback)

    # Add global constraint.
    glob = 'glob'
    routing.AddDimension(
        glob_callback_index,
        0,
        10,
        True,
        glob)
    glob_dimension = routing.GetDimensionOrDie(glob)
    routing.solver().Add(glob_count <= 2)

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

    for node_index in range(1, len(data['time_windows'])):
        index = manager.NodeToIndex(node_index)
        routing.AddDisjunction([index], 100)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.time_limit.FromSeconds(10)
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print("No Solution!")


if __name__ == '__main__':
    main()

Another way to do it may be adding a dimension that increments when entering a zone from an entry dummy nodes and to use:

  glob_vars = []
  for node in entry_nodes:
       glob_vars.append(glob_dimension.CumulVar(manager.NodeToIndex(node))
       routing.solver().Add(routing.solver().SumLessOrEqual(glob_vars, MAX_VEHICLES_IN_ZONE))

What do you think?
Thanks!

[ronenbh1]

Ok, I think I now understand your answer.
I confused it with the original example of resource constraints which is on the depot alone.
The added cumulative is on all the intervals together and considers all routes.
I tried it on the example I've attached above and it seems to work.
Please correct me if I'm wrong.
Thanks again you guys for your awesome job creating this project and being so helpful all the time!

[ronenbh1]

After trying to adjust your suggestion to my problem I figured it is not quit what I'm trying to solve.
When using your suggestion, when a node has been matched, the solver holds all the nodes from being matched during the duration period but then another vehicle can be matched to one of the nodes.
The constraint I want to add is that during the time a vehicle is traveling in a list of nodes (representing a zone) another vehicle cannot be matched in that zone until the first one left that zone.
Any other suggestions?

[Mizux]

yes contention is on nodes, not region unfortunately.