How to find the optimal route, given distances and delivery deadlines?

[Yossu]

Hello,

I have a problem that I can't get my head around. Suppose I were a
courier (I'm not, but imagine I were for the sake of this question),
and I had six parcels to deliver, each of which had a deadline by
which it had to be delivered.

For example, consider the following table with d = distance (in miles)
and t = time left to complete the delivery (in minutes)

d | t
-------------

3 | 12
2 | 6
1 | 8
1 | 2
4 | 10
5 | 3

How would I work out the optimal route to deliver all these packages?
I would like an algorithm if possible, as tomorrow's deliveries will
be different.

As I said, I'm not a courier, I was just discussing this with a
friend, and we were trying to work it out. It looks like a variation
of the travelling salesman problem, but with the added twist of
delivery times.

Anyone any ideas? Thanks

[Tim Little]

On 2012-05-13, Yossu <goo...@alansilver.co.uk> wrote:
> For example, consider the following table with d = distance (in miles)
> and t = time left to complete the delivery (in minutes)

[...]

> How would I work out the optimal route to deliver all these packages?
> I would like an algorithm if possible, as tomorrow's deliveries will
> be different.

You need more information than that. Knowing that points E and F are
4 and 5 miles away doesn't tell you how far they are apart. It could
be anything from 1 to 9 miles. Possibly even more in rare cases, e.g.
long one-way streets.


--
Tim

[Yossu]

On Tuesday, May 15, 2012 1:21:48 AM UTC+1, Tim Little wrote:

Sorry, you're right, I oversimplified my example. In reality, we would have the full address of the location, so would know exactly where it was.

Thanks for the reply. Any ideas on how to tackle the problem?

[Tim Little]

There's still a fair bit required to nail down the problem. At a
minimum, you need some way to convert between distances and times.
For a toy problem you could just fix a speed, but in a real-life
situation you need to consider that speed won't be constant. Each
path will have some distribution of times, which may even vary
throughout the day.

After that, you need to decide what you're actually optimizing.
Maximise chance of delivering all items on time? Minimize total time
taken while maintaining some fixed all-on-time probability? Minimize
distance travelled within some threshold? Maximize some other
"expected utility" function of delivery times? Or even just determine
"is this task possible", perhaps providing any delivery route that
satisfies the conditions?

Are there any other additional constraints, e.g. computational power?
If you have a few dozen deliveries to make, you can expect a computer
program to be able to guarantee an optimal result. If you have to do
it in your head, you're unlikely to be able to get the optimum, but
there may be an algorithm to get some sort of decent route.


--
Tim

[Yossu]

On Thursday, May 17, 2012 1:11:38 AM UTC+1, Tim Little wrote:

Hi again Tim,

Thanks for the reply. As for the conversion between distance and time, we could probably get away with an average speed. Most of these deliveries are fairly short distances, and all locally, so the driving speed would be roughly the same for all of them (taking into account factors like traffic lights, etc). This would be accurate enough for the purpose.

As for the actual target, the main aim is to ensure that all deliveries are made on time. If there are two routes that would allow this, then either the quickest or shortest (not really sure it's important) would be chosen.

I'm not worried about computing power, as we are only talking about half a dozen deliveries, which shouldn't be too much of a problem for a modern PC. I know these sorts of problems can have exponential compute times, but we should be OK here.

Thanks again

[Tim Little]

On 2012-05-17, Yossu <goo...@alansilver.co.uk> wrote:
> I'm not worried about computing power, as we are only talking about
> half a dozen deliveries, which shouldn't be too much of a problem
> for a modern PC. I know these sorts of problems can have exponential
> compute times, but we should be OK here.

Oh! In that case even a brute-force "try all permutations and pick
the best" would work very quickly. If there are only 6 deliveries,
there's only 720 permutations. Even up to 12 deliveries would be
within a brute-force approach -- 500 million permutations, probably
less than a minute.


--
Tim

[Frederick Williams]

Tim Little wrote:
>
> On 2012-05-17, Yossu <goo...@alansilver.co.uk> wrote:
> > I'm not worried about computing power, as we are only talking about
> > half a dozen deliveries, which shouldn't be too much of a problem
> > for a modern PC. I know these sorts of problems can have exponential
> > compute times, but we should be OK here.
>
> Oh! In that case even a brute-force "try all permutations and pick
> the best" would work very quickly. If there are only 6 deliveries,
> there's only 720 permutations.

720 what? There are 720 ways of ordering the destinations. But there
is still the question of what route to take to a destination. Draw a
straight line between any two points of a town (as opposed to a country)
map and ask yourself: what is the route that stays closest to that
line? There will often be a number of equally plausible answers.
Plausible, that is, from the point of view of someone just looking at
the map; but an experienced driver may know that some of the roads are
congested and some not. A straight A road may look tempting, but it
will be dug up next week while a gas main is replaced.

I don't know nothing about problems such as this, but it looks to me as
if it might be difficult even for a few destinations.

I don't know if this is possible: consider a "spy in the cab" that
records each route and produces data that can be fed into a computer.
The computer finds the best (in some sense) routes from those fed to
it. Next week it has a different answer because it works on different
data. But perhaps over time it will learn that certain roads are better
than others. But wait a minute, that is just what an experienced drive
will do!

> Even up to 12 deliveries would be
> within a brute-force approach -- 500 million permutations, probably
> less than a minute.

--

When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[Yossu]

Hi Frederick,

Interesting points you raise, and quite valid. However, as my case is using fairly short journeys, it's less of a problem than it might be if they were longer. Also, we are only really looking for a first-guess approximation. The driver would cast his eye over the suggested route (or even better, the two or three best suggested routes) and use his experience and intuition to decide which one to use.

Thanks for the comments though, certainly extra food for thought!

[Narasimham]

linear programming , transportation problem.