[need help]Could I allow multiple vehicles cross one node?

[shinkisan]

Hi all, I am trying to use ortools to solve a kind of real world problem. It is basicly a vehicle routing problem except it allows a customer's requirement be satisfield by multicle vehicles, and this may be more effeciency to this kind of problem.
Could I pass any argue to AddDimension function or do something else to implement this?
Sorry for this silly question cause I am new to vrp and ortools.
Thank you guys!

[Mizux]

Not sure to understand, by default any vehicle (if you have a fleet) can go to any nodes. OR-Tools solver will then try hard to find the best one.

After that, I don't understand why you want several vehicles to go to the same node except if the node demand is bigger than the vehicle capacity (not sure it works BTW).

[shinkisan]

@Mizux
Thanks for your reply sir. I will describe my question in detail. I have a warehouse and lot of clothes(demands) are stored here, in several shelves(nodes). I also have some people(vehicles) to pick this clothes everyday. I want to plan people's route by ortools. But it often encounter "No solution found" problem. I was trying to found out why, sometimes it caused by "node demand is bigger than the vehicle capacity" situation. and sometimes it may happen though no demand reach the capacity.
For example. there are 2 vehicles and each of their capacity is 3, we have 3 nodes and each nodes' demand is 2, I thinnk there won't be a solution too.
Would you give me some advice? Thanks.

[Mizux]

Hi,

Unfortunately our solver suppose there is only one incident arc for each node (except depot) as well as one output arc...
-> so you can't have the location demand "split" between several vehicles...
i.e. having a vehicle with capacity 2 and an other with capacity 1 to fill a location demand of 3 is not evaluated.

from six.moves import xrange
from ortools.constraint_solver import pywrapcp

def distance(x1, y1, x2, y2):
    # Manhattan distance
    dist = abs(x1 - x2) + abs(y1 - y2)
    return dist

# Distance callback

class CreateDistanceCallback(object):
  """Create callback to calculate distances and travel times between points."""

  def __init__(self, locations):
    """Initialize distance array."""
    num_locations = len(locations)
    self.matrix = {}

    for from_node in xrange(num_locations):
      self.matrix[from_node] = {}
      for to_node in xrange(num_locations):
        if from_node == to_node:
          self.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.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

  def Distance(self, from_node, to_node):
    return self.matrix[from_node][to_node]


# Demand callback
class CreateDemandCallback(object):
  """Create callback to get demands at each location."""

  def __init__(self, demands):
    self.matrix = demands

  def Demand(self, from_node, to_node):
    return self.matrix[from_node]

def main():
  # Create the data.
  data = create_data_array()
  locations = data[0]
  demands = data[1]
  num_locations = len(locations)
  depot = 0
  num_vehicles = 2
  search_time_limit = 400000

  # Create routing model.
  if num_locations > 0:

    # The number of nodes of the VRP is num_locations.
    # Nodes are indexed from 0 to num_locations - 1. By default the start of
    # a route is node 0.
    routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

    # Callbacks to the distance function and travel time functions here.
    dist_between_locations = CreateDistanceCallback(locations)
    dist_callback = dist_between_locations.Distance
    routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

    # Adding capacity dimension constraints.
    demands_at_locations = CreateDemandCallback(demands)
    demands_callback = demands_at_locations.Demand
    VehicleCapacity = 3;
    NullCapacitySlack = 0;
    fix_start_cumul_to_zero = True
    capacity = "Capacity"
    routing.AddDimension(demands_callback, NullCapacitySlack, VehicleCapacity,
                         fix_start_cumul_to_zero, capacity)

    # Solve displays a solution if any.
    assignment = routing.SolveWithParameters(search_parameters)
    if assignment:
      size = len(locations)
      # Solution cost.
      print ("Total distance of all routes: " , str(assignment.ObjectiveValue()), '\n')
      # Inspect solution.
      capacity_dimension = routing.GetDimensionOrDie(capacity);

      for vehicle_nbr in xrange(num_vehicles):
        index = routing.Start(vehicle_nbr)
        plan_output = 'Route for vehicle {0}:\n'.format(vehicle_nbr)
        route_dist = 0

        while not routing.IsEnd(index):
          node_index = routing.IndexToNode(index)
          route_dist += dist_callback(node_index, routing.IndexToNode(assignment.Value(routing.NextVar(index))))
          load_var = capacity_dimension.CumulVar(index)
          plan_output += \
                    " {node_index} Load({load}) -> ".format(
                        node_index=node_index,
                        load=assignment.Value(load_var))
          index = assignment.Value(routing.NextVar(index))

        node_index = routing.IndexToNode(index)
        load_var = capacity_dimension.CumulVar(index)
        plan_output += \
                  " {node_index} Load({load})\n".format(
                      node_index=node_index,
                      load=assignment.Value(load_var))
        plan_output += 'Distance of the route {0}: {dist}\n'.format(vehicle_nbr, dist=route_dist)
        plan_output += 'Demand met by vehicle {0}: {load}\n'.format(vehicle_nbr, load=assignment.Value(load_var))
        print (plan_output , '\n')
    else:
      print ('No solution found.')
  else:
    print ('Specify an instance greater than 0.')

