[Solved]: Delivery Algorithm - Find shortest paths

Problem Detail: 

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)

Asked By : abipc

Answered By : Pikalek

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45422