Vehicle Routing Problem with orders taking multiple days

4397
8
Jump to solution
08-05-2014 07:55 AM
Highlighted
New Contributor

Hello all,

I am attempting to show offthe power of Network Analsyst to my management.

Basically, we have a contract for over 100 sites across six that we need to survey, with each site estimated to take between 0.5 and 5 working days.

I need to set up a Vehicle Routing Problem where a single order can be broken up into multiple days (the most realistic model would have them working for 8 hours, then taking a 16 hour break) and they return to the depot at the end of each week, rather than at the end of each day.

Has anyone done anything like this that can give me some guidance?

Thanks in advance!

Reply
0 Kudos
1 Solution

Accepted Solutions
Highlighted
by
Occasional Contributor

Yes, you can use breaks to model it as a multiple day problem.  There are a few things you need to be aware of:

  • Breaks: Set the TimeWindowStart with date information, for instance, 8/4/2014 5pm, 8/5/2014 5pm, etc. TimeWindowEnd can be set the same value as TimeWindowStart. Each route can have up to 5 breaks. For your weekly schedule, you will need at least 4 breaks.
  • Since Breaks have the date information in time window, you will need to make sure all the other NA class Time Windows have date information as well, such as Routes “EarliestStartTime” and “LatestStartTime. ”
  • Please make sure in layer properties->Analysis Settings-> Default Date is set to a specific date, i.e. 8/4/2014.

In the solution, you might see some route runs over a couple of days, while the others might only be one day long unless you force to balance the routes with special settings (such as restricting the MaxTotalTime on route). For the less than one week route, the unused breaks will be added to the end of route. You will need to remove them afterwards to get a clean report.

Thanks.

Anna

View solution in original post

8 Replies
Highlighted
by
Occasional Contributor

Yes, you can use breaks to model it as a multiple day problem.  There are a few things you need to be aware of:

  • Breaks: Set the TimeWindowStart with date information, for instance, 8/4/2014 5pm, 8/5/2014 5pm, etc. TimeWindowEnd can be set the same value as TimeWindowStart. Each route can have up to 5 breaks. For your weekly schedule, you will need at least 4 breaks.
  • Since Breaks have the date information in time window, you will need to make sure all the other NA class Time Windows have date information as well, such as Routes “EarliestStartTime” and “LatestStartTime. ”
  • Please make sure in layer properties->Analysis Settings-> Default Date is set to a specific date, i.e. 8/4/2014.

In the solution, you might see some route runs over a couple of days, while the others might only be one day long unless you force to balance the routes with special settings (such as restricting the MaxTotalTime on route). For the less than one week route, the unused breaks will be added to the end of route. You will need to remove them afterwards to get a clean report.

Thanks.

Anna

View solution in original post

Highlighted
New Contributor III

I need to be able to set up multidays route. I am looking anywhere to see if I could find an exemple of a setting for a it, but with no chance.

The only post I have find is yours. 
Could you direct me with a simple exemple or some link with a bit more information on the way to do it. 

The prolems I try to solve are quite simple 20 or 30 deliveries with 6 drivers but that covered long truck distance thus that could only be done over 3 to 4 days. 

If you could give me some more tips on general multiday routing I would be grateful!! 

Thanks in advance.

Best Regards,

Reply
0 Kudos
Highlighted
Esri Contributor

Making a multi day routing problem is pretty similar to making a VRP problem with breaks.  Here is a tutorial for adding in breaks. Exercise 7: Servicing a set of orders with a fleet of vehicles—Help | ArcGIS Desktop 

The big difference as Anna points out above is that to make it multi day you need to specify both the day and time throughout the whole problem set up.  That would include the default date in the Analysis Settings of the layer properties, any time windows, and start and end times.

Remember the solver allows for 5 breaks per route (that would include both lunch and overnight type breaks) so keep that in mind when setting up for multiple days.

Reply
0 Kudos
Highlighted
New Contributor II

Hi Heather, I see this thread is getting long in the tooth, but here goes...!

So your previous advice has helped me break up my Routes (thank you!), save for one thing: the OP mentioned having the crew return to their Depot at the end of each day, or 'break'.  I attempted this by 'Breaks > Load Location...' , but unfortunately, the VRP solved by just having the driver hold between two Orders for the duration of ServiceTime.  Is there a way to force a driver to a location for their Break (In my case, we need to simulate a bathroom break where the crew is forced to return to 'home base' because of COVID restrictions).

Thank you for your time!

Reply
0 Kudos
Highlighted
Esri Contributor

Hi Justin,

Great question. There are a few options for requiring the routes to go back to the depot for a break and they each have their benefits so It might be worth trying both to see what works best for you (and we would love feedback on what you end up doing). 

1.) One option is to break the work day into multiple routes per person setting the time portions of those routes appropriately for the time of day such as Justin_Morning has a start time of 8 am and a max total time of 2 hours, Justin_LateMorning has a start time of 10:15 am and a max total time of 1.75 hours, Justin_afternoon has a start time of 1:00 pm with a max total time of 2.75 hours, and Justin_LateAfternoon has a start time of 3:00 pm and a max total time of 2 hours. The start and end depot for all of them would be back at the office forcing the routes for each driver to go back to the office for a morning break, lunch break, and afternoon break. One concern for this is that it will grow the size of the problem substantially, so this works well for smaller fleets but if you have a large problem to begin with it could make the problem too large. This should still do a good job of filling up the routes to get work done efficiently.

