# Minimize the time to do a delivery route

1. Jul 16, 2006

### fourier jr

my boss says he'd give me a raise if i figured out a way to do the delivery routes faster than we already do it. the number of stops to make would be the same but the order might be different in order to minimize the time (maybe not necessarily the distance) it would take to do the route, if possible. (might already have the fastest-possible ordering of deliveries) there are also some constraints, like some deliveries have to be there precisely at a specific time or before/after a specific time, one-way streets, etc. that sounds like some sort of discrete math (combinatorics?) problem, in which case i'm out of my element. can anyone point me in the right direction?

edit: i guess there are n! ways to do n deliveries but how to figure out which one is fastest i'm not sure. for my work that would be about 20! possibilities for each delivery van (2 of them). i think most of the orderings would be silly though so i could probably rule out most of them. what about looking up the addresses of all the places, using mapquest to find out how far away they are & adding up the distances that way? i could also suppose the driver goes no faster than a certain speed like 60km/h. i guess thats a start, i'll get a list of all our accounts tonite.

Last edited: Jul 16, 2006
2. Jul 16, 2006

### arildno

Perhaps you should see if there are some natural sub-groups of delivery stops where you can reduce the traversing time.

3. Jul 16, 2006

### 0rthodontist

This is the travelling salesman problem and there is no known good way to find the perfect route. However many approximate solvers do exist, and you could try something found at