Python routing VRP - time limit and search monitor

[Andres Collart]

Trying to solve a routing VRP in python modified from the or-tools routing library examples. However, I'm having 3 issues:

1. The search_time_limit is not being enforced. Search will continue for hours if left to it, even though it's set for 5 minutes. 

2. I'd like to add a search monitor that shows me when a solution has been found. All I want is the objective function returned and a time stamp. 

3. I have 30ish depots and hoping to scale the problem up around 7000 nodes visited. However, to do so I need to break it up somewhat. Best I've been able to run so far is like 1000 routes by running it overnight. I'm thinking of adding a constraint that limits some nodes to not be visited by trucks from certain depots. Basically creating some sort of overlapping service area for each depot. However, since the service areas are overlapping I can't fully just create 30 different models. How would I limit which depots can service which nodes?

Has anyone ran into these issues before and know how to fix them?

Thank you,

  #Times in seconds

  # Create the data.

  planning_horizon=24*60*60

    

  data = create_data_array(planning_horizon)

  locations = data[0]

  demands = data[1]

  start_times = data[2]

  num_locations = len(locations)

  depots=len(df_depots)

  num_vehicles_perdepot=10

  num_vehicles = num_vehicles_perdepot*depots #Per depot

  #additional_vehicle_cost=1882 #meters-worth

  cost_per_km=1.7 #dollars

  search_time_limit = 300*1000 #milliseconds -> 5 minutes

  # Create routing model.

  if num_locations > 0:

    # The number of nodes of the VRP is num_locations.

    # Nodes are indexed from 0 to tsp_size - 1. By default the start of

    # a route is node 0.

    vehicle_depots=[locations.iloc[x]['objectid'] for x in xrange(0,depots)for y in xrange(0,num_vehicles_perdepot)]

    

    routing = pywrapcp.RoutingModel(num_locations, num_vehicles, 

                                    [x for x in xrange(0,depots)\

                                       for y in xrange(0,num_vehicles_perdepot)],

                                    [x for x in xrange(0,depots)\

                                       for y in xrange(0,num_vehicles_perdepot)])

    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

    search_parameters.time_limit_ms = search_time_limit

    #search_parameters.log_search = True

    

    # Set first solution heuristic: the

    # method for finding a first solution to the problem.

    search_parameters.first_solution_strategy = (

        routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC)

        #FirstSolutionStrategy.PATH_CHEAPEST_ARC

    # The 'PATH_CHEAPEST_ARC' method does the following:

    # Starting from a route "start" node, connect it to the node which produces the

    # cheapest route segment, then extend the route by iterating on the last

    # node added to the route.

    

    # Put callbacks to the distance function here.

    dist_between_locations = CreateDistanceCallback(locations)

    dist_callback = dist_between_locations.Distance

    routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

    demands_at_locations = CreateDemandCallback(demands)

    demands_callback = demands_at_locations.Demand

    

    # Add capacity dimension constraints.

    vehicle_capacity = 50000;

    null_capacity_slack = 0;

    fix_start_cumul_to_zero = True

    capacity = "Capacity"

    #routing.AddDimension(demands_callback, null_capacity_slack, vehicle_capacity,

    #                     fix_start_cumul_to_zero, capacity)

    

    # Adding time dimension constraints.

    #time_per_demand_unit = 5 * 60 # 5 minutes for pickup

    horizon = planning_horizon #Set maximum time for any.

    time = "Time"

    #tw_duration = 30 * 60 # 30 minutes

    speed = 70*1000/(60.0*60) # meter/ second

    service_times = CreateServiceTimeCallback(demands, speed)

    service_time_callback = service_times.ServiceTime

    total_times = CreateTotalTimeCallback(service_time_callback, dist_callback, speed)

    total_time_callback = total_times.TotalTime

    # Note: In this case fix_start_cumul_to_zero is set to False,

    # because some vehicles start their routes after time 0, due to resource constraints.

    

    # Add a dimension for time and a limit on the total time_horizon

    fix_start_cumul_to_zero = False

    routing.AddDimension(total_time_callback,  # total time function callback

                         horizon,

                         horizon,

                         fix_start_cumul_to_zero,

                         time)

    time_dimension = routing.GetDimensionOrDie("Time")

    #for order in range(1, num_locations):

    #  start = start_times[order]

    #  time_dimension.CumulVar(order).SetRange(start, start + tw_duration)

        

    print "here- disjunction"

    # Add disjunction - Support reverse nodes

    for item in locations[~locations.objectid.isin(df_depots.objectid.unique())].drop_duplicates('objectid').index:

        obj_id=locations.loc[item]['objectid']

        print locations[locations.objectid==obj_id].index.tolist()

        routing.AddDisjunction(locations[locations.objectid==obj_id].index.tolist())

        

    # Solve, displays a solution if any.

    assignment = routing.SolveWithParameters(search_parameters)

    

    #Print solution

    if assignment:

      #prepare DataFrame output

      locations['Route_Depot']=''

      locations['Route_Number']=0

    

      # Solution distance.

      #Not distance exactly given the cost of adding new vehicles is taken as a distance metric

      #print "Total distance of all routes: {:,.2f} km\n".format(assignment.ObjectiveValue()/1000.0)

      print "Total cost of all routes: ${:,.2f}".format(cost_per_km*assignment.ObjectiveValue()/1000.0)

      print "Does not factor in cost of additional passengers ($0.70 each)\n"

      # Display solution.

      #capacity_dimension = routing.GetDimensionOrDie(capacity);

      time_dimension = routing.GetDimensionOrDie(time);

      for vehicle_nbr in range(num_vehicles):

        index = routing.Start(int(vehicle_nbr))

        plan_output = 'Route {0}:'.format(vehicle_nbr)

        while not routing.IsEnd(index):

          node_index = routing.IndexToNode(index)

          #load_var = capacity_dimension.CumulVar(index)

          time_var = time_dimension.CumulVar(index)

          plan_output += \

                    " \n{node_index} StartTime({tmin}) ServTime {serv_time}s-> ".format(

                        node_index=node_index, #locations.iloc[node_index]['objectid'],

                        tmin=str(assignment.Value(time_var)),

                        serv_time=service_times.ServiceTime(node_index))

          

          #For every point except route start

          if not routing.IsStart(index):

              locations.set_value(node_index,'Route_Depot',vehicle_depots[vehicle_nbr])

              locations.set_value(node_index,'Route_Number',vehicle_nbr)

        

          index = assignment.Value(routing.NextVar(index))

        node_index = routing.IndexToNode(index)  # Convert index to node

        #load_var = capacity_dimension.CumulVar(index)

        time_var = time_dimension.CumulVar(index)

        plan_output += \

                  " \n{node_index} StartTime({tmin}) ServTime {serv_time}s".format(

                      node_index=node_index, #locations.iloc[node_index]['objectid'],

                      tmin=str(assignment.Value(time_var)),

                      serv_time=service_times.ServiceTime(node_index))

        #print plan_output

        #print "\n"

