Delivery Algorithm - Find shortest paths

Question

Given -

• A center(lat=x,lng=y) 'C' from which a delivery boy makes a round trip.
• A delivery boy has a bag which may contain at the most 10 boxes to deliver.
• A set of points Di (lat=xi,lng=yi) around 'C' where the delivery has to be done. D=number of Di & 1<=D<=10
• Each Di either belongs to time window(30 minutes) W1 or W2 where W1 is something like 11-30 am to 12 pm and W2 like 12 pm to 12-30 pm
• Each delivery has to meet an SLA (service level agreement). Eg- If the order O1 at drop point D1 belongs to W1 then it must be delivered within W1 window.

Task - Find the shortest time path such that the delivery boy meets SLA for maximum number of orders. The best path is the one where SLA is met for all orders..

I think it will be better if I start with a couple of variations.. Use these variations in dry runs and gather some data for each of the variations..

What I am looking for - Any other cues/variations that I can use.. The greedy approach is already up and running. I am gathering real time data to measure its performance..

CLARIFICATIONS

If SLA's can't be met, do the deliveries still need to be made? - Yes, in those cases the best algorithm will be the one with minimum SLA breaches..followed by minimum time..

Are there algorithm constraints/metrics (I.E. execution speed, memory used,etc) that must be considered? - Speed - not so much an issue - even if it takes 1 minute to run algo its ok, memory - it may take upto 0.5 gb.. Also if it turns out to be very compute intensive.. I can buy a new machine for running this algo..

Will you need to scale up beyond the relatively small inputs stated - NO. The delivery boys capacity is fixed. It may at the most become 15 (from 10 earlier)

Answer 1

A max of 10-15 orders is small enough that you might be able to brute force it. While this would exceed your execution time limit, it might be worth doing so on a small number of problems in order to compare algorithms absolutely rather than relatively. Alternatively, you might be able to find precomputed benchmarks for this problem.

In general, I'm personally found of restricting routing problems to a Deluaney triangulation. It's fast to calculate and has a Euclidean minimum spanning tree (MSP) as a subset. It won't have any route crossings (like those removed by a 2-opt).

However, the SLA constraint may work against that. E.G. Say that the you have found an optimal TSP solution (a locally optimal solution) for W1, but it can only service k out of n orders in time. In that case the globally optimal solution may require delaying the last (n-k) orders in W1 and going to the clostest order in W2. There's no reason to expect this W1 to W2 switch-over arch to be in a DT over all the sites. Furthermore, if your time windows don't overlap, there's no reason to visit W2 site during the W1 phase.

So then, I'd find a MSP for each subset of order sites (W1 & W2). On W1, apply Christofide's algorithm to get a Hamiltonian cycle. Find the start node, call it S1, & remove its longest arc in the cycle to get a Hamiltonian path through all of W1 - call this P1.

Next, compute the travel time & check for broken SLAs on P1. Eject the site that yeilds the biggest time savings until all remaining SLAs on P1 are valid.

Find the clostest point in W2 to the last site in P1 - call this S2.

On W2, apply Christofide's. Find S2 & remove its longest arc in the cycle to get a path through all of W2.

Recompute the travel time for P1 + P2 & check for broken SLAs on P2. Eject the site that yeilds the biggest time savings until all remaining SLAs on P2 are valid.

Finally, let W3 be all the previously ejected sites. Find the clostest point in W3 to the last site in P2 - call this S3. Find a MSP on W3, apply christofides, find the S3 & remove its longest arc in the cycle to get a path.

Solution is concatenation of P1, P2, P3, S1. Clearly, there are cases where this won't give the optimal answer, but it should scale well & has known bounds on the sub-problems which might help in determining its overall bounds.

Answer 2

Let's focus on the case where you try to figure out whether there is a way to meet the requirements without any SLA violation. This problem can be solved by solving at most 10 Hamiltonian path problems, then combining their solutions appropriately.

First, let's focus on the first time window. For each $i$ such that $D_i$ must be visited during the first window, find the shortest path that starts at $C$ and ends at $D_i$ and delivers every order that is scheduled to appear in the first window. This is a Hamiltonian path problem, so can be solved using standard methods (e.g., branch-and-bound, ILP, etc.). In particular, you build a graph with one vertex per $D_j$ such that $D_j$ must occur in the first window plus one vertex for $C$, where the length of the edge from $v$ to $w$ is equal to the time it takes to travel from $v$ to $w$, then you find the shortest Hamiltonian path from $C$ to $D_i$. Let $\ell(C,D_i)$ be the length of the shortest such path.

Next, focus on the second time window. Build a graph with one vertex for $C$ plus one vertex for each $D_j$ such that you have to deliver to $D_j$ in the second time window. Let $\ell(D_j,C)$ be the length of the shortest Hamiltonian path in this graph from $D_j$ to $C$, i.e., the shortest path that starts at $D_j$ and ends at $C$ and visits every vertex in the second graph.

Finally, we'll look at all ways to piece together a Hamiltonian path for the first graph and a Hamiltonian path for the second graph. In particular, if $D_i$ is a delivery location for the first time window and $D_j$ is a delivery location for the second time window, the cost of the shortest path $C \to \dots \to D_i \to D_j \to \dots \to C$ that visits every location will be $\ell(C,D_i) + \text{wt}(D_i,D_j) + \ell(D_j,C)$ (where $\text{wt}(D_i,D_j)$ is the time it takes to get from $D_i$ to $D_j$).

So, compute the minimum of $\ell(C,D_i) + \text{wt}(D_i,D_j) + \ell(D_j,C)$ over all $i,j$ such that $D_i$ is in the first time window and $j$ is in the second time window. This gives you the shortest path that starts at $C$, visits every delivery location once and within the right time window, and ends at $C$. In other words, it gives you the shortest path that meets all your requirements and doesn't violate any order's SLA.

Given how small each of the graphs will be, you should easily be able to solve each of those 10 Hamiltonian path problems -- it should be very fast. There are many known techniques for solving Hamiltonian path problems, from exhaustive enumeration to branch-and-bound to integer linear programming (ILP).

This only handles the case of no SLA violations, and it assumes the delivery person never needs to return to the center $C$ (his bag is large enough to store all of the boxes).

If it's not possible to solve the problem with no SLA violations, you can probably extend this to find the best solution that minimizes the number of SLA violations with a bit more work, by adapting these techniques. As a simple trick, you could check whether it's possible to solve the problem with only one SLA violation by iterating over all possibilities for which order to skip (solving the resulting problem by deleting that one order and then looking for a way to handle all the remaining orders with no other SLA violations). It's probably possible to generalize to an arbitrary number of SLA violations by a clever use of dynamic programming, but if you expect it to be rare to need to violate the SLA by more than one or two orders, it might not be necessary to develop the more sophisticated algorithms to handle the general case.