How to implement Gate node?

[Kazi Ahsan]

Hello,

  I remember one of my past threads where Mizuk had suggested implementing a Gate node. Gate node is extremely useful where we can easily add many useful constraints.I would like to share my understanding of Gate node and how I am planning to implement it in my current program.

   The idea of Gate node comes as - The vehicle can not directly access the pickup node or delivery node of a location. It has to go through the Gate node to pickup or delivery. The vehicle has to visit the exit gate node as well as leave a location. Every location has 2 gate nodes one for entering and another for the exit.
  
   In order to implement a Gate node, I have taken an example of initial inputs so that I can explain how my current program works.
 
   3 loads (Load 1, Load 2, Load3) and
   2 locations (Location A and Location B)and
   2 vehicles (Vehicle X, Vehicle Y).
   
   My program produces one of the below solutions

   Vehicle X takes Load 1 and Load 2
   Vehicle Y takes Load 3.

   I am duplicating nodes for each pickup and delivery load as below before calling routing.AddPickupAndDelivery function as below

    Load 1  pickup -  Location A delivery Location B   [1,4]
    Load 2  pickup -  Location B delivery Location B.  [2,5]
    Load 3  pickup -  Location B delivery Location B. [3,6]

    data.pickups_deliveries = [[1,4], [2,5], [3,6]]
    for request in data.pickups_deliveries:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)

   
   If I want to implement a gate node, then I think I need to produce 2 gate nodes (one for entry and another for exit) for each pickup node and the same for each delivery node which will give me the following list of pairs

    data.pickups_deliveries = [[10,1],
                               [11,2],
                               [12,3]

                               [1,13],
                               [2,14],
                               [3,15],

                               [16,4],
                               [17,5],
                               [18,6],

                               [4,19],
                               [5,20],
                               [6,21]]

    From the above, node 10, node 11, node 12 to enter Location A and Node 13, node 14, node 15 to exit location A for pickups.

    Node 16, node 17, node 18 to enter Location B, and Node 19, Node 20, and Node 21 to exit Location B for delivery.

  (I also need to include gate nodes when generating distance and time matrixes. Distance between gate nodes in my case is zero. But once entered I can add rest time, service time etc once it enters any gate node in my time matrix.)

    The vehicle can pick up multiple loads or re-enter the same location after drop off but any vehicle for example  Enters from Node 10, it needs to stop re-enters Node 11 as the next node. The same is true for departure which gives me the following restriction lists when implementing the Gate node.

1.     Restriction in among Node 10, Node 11, and Node 12.
2.     Restrictions among Node 13, Node 14, Node 15
3.     Restrictions among Node 16, Node 17, Node 18
4.     Restrictions among Node 19, Node 20, Node 21

  Please feel free to advise.

Kind Regards

Kazi
   

[blind.lin...@gmail.com]

Hi Kazi,

Thanks for sharing this explanation. Have you implemented and run this yet?

I have one question, related to the explanation, not the method. What does it mean to pickup at location B and deliver to location B? What is the real world problem that you are modeling there?

Regards,

James

-- 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/0604a949-d124-462d-8ecc-320f9c76df8cn%40googlegroups.com.

--
James E. Marca
Activimetrics LLC

[Kazi Ahsan]

James,

   Welcome. Really sorry for the confusion from my typos. What I meant is as below

   Load 1  pickup -  Location A   delivery -  Location B   [1,4]

   Load 2  pickup -  Location A   delivery  - Location B   [2,5]
   Load 3  pickup -  Location A   delivery -  Location B   [3,6]

   A vehicle can pick up one or multiple loads from a location. In either case, there is location service time which only gets added only once when a vehicle enters a location. We call it Consolidated Location service time. We have already implemented this feature successfully inside time callback. 

   

  I also want to explore the gate node concept so that I can add this consolidated location service time in the gate node.

   

Kind Regards

Kazi

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/YdhhC00QbF7Z2bvg%4050e47090dcd7.

[Kazi Ahsan]

James,

I did not implement it yet. I am planning to do it and let you know. 

Kind Regards

Kazi

[Kazi Ahsan]

Hello,

     Has anyone implemented the "Gate Node concept"?  

     

     For more details about the Gate Node concept see one of my past question (https://groups.google.com/g/or-tools-discuss/c/uyPwvCoG7Js/m/FbkQEU9HMwAJ). Also by searching forums, I see Gate Node has been suggested on different occasions as a solution from OR team. Surprisingly I did not find any implementation of Gate node or anything similar either here or web!

     

     So I came up with my own implementation plan of  Gate Node in this thread. Before I write some code, I would like to know from anyone who has already implemented the Gate node in their project?

Kind Regards

Kazi