def create_data_array():

  locations = [[10, 10], [10, 0], [20, 10], [10, 0]]

  demands =   [       0,       2,        2,        2]

  data = [locations, demands]
  return data

if __name__ == '__main__':
  main()

output:

No solution found.

if I change to num_vehicles = 3 thus a solution is found one vehicle/location...

Total distance of all routes:  60 

Route for vehicle 0:
 0 Load(0) ->  1 Load(0) ->  0 Load(2)
Distance of the route 0: 20
Demand met by vehicle 0: 2
 
Route for vehicle 1:
 0 Load(0) ->  2 Load(0) ->  0 Load(2)
Distance of the route 1: 20
Demand met by vehicle 1: 2
 
Route for vehicle 2:
 0 Load(0) ->  3 Load(0) ->  0 Load(2)
Distance of the route 2: 20
Demand met by vehicle 2: 2

[shinkisan]

@Mizux
Hi, thank you and glad to see your reply. I was just trying a temprary way to solve my problem, by split a max node to 2 nodes and assign them the same loacations if no solution found. here is the modifield code:

from six.moves import xrange
from ortools.constraint_solver import pywrapcp
import math

def distance(x1, y1, x2, y2):
   # Manhattan distance
   dist = abs(x1 - x2) + abs(y1 - y2)
   return dist

# Distance callback

class CreateDistanceCallback(object):
 """Create callback to calculate distances and travel times between points."""

 def __init__(self, locations):
   """Initialize distance array."""
   num_locations = len(locations)
   self.matrix = {}

   for from_node in xrange(num_locations):
     self.matrix[from_node] = {}
     for to_node in xrange(num_locations):
       if from_node == to_node:
         self.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.matrix[from_node][to_node] = distance(x1, y1, x2, y2)

 def Distance(self, from_node, to_node):
   return self.matrix[from_node][to_node]


# Demand callback
class CreateDemandCallback(object):
 """Create callback to get demands at each location."""

 def __init__(self, demands):
   self.matrix = demands

 def Demand(self, from_node, to_node):
   return self.matrix[from_node]