2.) Another option when needing a break to take place at a specific location is to insert it as an order. You can use the TimeWindowStart1, TimeWindowEnd1, and MaxViolationTime1 fields to indicate the time of the break and the ServiceTime to indicate how long it is. You will need one order for each route for each break that is needed and then can pair each with the route using the specialties. So following the example above you would have three orders Justin_MorningBreak, Justin_LunchBreak, and Justin_AfternoonBreak with the appropriate time windows. They would each be given and OrderSpecialties value of Justin and then the route Justin would have a RouteSpecialties of Justin. If you see that the solver is not assigning these orders which is a possibility if you have too much work for the day, then I would add in a revenue value for these orders that is more then the revenue for other orders in the problem combined, that will signify to the solver to definitely go to that order.

Hope that helps,

Heather

Reply
0 Kudos
Highlighted
New Contributor II

Hi Heather! Thanks for the quick response - I really appreciate that!

So far I'm liking option 1, mostly because that's exactly the 'route' (lol) I was taking since writing yesterday! Knowing that our 3 trucks take approx. 5 days to complete their work, I'm setting things up such that there are 3 trucks x 2 runs (morning and afternoon, using a MaxTotalTime of 180 min for each) x 5 days (for now - but this can be expanded if Orders are not solved for, or vice versa), for a total of 30 Routes.

Well enough - but I'm now running into 2 issues which I hope to illustrate with this screen capture, after solving for Day 1 (reds = Route 1, greens = Route 2, blues = Route 3):

One is the Solver seemingly skipping what would seem to be obvious Orders, like those circled in Maroon. The other I call "the spaghetti factory", where the Solver entangles Routes while 'leap-frogging' over neighbourhoods, or placing Orders in a single street into different Routes (circled in fuchsia); or, by placing orders in wildly disparate areas (circled in teal).  While I can somewhat understand how this could work in the real world, I know my clients prefer to give their crews discrete route areas. I'd used Route Areas in a previous version of this VRP to model just the 3 overall Routes and it did so beautifully and quickly (by an order of magnitude over solving without Route Zones!), but the thought of eyeballing clusters and then manually creating 30 Routes is....nope. I had just found this other thread where someone recommended using L-A :

but I've never used L-A before and I'm having trouble coming up with the correct usage of it to accomplish this. My most recent attempt was actually to use the ND_Junctions as Candidate Facilities, and solve for 30 clusters that have a cumulative travel cost of 180 minutes to surrounding demand points...? 

I know there's a lot of things to cover here, but any help or points in the right direction would be life-saving - aaaand I'd get to keep my hair on my head instead of the floor around me lol!!!!   

Thanks again Heather!

Reply
0 Kudos
Highlighted
Esri Contributor

Hi Justin,

I'm all for keeping hair on heads instead of on the floor. Let's see if we can get your model working well again.

I again see two options depending on a few settings and preferences for you. 

1.) Since you liked the route zone option you could again go with this defining a region for each truck and have multiple copies of that polygon for each of the minor routes you are making for that truck to divide the work among days and morning/afternoon. This might run into similar skipped orders or routes overlapping each other within the region but they would then at least all be done by the same driver and only require defining three zones.

2.) The other options is to use dynamic seed points. This will tell the solver to emphasize clustering orders onto routes based on geographic regions so they are better clustered into regions over looking for the minimum cost. It usually does a really good job of minimizing cost also but just so you understand the difference in the emphasis for the heuristic with this setting. This is set up differently depending on how you are solving the problem. If you are using an ArcMap VRP layer you will need to add a point feature for each of the 30 routes into the map in the feature class called Route Seed Points. It does not matter where these points are, they just have to be in the map and the solver will move them around to the best location for the center of that cluster. You will need to specify the RouteName and then make SeedPointType set to Dynamic for all of them. If you are using the Solve Vehicle Routing Problem GP tool, or one of the ways to call a service then simply make sure that Spatial Cluster Routes is set to True. This will not put any emphasis on keeping the trucks in the same region for all 10 of the minor routes for days and morning/afternoon. If they are all essentially the same you could not predefine which route goes for which truck and then look at the output afterwards and group the routes to trucks based on what is close by geographically.

Let me know if you have other questions,

Heather

Reply
0 Kudos
Highlighted
New Contributor II

Hi Heather, I went with the Seed Points method, and after cleaning up a little...

...success! Thank you so much!  Y'know what? I'd cursorily looked into Dynamic Seed Points but was under the mistaken impression that, while - yes - I could place them anywhere, best practice would be to place them where I thought they <should> go (i.e eyeball my own clusters or derive them some other way and load them into Seed Point Layer), and that the extent of their dynamism was only that they'd shift <around> the spot I placed them.  Thank you for pointing me in the right direction Heather!

Cheers and take care out there!

Justin

Reply
0 Kudos