Grouped Relative Sequencing of Stops

Question

Is it possible to group together sets of stops and enforce "relative" sequencing by a category?  Specifically, we would like plan a route to service a subset of stops first, then service the remaining stops.  The reason is to honor a business specific rule.

For example, a route has ten stops numbered 1 through 10.  Assume the most optimal route is running in numbered sequential order (stop 1, 2, etc, 10).  We would like to create a route where the odd number stops are optimally sequenced first, then the even numbers are optimally sequenced after the last odd number stop.  Ideally we would like to do this in Route and VRP.

@RodneyConger @RobertHaley @HeatherMoe @KelseyMills

robhaley · Answer

I spent quite a bit of time on this problem a couple years ago but we have added some capabilities to our tech now that we did not have then.

However, this is not a problem for the faint of heart. One idea might be to experiment with the last mile delivery solver. It has some things it cannot do, like ordered pairs. But it can do some cool stuff, among them support no depot. One idea I had was to use LMD to solve a number of micro routes constrained by something like time or order count or something and then create some logic that knows how to combine them afterwards by logically pairing up ending sequence and starting sequences cleverly.

RodneyConger · Answer

Hi Garrett, there is not a super clean way to support this. I can think of a couple clumsy methods that should work.  Method1. Build route components and then link them together. The route components would be groups of stops you want serviced together and would represent partial shifts. Once you've built these grouped stop modules, you could then link them together into one route using "preserve route and relative sequence". This approach would require that you assemble the modules yourself. I can think of another way you could get VRP to group them for you, but that's a longer explanation. Method2. I am less confident this method would always prove to give you the result you want, but you could use mutually exclusive soft time windows. All of your "service first" stops would have time windows that start early and are very short (like 5 minutes wide), but would have a max late time that stretches to when you think the second stop group would start. Assume the stops are evenly split between "clean" and "dirty" stops and you want to service clean first. Assume also that your days start at 8am and are 8 hours. All of your first group stops would have time windows that start at 08:00 and close at 08:05. The max late time is 4 hours. Your second group stops would have time windows that open ~11.00 and close at 17:00. You may need to play with the TwStart of the second group and the max late of the first group until you get the solutions you want. In any case, your multi-vehicle assignment should look pretty good (clustering), but you may need to post process some of the sequencing.