Select to view content in your preferred language

Vehicle Routing Problem - Return to Order

144
4
Jump to solution
a week ago
ClintSteeves
Emerging Contributor

I’m trying to use the Vehicle Routing Problem to create a strategy for making deliveries. I’ve built a working network dataset. I have depots, orders, and routes set up. But it seems like it has a serious limitation regarding vehicle capacity vs delivery requirements.

Background Information:

  • If my truck capacity is higher than the individual delivery amounts, the analysis works as intended.  
  • If my truck capacity is higher than the individual delivery amounts, but the total delivery amount is higher than the truck capacity, the truck will return to the depot to refill as needed (using Route Renewal Table). This works as intended.
  • If my truck capacity is lower than the individual delivery amounts, the analysis skips those delivery locations.
  • I currently have no limitations on the amount of time nor distance for transport, delivering, loading, etc. 

 

What I’d like:

  1. Have the analysis realize that one truck can go to the same order location more than once to fulfill the delivery amount.
    • For example, my truck has a capacity of 1 unit. The delivery location requires 3 units. I’d like the analysis to realize the truck can make that delivery with 3 trips.
    • Setting up the depot as an available Route Renewal point does not alleviate the issue.
  2. Have the analysis allow more than one truck to go to a delivery location to fulfill the delivery
    • For example, if I have 3 trucks, each with a capacity of 1 unit, I’d like to send all 3 trucks to a location if it requires 3 units delivered. 
    • If the location only requires 2 units, let's send 2 trucks there and send the 3rd truck elsewhere
    • Normally, sending multiple trucks to make a single delivery would probably not be ideal, but in my case, it is absolutely necessary to deal with the quantities of goods to be delivered within my timeframe.

My (Untested) Ideas:

  1. Set up multiple routes to emulate multiple trucks:
    • Route 1 has a capacity of 1 unit (therefore 1 truck), and will only service Orders requiring fewer than 1 unit
    • Route 2 has a capacity of 2 units (therefore 2 trucks), and will only service Orders requiring 1 to 2 units
    • and so forth
  2. Use Generate Points along Line Tool to create Order locations:
    • A bit of background information again: the delivery locations are actually lines along which multiple deliveries will be made, but I'm using the centroids of these lines as my Order locations for the purposes of the network analysis
    • My idea is to generate points at regular intervals to represent the locations along the line where the deliveries will actually be made. So for a line requiring 4 units, I will generate 4 points along the line with a delivery quantity of 1 unit each.
    • This would allow a single truck with a capacity of 1 unit to return to that delivery location 4 times rather than skipping it in the analysis.

Neither of these ideas will produce perfect results, and they'll require some post-analysis interpretation to manage the real-world deliveries of the goods. But I'm hoping they'll be close enough. I've wondered about using each DeliveryQuantity field to represent a different truck within the same route too, but haven't gone beyond surface thoughts with that.

It would be really nice if there was a Yes/No field in the orders to allow for return trips and/or multiple vehicles, but alas.

If anyone has any thoughts or suggestions about any of this, I’d really appreciate it. (Sorry this is a very long post)

0 Kudos
1 Solution

Accepted Solutions
GarrettMelvin
Occasional Contributor
0 Kudos
4 Replies
GarrettMelvin
Occasional Contributor

You mentioned a delivery location requires 3 units, and it would be acceptable for three trucks with a capacity of 1 unit each to service that location.  Have you tried creating three orders with a delivery amount of one unit each for that location?  The points would be coincident, this should allow three different trucks to service the one location, or allow the same truck to service the location with renewals.  If the location only requires 2 units, I think you would set up the same scenario-two coincident orders with 1 unit each.  

0 Kudos
ClintSteeves
Emerging Contributor

I did just finish solving the VRP using a very similar method (2 hour runtime for 1 of my 7 depots). I haven't gone through the results very comprehensively yet, but I think I'm on the right track. This is what I did (I'll admit, it's a bit convoluted):
-Calculated the total number of deliveries required by each line segment based on the capacity of an individual truck, rounded up to the nearest integer. 

-Used that integer and the entire line length to calculate the "line length between deliveries"

-Generated points along the lines using the "line length between deliveries" as the distance, but did not include start/end points. This yielded points equivalent to n-1 required deliveries along each line. 

-Added a final point at the end vertex, and set the required delivery quantity for that point to be the remainder from the previous calculation. Adding together this delivery quantity and the previous delivery quantities gives me the exact total required delivery for that line. 

-Set up a number of routes equal to the approximate number of days the entire delivery project should take based on other analyses and historical data. Each route has a delivery capacity of the number of trucks multiplied by the capacity of each truck to emulate sending multiple trucks at a time. 

 

It yielded results far better than I was getting before, but I can see some problems with it just for my specific case. I'm going to keep tinkering away with it

0 Kudos
GarrettMelvin
Occasional Contributor
0 Kudos
ClintSteeves
Emerging Contributor

That's extremely similar--good catch. I'll mark this as resolved and refer to that one. Thanks for the help