[Vincent Furnon]

About 2. you can use the AddAtSolutionCallback on the routing object to pass a callback that will be called for each solution found.

Example:

class SolutionCallback(object):

  def __init__(self, model):

    self.model = model

  def __call__(self):

    print self.model.CostVar().Max()

...

solution_callback = SolutionCallback(routing)

routing.AddAtSolutionCallback(solution_callback)

--
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-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Vincent Furnon]

About 1, this is really strange (did not manage to reproduce it on my side). What OS/compiler are you using ? When you use log_search, is the search stuck in the first solution phase or do you see new solutions being found ?

BTW why are you using GLOBAL_CHEAPEST_ARC ? This heuristic is usually much slower than the others such as PATH_CHEAPEST_ARC. 

[Andres Collart]

Thank you, that seems to be mostly working but I do get an error when the script finishes running (see below). I also just get all the printout from the monitor at the end, not while the process is running. Do you know what could be causing that?

I'm using MacOS and then python via KNIME. I've also ran into issue #1 in an earlier version of this model on just Jupyter notebooks. I can't run the log_search because the optimization never ends for those to be created... I can try running one overnight of a good size and see what's happening. Where would the log_search results be found?

Traceback (most recent call last):
  File "/Applications/KNIME 3.3.1.app/Contents/Eclipse/plugins/org.knime.python_3.3.0.v201611242050/py/PythonKernel.py", line 282, in execute
    exec(source_code, _exec_env, _exec_env)
  File "<string>", line 296, in <module>
  File "<string>", line 231, in Solve_Routes
  File "/Users/andrescollart/anaconda/lib/python2.7/site-packages/pandas/core/frame.py", line 2357, in __setitem__
    self._set_item(key, value)
  File "/Users/andrescollart/anaconda/lib/python2.7/site-packages/pandas/core/frame.py", line 2422, in _set_item
    self._ensure_valid_index(value)
  File "/Users/andrescollart/anaconda/lib/python2.7/site-packages/pandas/core/frame.py", line 2400, in _ensure_valid_index
    if not len(self.index) and is_list_like(value):
  File "/Users/andrescollart/anaconda/lib/python2.7/site-packages/pandas/indexes/range.py", line 439, in __len__
    return max(0, -(-(self._stop - self._start) // self._step))
RuntimeError: std::function<void()> invocation failed.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Andres Collart]

Changed the heuristic to PATH_CHEAPEST_ARC. I'd just been trying a few on a small problem and hadn't seen much of a difference between them, but likely the problem was too small to actually test.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Andres Collart]

For #3, I'm planning on using the .Solver() object to add the constraints using the normal CP library.

If a pre-compute a matrix of Vehicles to Nodes, with 0's for those that shouldn't be visited. How can I add the constraint to restrict vehicles to visiting nodes with a corresponding 0?

I thought of doing so through an AddDimension too, and having a max capacity of 0 for the vehicle (in this case flipping so that 1's are nodes that can't be visited).  I used the code below to test, but I suspect that what I'm reading as "route number" is actually the from_node. How would I access the route_number there?

# Zoning callback
class CreateZoningCallback(object):
  """Create callback to get zoning at each node."""


  def __init__(self):
    print "initialized zoning callback"


  def Ability(self, route_number, to_node):
    #All allowed
    #print "route num: %s, to_node: %s"%(route_number,to_node)
    return 0 #self.matrix[route_number][to_node]

Thank you,

Andres