Decision Intelligence (DI) can only have an impact when the plans it creates get executed. Which is to say, the plans have to be accepted by the operators. Can you provide a solution for this client that will keep them coming back for more?
A Utility has planned repairs around their depot (location (0,0), marked yellow) which features nine vehicles and their respective crews. Each vehicle is supposed to serve at most six planned maintenance jobs and otherwise may be rerouted to handle unforeseen issues in the network.
The Utility is concerned with the total travel distance (we use Euclidean distance for this puzzle) and travel time for their maintenance crews and has asked for your help.
You can use this Colab to get the data and visualize your solution.
How are you thinking about the time factor and the fact that additional work may pop up anywhere in the service area?
My personal recommendation would be to cluster the maintenance jobs in this application rather than formulating the problem as a classical vehicle routing problem.
Reasoning:
- When jobs are clustered in one restricted area, we can easily reorder jobs based on current traffic conditions following reroutings to emergency jobs that need to be handled.
- For regions further from the depot, we have a long stretch for the first and last legs and then a sequence of small connections in between. This allows the drivers to choose the best routes in the morning and the evening depending on traffic conditions, without tying them to a predetermined sequence of intermediate stops.
- From the beginning to the end of the workday, we have coverage in the entire service area, allowing us short reaction times in response to emergency jobs.
Seeker suggests this solution when aiming to minimize mean radius plus max radius over all nine clusters:
Below we color the regions that individual crews are handling. This illustrates the points made above: clustering naturally leads to localized service, allowing flexibility how to get to and from the service region while offering short distance recovery in case of ad-hoc changes.
Contrast this with a typical vehicle routing solution where we minimize total distance:
When travel distance is the optimization criterion, we typically get tours that cover elongated wedges rather than short-diameter blobs as the picture below shows.
This solution structure leads to little flexibility when rerouting (in response to traffic or new emergency jobs) and causes high costs in practice. This easily justifies the ~3% higher planned travel distance for the localized tours solution.
At InsideOpt, we believe that your success as optimization expert is determined by the acceptance of those who need to execute your plans. That is why we built a solver for you that not only works for standard textbook formulations.