Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimize the time to do a delivery route

  1. Jul 16, 2006 #1
    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. jcsd
  3. Jul 16, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Perhaps you should see if there are some natural sub-groups of delivery stops where you can reduce the traversing time.
  4. Jul 16, 2006 #3


    User Avatar
    Science Advisor

    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
    To use a TSP algorithm you'll need to know the approximate driving times between each pair of stops. You could try to compensate for traffic congenstion or just use, say, Google maps to get approximate times.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook