Vehicle Routing - Force use of all routes/depots

2169
10
07-27-2011 07:03 AM
AmandaWorrell
New Contributor
I am trying to use vehicle routing to distribute environmental inspections amongst all our inspectors.  The vehicle routing problem is only assigning orders to a subset of inspectors, even though this means sometimes not all orders are filled.  Is there a way to force the use of all routes/depots?
Tags (2)
10 Replies
JaySandhu
Esri Regular Contributor
VRP solver should assign all orders. If they are not being assigned then look at the reason why. That is, could the capacity of the trucks or number of orders or maximum work day hours, etc have been exceeded. So look at the reason and change the constraints accordingly. Do note that VRP is designed to lower your overall cost withing the specified constraints.

Jay Sandhu
0 Kudos
DavidWasserman
Occasional Contributor III

Hi Jay,
I am actually having a similar issue. Similar question, how do you force it to use all Routes? I am having a VRP layer with buses with a capacity of 14 and order pairs to particular destinations. I assign multiple routes but not all of them are utilized. Any thoughts on how to make sure they are all used? 
David

David Wasserman, AICP
0 Kudos
HeatherMoe
Esri Contributor

The VRP Solver is set up to take lots of extra routes and then only use what is necessary to most efficiently solve the problem.  If you are wanting all of the routes to be used you can change whichever max value for the routes that makes sense for limiting them.  One that makes sense intuitively without knowing you exact problem is to limit the max order count so that in order to fulfill all of the orders every route needs to be used.  So, for example, if you have 50 orders and 5 routes you could say that each route has a max order count of 12 and then it will force the solver to use all 5 routes to service all 50 orders. 

Another option could be to solve the problem once and see what the total time used for all of the routes and then limit the Max Total Time for a second solve so again all of the routes are needed.  So, for example, if for the first solve three out of the five routes were used and for all three routes a total of three hours were needed to service all of the orders then each route could be given a Max Total Time of 40 mins for the next solve and it should force all five of them to be used.  A similar approach can be used for distance.  The time and distance options would allow for more flexibility in the number of orders each route could go to but it wouldn’t necessarily guarantee all the routes would be used.  It would depend on the way the rest of the problem was modeled and the times and distances between orders but should work for a majority of cases.

Heather

deleted-user-Q-Ku9J1BlYDK
New Contributor II

Hi Heather, 

This helps me reformulate my problem. I know my exact number of orders and buses, so I think I just need to set the MaxOrderCount to be (orders/bus_count)+1 to assume some near equal distribution of effort. I might need to set it to be the minimum of the capacity of the vehicles in case they divide labor in ways that don't make sense. (If I have 20 riders, and the vehicles have a capacity of 12, maybe really we need just need to account for that in some way). I will have to experiment on this. Thanks Heather! I greatly appreciate your assistance. 

David

0 Kudos
DavidWasserman
Occasional Contributor III

Hi Heather, This solved my immediate problem but created more questions. 

Below is a data table of resulting average travel times from the VRP solver. We are trying to create a tool that can help with different scenarios of paratransit ridership coupled with bus allocations (number of routes). The numbers derived here are the averages of the "TotalTime" values for each route. Something we noticed was that for lower ridership outputs we saw some type of solve instability whenever the number of seats surpassed the number of total riders. For example each bus has 14 seats, and as a result our results make sense when we get to 2 buses with 20 riders. When we get to 3 buses though, we essentially could have "1 extra" bus (as 2 buses could pick everyone up  in one load). I am trying to understand conceptually why the average TotalTime could increase when 3 routes are assigned. I have tried a multitude of MaxOrderCount approaches including: 

1. max(Orders/Bus_Count, BusCapacity)

2. max(Orders/BusCount, BusCapacity*.75)

3. Orders/BusCount

Is this a result of how the solver workers? Am I missing a concept? Do you have any ideas on what to check for that causes this instability? 
These results are useful and give us a launching point for future analysis, but I am trying to understand this tools various parameters to determine what is relevant.

Thanks for your help so far! 

