VRPCTW: defining current available capacity and max capacity

[amihai...@gmail.com]

Hello,

I have a pickup-delivery model that involves time and capacity constraints.

Also, some of the solver runs are performed on ongoing shifts, which means that the state of the problem is not "initial". In particular, it means that the max_capacity and the available_capacity of the vehicle, can differ (when the shift/vehicle is not ongoing these values equal),

Obviously, if we only pass to the solver the available_capacity, it won't find a solution to some very simple instances such as to the jobs [-1, 2] where the available_capacity is 1 and the max_capacity is 2.

What is the best practice to define these both parameters in the solver? I thought of the option of defining dummy locations with the relevant capacities but I just wanted to see if there's a cleaner, less bug-prone solution.

Thank you

[lvss pk]

Hello, 

I am not sure what you are saying here. Can you post some example code?

How are you using your dimensions?

Thanks 

--
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/c591d22f-a9bd-4f92-9daa-d65be2a83de8n%40googlegroups.com.

[amihai...@gmail.com]

Hi,

Here is a small example. Assume that the vehicle has a max capacity of 2, but since it's an online/ongoing shift it has an available capacity of 1:

```python

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['demands'] = [-1, 2]
data['vehicle_capacities'] = [1]
data['num_vehicles'] = 1
data['depot'] = 0
return data


def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(2, 1, 0)

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)


# Create and register a transit callback.
def distance_callback(from_index, to_index):
return 0

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)


# 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
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)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(1)

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

# Print solution on console.
if solution:
print("found solution")
else:
print("no solution")


if __name__ == '__main__':
main()

```python

[Priidik Vilumaa]

I have always used "initial location" dummy nodes that consume the correct amount of resources (capacity, time,...) within the optimization model

[amihai...@gmail.com]

Thanks - it what I had in mind to do.

[Mizux Seiha]

Did you try: `your_dimension.CumulVar(routing.Start(vehicle_index)).setValue(initial_value)` to "force" the current load at start node ?

[amihai...@gmail.com]

No! Thanks!!! will try.

[amihai...@gmail.com]

Thanks again mizux - it worked nicely. I had to change the start_cumul_from_zero to False though - I wonder how that might influence the solver's behaviour.