VRP-Order Pair with Three Orders

[GarrettMelvin]

Our scenario has a truck leaving the depot with an empty roll-off garbage container.  The truck will go to a customer location, swap the full container with an empty container, carry the full container to a landfill to empty, then return to the depot to sanitize the container.  At this point the truck is available for a second run of the same setup.  

We tried adding three orders (pickup location "A", dump location "B", sanitize location "C"), then adding two order pair records (FirstOrder "A"+SecondOrder "B", FirstOrder "B"+SecondOrder "C").  The solver returned an error "Order pairs has a FirstOrderName value for an order that is already paired."  

How can we setup a VRP to solve this scenario?  

@HeatherMoe @RodneyConger @RobertHaley @KelseyMills 

[RodneyConger1 · Accepted solution]

Hi @GarrettMelvin   The VRP doesn’t support chaining pairs. You might try using a single pair that links the customer location with the landfill and force the trip back to the depot using capacities. Your landfill order fills the truck and forces a renewal. 

[GarrettMelvin]

Thanks @RodneyConger1. We created a "force landfill" order for each customer pair order, but the solve did not return a feasible solution (some routes serviced only "force landfill" orders, some routes serviced customer orders without a "force landfill").  We changed the setup to have one "force landfill" order for each route, and setup specialties so they would stay only one per route.  We then added in time windows, revenue, and renewals, and the resulting solve produced an output where the "force landfill" orders were (mostly) in the feasible sequence.  The only instances of infeasible sequence was for routes that were unable to make a 2 customer serviced route, in which case a sanitize run is unnecessary.  Thank you.

[RodneyConger1 · Accepted solution]

Hi @GarrettMelvin  Something along the  here is what i had in mind. Each of the points below is labeled with the order name and the solved sequence. The Depot is labeled with the sequences of the depot visits (1, 5, and 9)

The route has a capacity of 1. It begins at the depot empty. it travels to "PU2" and picks up an order with pickup quantity = 1. PU2 is paired with DEL2 at the landfill, it visits there next with sequence 3. After if services the delivery at the landfill, it picks up another order (assigned by the VRP) at the landfill with pick up quantity 1 - which fills the vehicle again. Next it visits the Depot to renew as sequence 5. It then travels to PU1 to fill the capacity again. PU1 is paired with DEL1 at the landfill and that's sequence 7. Another landfill order with pick up quantity 1 is serviced as sequence 8 and that forces the vehicle back to the depot to renew again as sequence 9.

[GarrettMelvin]

Thank you @RodneyConger1.  I would add that with multiple routes and additional customers, adding in LF orders for each route and grouping together through specialties helps to prevent routes from servicing only LF orders.  

We have a similar working use case where pickups are made at one customer, delivered to another customer, after which a truck wash at the depot is required.  There are multiple locations for pickup and delivery customers.  Our approach is a two-solve solution.  First we add all routes with a max order count of 4 (knowing that most of the time only two pickups and deliveries is feasible with then available time constraints); add pickup and delivery orders with assignment rule override, quantities of 1, and order pairs; and add route renewals.  We also add in a wash order at each delivery location with a pickup quantity of 1 and an assignment rule of exclude.  The naming convention is order1_p (for pickup), order1_d (for delivery), and order1_w (for wash).  The first VRP solve assigns two sets of paired orders to each route.  We update assignment rule for routed orders to Preserve Route, and route max order count to 6.  We created a script that identifies route name for each delivery order, and updates the wash order route name to the appropriate value, and updates assignment rule from exclude to preserve route.  We then run a second solve, and the output routes all wash orders after the pickup/delivery pair, and forces the renewal, essentially creating a three "paired order" situation.  

Do you have any suggestions to improve this work flow?  

[RodneyConger1]

Hi @GarrettMelvin Yeah, the thing that would make your problem easier to solve would be the ability to chain pairs and it's simply is not supported. I'll bring it up with the Dev team, but it's very unlikely it would be added as an enhancement to the existing VRP - maybe a new VRP someday. 

So where is the truck wash happening? at the dump site? If it's at the dump site, do you even need an order to represent it? If the truck is always washed after the dump, you could just add the washing service time to the dump. If washing occurs somewhere other than the dump, you could also add a average travel time to and from the washing site. A post-process could insert the washing order into the route after your primary pickup and delivery order-pair solve is done.

[GarrettMelvin]

The truck wash occurs back at the depot.  Do I understand correct that you recommend to run a VRP with only pickup and deliver order pairs, increase the service time of the delivery order, then run a post script to insert orders at the wash location?  Would you keep the max order count at 5? (two pickups, two deliveries, and one intermediate wash given the end depot visit models the final wash).  

[RodneyConger1]

Hi @GarrettMelvin the original suggested solution to this problem should cover the wash at the depot. Your vehicle has a capacity = 1, so each order it picks up from the dump site forces a renewal at the depot.
Start - empty at the depot
Stop1 - pickup of real order fills capacity: paired order 1
Stop2 - delivery of real order empties capacity: paired order 2
Stop3 - pickup fake order at same location as Stop2 fills capacity
Stop4 - emptying of fake order picked up at Stop3 at the depot as a renewal and the wash occurs

You can put as many of these real and fake orders as needed in the same problem and it should just work.