def main(create_data_array_fun):
 create_data_array = create_data_array_fun
 # Create the data.
 data = create_data_array()
 locations = data[0]
 demands = data[1]
 num_locations = len(locations)
 depot = 0
 num_vehicles = 2
 search_time_limit = 400000

 # Create routing model.
 if num_locations > 0:

   # The number of nodes of the VRP is num_locations.
   # Nodes are indexed from 0 to num_locations - 1. By default the start of
   # a route is node 0.
   routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
   search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()

   # Callbacks to the distance function and travel time functions here.
   dist_between_locations = CreateDistanceCallback(locations)
   dist_callback = dist_between_locations.Distance
   routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

   # Adding capacity dimension constraints.
   demands_at_locations = CreateDemandCallback(demands)
   demands_callback = demands_at_locations.Demand
   VehicleCapacity = 3;
   NullCapacitySlack = 0;
   fix_start_cumul_to_zero = True
   capacity = "Capacity"
   routing.AddDimension(demands_callback, NullCapacitySlack, VehicleCapacity,
                        fix_start_cumul_to_zero, capacity)

   # Solve displays a solution if any.
   assignment = routing.SolveWithParameters(search_parameters)
   if assignment:
     size = len(locations)
     # Solution cost.
     print ("Total distance of all routes: " , str(assignment.ObjectiveValue()), '\n')
     # Inspect solution.
     capacity_dimension = routing.GetDimensionOrDie(capacity);

     for vehicle_nbr in xrange(num_vehicles):
       index = routing.Start(vehicle_nbr)
       plan_output = 'Route for vehicle {0}:\n'.format(vehicle_nbr)
       route_dist = 0

       while not routing.IsEnd(index):
         node_index = routing.IndexToNode(index)
         route_dist += dist_callback(node_index, routing.IndexToNode(assignment.Value(routing.NextVar(index))))
         load_var = capacity_dimension.CumulVar(index)
         plan_output += \
                   " {node_index} Load({load}) -> ".format(
                       node_index=node_true_node_dict[node_index],
                       load=assignment.Value(load_var))
         index = assignment.Value(routing.NextVar(index))

       node_index = routing.IndexToNode(index)
       load_var = capacity_dimension.CumulVar(index)
       plan_output += \
                 " {node_index} Load({load})\n".format(
                     node_index=node_true_node_dict[node_index],
                     load=assignment.Value(load_var))
       plan_output += 'Distance of the route {0}: {dist}\n'.format(vehicle_nbr, dist=route_dist)
       plan_output += 'Demand met by vehicle {0}: {load}\n'.format(vehicle_nbr, load=assignment.Value(load_var))
       print (plan_output , '\n')
   else:
     print ('No solution found.Trying split node...')
     max_value = max(demands)
     max_index = [i for i,v in enumerate(demands) if v == max_value][0]
    
     # generate new demands and locations
     half_max_value = math.ceil(max_value/2)
     if max_index == 0:
       new_demands = [half_max_value, max_value - half_max_value] + demands[1:]
       new_locations = [locations[0]] * 2 + locations[1:]
     else:
       new_demands = demands[:max_index] + [half_max_value, max_value - half_max_value] + demands[(max_index + 1):]
       new_locations = locations[:max_index] + [locations[max_index]] * 2 + locations[(max_index + 1):]

     print('new_demands:',new_demands,'new_locations:', new_locations)
     
     # record true node
     for i in range(len(new_demands)):
       if i > max_index:
         node_true_node_dict[i] = node_true_node_dict[i] - 1

     new_create_data_array = lambda : [new_locations, new_demands]
     main(new_create_data_array)
 else:
   print ('Specify an instance greater than 0.')

   
def create_data_array():

 locations = [[10, 10], [10, 0], [20, 10], [10, 0]]

 demands =   [       0,       2,        2,        2]

 data = [locations, demands]
 return data
 
# define the node -> true_node dict
class Mydict(dict):
 __missing__ = lambda self, key: key
 
node_true_node_dict = Mydict()

if __name__ == '__main__':
 main(create_data_array)

and the result is:

Route for vehicle 0:
0 Load(0) ->  2 Load(0) ->  1 Load(2) ->  0 Load(3)
Distance of the route 0: 40
Demand met by vehicle 0: 3


Route for vehicle 1:
 0 Load(0) ->  3 Load(0) ->  1 Load(2) ->  0 Load(3)
Distance of the route 1: 20
Demand met by vehicle 1: 3