Negative pickup and demand capacity issue

[SergiBago]

Good morning,

I have to solve a problem, in which a company has different jobs in diferent places of a city. The idea is that instead of each worker having his own car, the company puts up a van that picks up and drops off workers. All workers have the same functions, so anyone can go to any job. In addition, the jobs have specific time windows.

So, I have done an example of time window with capacity constrains, where the pickups are positive values and the dropoffs are negative values, the only problem is that I have negative charges. That is, the vehicle tries to leave more workers than it carries. With the upper limit of the loads I have no problem.

I would like to know how I can do to restrict that the minimum of the load in the vehicles has to be 0.

Code:

!pip install ortools

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

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    #TIME PART
    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'] = 6   
    data['depot'] = 0

    # PICKUP AND DELIVERIES

    #PICKUPS
    data['demand'] = [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):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    time_dimension = routing.GetDimensionOrDie('Time')
    total_time = 0
    total_load = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_load = 0
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            node_index = manager.IndexToNode(index)
            route_load += data['demand'][node_index]

            plan_output += '{0} Time({1},{2}), Load {3} -> '.format( manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var), route_load)
            index = solution.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += '{0} Time({1},{2}), Load {3}\n'.format(manager.IndexToNode(index),
                                                    solution.Min(time_var),
                                                    solution.Max(time_var), route_load)
        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)

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


    ### PICKUPS AND
    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['demand'][from_node]


    demand_callback_index = routing.RegisterUnaryTransitCallback(
        demand_callback)


    capacity= 'Capacity'    
    routing.AddDimension(
        demand_callback_index,
        0,  # null capacity slack
        15,  # vehicle maximum capacities
        False,  # start cumul to zero
        capacity)


    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

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

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)


if __name__ == '__main__':
    main()

Solution:

Route for vehicle 0:
0 Time(0,0), Load 0 -> 0 Time(0,0), Load 0
Time of the route: 0min

Route for vehicle 1:
0 Time(0,0), Load 0 -> 0 Time(0,0), Load 0
Time of the route: 0min

Route for vehicle 2:
0 Time(0,0), Load 0 -> 9 Time(2,3), Load 1 -> 14 Time(7,8), Load 5 -> 16 Time(11,11), Load 13 -> 0 Time(18,18), Load 13
Time of the route: 18min

Route for vehicle 3:
0 Time(0,0), Load 0 -> 7 Time(2,4), Load 8 -> 1 Time(7,11), Load 9 -> 4 Time(10,13), Load 13 -> 3 Time(16,16), Load 11 -> 0 Time(24,24), Load 11
Time of the route: 24min

Route for vehicle 4:
0 Time(0,0), Load 0 -> 12 Time(4,4), Load -2 -> 13 Time(6,6), Load 2 -> 15 Time(11,11), Load -6 -> 11 Time(14,14), Load -5 -> 0 Time(20,20), Load -5
Time of the route: 20min

Route for vehicle 5:
0 Time(0,0), Load 0 -> 5 Time(3,3), Load 2 -> 8 Time(5,5), Load 10 -> 6 Time(7,7), Load 6 -> 2 Time(10,10), Load 7 -> 10 Time(14,14), Load 5 -> 0 Time(20,20), Load 5
Time of the route: 20min

Total time of all routes: 82min

[jmarca]

Maybe this part is the issue: ``` capacity= 'Capacity' routing.AddDimension( demand_callback_index, 0, # null capacity slack 15, # vehicle maximum capacities False, # start cumul to zero capacity) ``` Try setting the initial cumul to zero. I learned the hard way that dimensions have an absolute floor at zero, the only way you can drop off more than you pick up is if you let the solver find its own floor with that `False` in the dimension initialization command. Or perhaps it is something else... James

…

