VRP - optimise solution with multiple constraints

[JJ8]

Problem:   200 stores are visited throughout the week on different days, the same driver is required to visit the same store across the week.

• The days each store is visited differ. (Some might be MON-FRI, other 1-4 days only)
• The number of stores visited is different each day. (MON - 130, THURS - 150)
• Capacities vary daily for each store. 

What is the best approach to optimise this network? 

I have looked at order pairs, but would need to know "which pairs to assign" and this doesn't seem to optimise solution. 

[HeatherMoe]

This is a very interesting use case. We don't have methods that allow it to be solved with just a single solve but I have seen other periodic routing problems solved successfully with a series of solves. This requires solving for a portion of the problem and then locking those orders to the route and adding in the next part of the problem for another solve. For example The first solve of the problem could look at how to divide up the work that is done daily to the different drivers. This could be done with having one order for every location that has an every day visit requirement. For routes include just a single route for each of the drivers. Once this work is divided then the order locations that need to be visited periodically can be added into the problem and the routes expand to show the drivers and day of the week. With each successive solve the orders that are already routed are kept in the problem and given an AssignmentRule of PreserveRoute and the new ones that are to be assigned have an AssignmentRule of override. 

I'm not able to give too much more advice on the second portion of this yet, because it would depend on the requirements of the periodic routing. For the twice a week locations can they be visited any two days of the week or do you need a required separation between visits such as it could only be Monday/Thursday or Tuesday/Friday or would Monday/Tuesday be okay? Similar questions for the three times a week locations and four times a week locations. Once you have the different options listed out then you would be able to figure out how best to solve the second portion of the solve. 

For example if the twice a week locations must be either Monday/Thursday or Tuesday/Friday then you could solve the problem with just deciding if it will be visited on Monday or Tuesday. You would have routes for double the number of drivers (Driver1_Monday, Driver1_Tuesday, Driver2_Monday, Driver2_Tuesday, ...) TThe every day orders would be duplicated and given a route assignment matching the Monday and Tuesday routes for that driver it was assigned in the first solve. And the twice a week orders would be added into the problem with an assignment rule of override. This would allow the solver to divide up the work between the drivers and the days of the week. If it is assigned to Driver1_Monday then you know it will also be on Driver1_Thursday's route and so when solving for the next set you can include an order for that day and lock it to that route with the AssignmentRule. 

[JJ8]

Hi @HeatherMoe , 

Appreciate the reply. The two step approach, is what I had taken, but thought I might've been missing something obvious. So it is nice to know I am not missing something!

I have the 200 stores routed to the best routes based on approx 25% greater time / capacities than a 'actual day'. Using preserve route assignment rule, I had a number of errors come up due to exceeding capacities and time but with some tweaks to individual orders / routes managed to get the busiest day (142 stores) to successfully run. 

However, when trying to apply to a day with less orders (136) I am getting lots of errors again (Max time and capacities). So feel like I am going around in circles if I keep manually tweaking orders to fit - and not really ending up with an optimised solution. 

To clarify your query: The days are set by historical data - I have 1 week of data, so the days of the week are pre determined by that. The capacities can vary drastically day to day. I have attached a list of all stores, days they need to be visited and how many items are delivered on each day - if that makes my problem any clearer 🙂 

Thank you

[HeatherMoe]

That data was very helpful for understanding this issue. At the fundamental level this is two problems, one which is assigning stores to routes (the Assignment Model) and then a routing problem to sequence the assigned orders. We do not specifically solve the assignment model but brainstormed a few ways that it could be approximated. Here are some options for determining which driver should visit each store.

1. Choose the day with the largest overall quantity and solve that day first. Then lock the orders to the specific drivers with either the assignment rule suggested above or using a specialty that pairs those routes and orders together and solve the next largest quantity day and so on until you have assigned all stores to a driver.

2. For the initial solve have a single order for each store and set the quantity value to the highest for that store location. That might be Monday's quantity for one store but Thursday's quantity for a different store. This first solve would give you the route assignments for each store. Then for each day of the week use specialties to require a store be visited by it's assigned route. This will give you the sequencing of orders for that day.

3. Similar to option 2 but instead of the highest quantity value add them all up and use the sum for the quantity of that location. Also set the route capacity to five times the normal capacity value.

None of these options are perfect but hopefully one can work well enough for you to get some improved optimization for your problem.