David Wasserman, AICP
0 Kudos
HeatherMoe
Esri Contributor

Hi David,

The only thought for explaining this is that based on the distances between the orders and the distance too and from the depot that three routes simply requires more travel time because of how the routes have to be separated to get to all of the orders and then back to the depot.  

Another option for how you determine the max order count could be to do the number of orders / (the number of buses minus one) and then either round down to the nearest whole number or if it comes out to be a whole number subtract one.  This would allow the most flexibility of orders per route while still forcing all buses to be used.  That said I don't see anything wrong with the options that you have tried and it seems like you have things up and running well so if none of these thoughts help you understand why the solver behavior spiked at that point it could just be that because we use a heuristic that maybe that particular set of parameters just doesn't perform as well as the others.  Although we try to make our heuristic work well for as many different scenarios as possible its just not possible to make it perfect for all.

Hope this helps,

Heather

0 Kudos
DavidWasserman
Occasional Contributor III

Hi Heather, 

Thanks for your thoughtful reply. I will give your suggestion a try. I think that metric for orders makes sense. Is the thought there that, if it is more optimal, it will use the same bus to grab more passengers if it makes sense (locations are clustered close to where they are delivered for example)?

A lot of the trouble is I am doing this all programatically with Python and Pandas (so 40 VRP runs in total for 2 destinations), which makes it hard to QAQC the 160 output files. 

I think the next thing we want to investigate is determining the average wait time from the passenger's perspective. This could theoretically be done by using the timestamps in the output visited stops correct? Does it make sense to use the default times it allocates or should I determine when orders are put in myself?  Are there explicit settings that need to be changed to simulate this? 

At this point I might owe you a beer at the next UC. 

Thanks, 

David

David Wasserman, AICP
0 Kudos
HeatherMoe
Esri Contributor

Hi David,

For the max order count portion of your discussion, it is really about what problem are you trying to solve.  If you want to make the solver lean more towards balanced work loads for your buses then the metrics that you described would make sense because they cap each truck's order count sooner.  This could lead to longer distances/times for the entire problem though.  The option I suggested allows each route to have more stops (off coarse you still need to limit it to the capacity of the buses if it isn't captured in the capacity of the routes).  By giving more allowed stops to the routes the solver has more freedom to be able to capture all of the orders in an area with just one bus instead of having to send two into the area.  This can create solutions that have shorter overall distances and times but could potentially leave that last required bus with very little work.  This is more a business decision at this point of figuring out what works best for your problem and look at the results you get from some test cases and see what makes the most sense.

As for the discussion on the passenger's wait time, I'm not sure I fully understand what you are asking.  Do the passenger's have time windows in your model?  If so you can use the ViolationTime field to see if any of the time windows were not meet.  If you aren't running with time windows in the model, there is an output field in the orders fc for the ArriveTime which shows when the route is scheduled to get to each order.  You could extract this and compare it to the time you have for each passenger.  

You ask "Does it make sense to use the default times it allocates or should I determine when orders are put in myself?"  I'm not sure what you are asking here.  The only thing I can come up with is that you could give orders a time window to get the solver to be at the orders within a certain time frame but I'm not sure if that is what you are trying to ask.  

Thanks,

Heather  Moe

0 Kudos
DavidWasserman
Occasional Contributor III

Understood thanks for clarifying. 

I don't really want a time window as a constraint, but a measurement of the passengers travel time from the start of their trip to the end at their destination. So for the person involved it would be (wait time+ service time+ travel time for delivery). I thought I could use the ArriveTime you mentioned. My concern is for ordered pairs I am not sure what the passengers "start time" is. If it varied at all etc.

My uncertainties are :

 I am not sure is if everyone is starting their trip at 8 AM or if I need to compare the ArriveTimes of the pick up order and the delivery order? If it is 8 AM I just need to say ArriveTime- 8 AM, but if it is pick up and delivery pairs I need to compare the two pairs (ArriveTime of  Drop off-  ArriveTime of Pickup) times correct? 

David

David Wasserman, AICP
0 Kudos