On Thu, Jan 13, 2022 at 04:48:41AM -0800, Sergi Bagó Vila wrote: Good morning, I have to solve a problem, in which a company has different jobs in diferent places of a city. The idea is that instead of each worker having his own car, the company puts up a van that picks up and drops off workers. All workers have the same functions, so anyone can go to any job. In addition, the jobs have specific time windows. So, I have done an example of time window with capacity constrains, where the pickups are positive values and the dropoffs are negative values, the only problem is that I have negative charges. That is, the vehicle tries to leave more workers than it carries. With the upper limit of the loads I have no problem. I would like to know how I can do to restrict that the minimum of the load in the vehicles has to be 0. Code: !pip install ortools """Vehicles Routing Problem (VRP) with Time Windows.""" from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" #TIME PART 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'] = 6 data['depot'] = 0 # PICKUP AND DELIVERIES #PICKUPS data['demand'] = [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): """Prints solution on console.""" print(f'Objective: {solution.ObjectiveValue()}') time_dimension = routing.GetDimensionOrDie('Time') total_time = 0 total_load = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) route_load = 0 while not routing.IsEnd(index): time_var = time_dimension.CumulVar(index) node_index = manager.IndexToNode(index) route_load += data['demand'][node_index] plan_output += '{0} Time({1},{2}), Load {3} -> '.format( manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var), route_load) index = solution.Value(routing.NextVar(index)) time_var = time_dimension.CumulVar(index) plan_output += '{0} Time({1},{2}), Load {3}\n'.format(manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var), route_load) 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) ##### ---- TIME ---- # 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) # 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))) ### PICKUPS AND 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['demand'][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback( demand_callback) capacity= 'Capacity' routing.AddDimension( demand_callback_index, 0, # null capacity slack 15, # vehicle maximum capacities False, # start cumul to zero capacity) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == '__main__': main() Solution: Route for vehicle 0: 0 Time(0,0), Load 0 -> 0 Time(0,0), Load 0 Time of the route: 0min Route for vehicle 1: 0 Time(0,0), Load 0 -> 0 Time(0,0), Load 0 Time of the route: 0min Route for vehicle 2: 0 Time(0,0), Load 0 -> 9 Time(2,3), Load 1 -> 14 Time(7,8), Load 5 -> 16 Time(11,11), Load 13 -> 0 Time(18,18), Load 13 Time of the route: 18min Route for vehicle 3: 0 Time(0,0), Load 0 -> 7 Time(2,4), Load 8 -> 1 Time(7,11), Load 9 -> 4 Time(10,13), Load 13 -> 3 Time(16,16), Load 11 -> 0 Time(24,24), Load 11 Time of the route: 24min Route for vehicle 4: 0 Time(0,0), Load 0 -> 12 Time(4,4), Load -2 -> 13 Time(6,6), Load 2 -> 15 Time(11,11), Load -6 -> 11 Time(14,14), Load -5 -> 0 Time(20,20), Load -5 Time of the route: 20min Route for vehicle 5: 0 Time(0,0), Load 0 -> 5 Time(3,3), Load 2 -> 8 Time(5,5), Load 10 -> 6 Time(7,7), Load 6 -> 2 Time(10,10), Load 7 -> 10 Time(14,14), Load 5 -> 0 Time(20,20), Load 5 Time of the route: 20min Total time of all routes: 82min -- Reply to this email directly or view it on GitHub: #3074 You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

-- James E. Marca Activimetrics LLC

[SergiBago]

Hi James,

I already tried that option, but it didn't solve the problem.

Furthermore, I think I need the start cumul to be bigguer than 0, since the vehicles leave the depot (company headquarters) loaded with the employees, and start dropping them of. When the employers end the that work, they are picked up and moved to another location. At the end of the day, all employes must be picked up and leaved at de depot.

All this conditions are okey with mi program, the only issue is the negative charge I mentioned above.

Thanks

[jmarca]

Then I suspect a mathematics error. Make sure you set a hard condition on the starting load of each vehicle to what you expect. Then check your loads and unloads

…

On Thu, Jan 13, 2022 at 08:52:10AM -0800, Sergi Bagó Vila wrote: Hi James, I already tried that option, but it didn't solve the problem. Furthermore, I think I need the start cumul to be bigguer than 0, since the vehicles leave the depot (company headquarters) loaded with the employees, and start dropping them of. When the employers end the that work, they are picked up and moved to another location. At the end of the day, all employes must be picked up and leaved at de depot. All this conditions are okey with mi program, the only issue is the negative charge I mentioned above. Thanks -- Reply to this email directly or view it on GitHub: #3074 (reply in thread) You are receiving this because you commented. Message ID: ***@***.***>

-- James E. Marca Activimetrics LLC

[SergiBago]

I think that I need to add the condition to make sure that at every pickup/demand node, the load of the vehicle plus the demand of that node is >=0, but I tried several things and none of them worked. Could you please tell me how to do it? a piece of code would be a great help.

Thanks!

[jmarca]

On Thu, Jan 13, 2022 at 10:57:07AM -0800, Sergi Bagó Vila wrote: I think that I need to add the condition to make sure that at every pickup/demand node, the load of the vehicle plus the demand of that node is >=0, but I tried several things and none of them worked. Could you please tell me how to do it? a piece of code would be a great help.

No need, that should happen automatically. If the vehicle has less than the required demand, unless there is slack in the dimension, it cannot visit. No, I don't have time to write code for you.

…

Thanks! -- Reply to this email directly or view it on GitHub: #3074 (comment) You are receiving this because you commented. Message ID: ***@***.***>

-- James E. Marca Activimetrics LLC

[Anshgala333]

i too have the same issue , where i try to deliver goods at a location
i also added negative demands in the demand array , and the solutuion is not giving any solution

this is my demands array = [0, 10, 30, -10, 30, 0] demands
this is my weight array = [0, 200, 300, -100, 600, 0] weight

i also added one extra coordinate for that specific location

and also
pickup_index = manager.NodeToIndex(2) # delivery node index
delivery_index = manager.NodeToIndex(3) # pickup node index

routing.AddPickupAndDelivery(pickup_index, delivery_index)
routing.solver().Add(
    routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index)
)
routing.solver().Add(
    capacity_dimension.CumulVar(pickup_index) >= capacity_dimension.CumulVar(delivery_index)
)

still doesnt work

[Anshgala333]

but as of now it is not dropping any nodes , instead taking all

[jmarca]

And if you have multiple visits per location, you need to generate multiple nodes for those locations, because each node in the model can only be visited once.

[Anshgala333]

my only problem is a valid solution wrt distance , such that all orders are delivered which start from depot and also those whose pickup and drop are decided , and also not exceed truck capacity

[Anshgala333]

yes i do "And if you have multiple visits per location, you need to generate multiple nodes for those locations, because each node in the model can only be visited once."

[Anshgala333]

what do you think what approach would work here
in official google or tools documentation for pickup and drop , they also only provide routes , not in constraints of demand and truck capacity
or thats just not possible ..?