Google OR-tools Pickups and deliverys Multiple Visits of same node

Question

I'm currently using C# and the Google-Or-Tools to solve an VRP problem

• Problem Statement:

I have one Depot node 0 and 3 location nodes (1,2) (1',3) (4,5). Location 1 and 1' is same location (2 order).

VehicleCapacities: 10

At location 1 I need to pickup 10 units

At location 2 I need to dropoff 10 units

At location 1' I need to pickup 5 units

At location 3 I need to dropoff 5 units

Run the program, it displays the following routes

 Route 1: 0 Load(0) -> 1 Load(10) -> 2 Load(0) -> 1' Load(5) -> 3 Load(0) -> 4 Load(10) -> 5 Load(0)

https://ibb.co/3sYxQYH (Sorry, I can't upload image)

My question is how to use or-tools to implement a solver that:

• Allows each location only visit one time

  example

  Route 1: 0 Load(0) -> 1 Load(10) -> 2 Load(0) -> 4 Load(10) -> 5 Load(0)

  Route 2: 0 Load(0) -> 1' Load(5) -> 3 Load(0)

• Location can visits multiple when it's continuous (1 need to pickup 5 unit, 1' need to pickup 5 units)

example: 0 Load(0) -> 1 Load(5) -> 1' Load(10) -> 2 Load(5) -> 3 Load(0) -> 4 Load(10) -> 5 Load(0)

Answer 1

1. To limit the route to visit only one node among a list (here [1, 1']).
   I would:

   • Create a "location_token" RoutingDimension with:

     • Force all slack to 0
     • Set capacity vehicle to at least 1
     • Force start cumul to zero
     • increase by one when visiting 1, 1'
       note: use an unary callback like in the capacity sample (https://developers.google.com/optimization/routing/cvrp#demand)

     token_transit_callback(from_index):
       from_node = manager.IndexToNode(from_index)
       # return one upon visiting 1 or 1'
       if from_node in (one_node, one_prime_node):
           return 1
       return 0
     
     token_transit_callback_index = routing.RegisterUnaryTransitCallback(
           token_transit_callback)
     routing.AddDimension(
       token_transit_callback_index,
       0, # no slack
       1, # vehicle capacity
       True, # force start cumul to zero
       'location_token')
     

   • Add a constraint to visit 1 or 1' you need the "location_one_token" dimension to be zero (i.e. you didn't already visit some nodes in the list).

     node_list = [one_node, one_prime_node] # 1, 1'
     location_token_dim = routing.GetDimensionOrDie('location_token')
     for node in node_list:
         index = manager.NodeToIndex(node)
         routing.Solver().Add(location_token_dim.CumulVar(index) < 1)
     

2. If you want to allow 1 -> 1' or 1' -> 1, Then I would use a regular callback with the usual two parameters from_index and to_index.
   The trick will be to not increase the token count if for transit(1, 1') and transit(1, 1`) something like this:

   token_transit_callback(from_index, to_index):
       from_node = manager.IndexToNode(from_index)
       to_node = manager.IndexToNode(to_index)
       out = 0
       # return one upon visiting 1 or 1'
       if from_node in (one_node, one_prime_node):
           out = 1
       # except if next node is 1 or 1'
       if to_node in (one_node, one_prime_node):
           out = 0
       return out