3 ms·
The situation I've had to apply the travelling salesman problem to, and probably the one its most applicable in, was delivery logistics. Given a list of deliver
by jon-wood 9y ago
The situation I've had to apply the travelling salesman problem to, and probably the one its most applicable in, was delivery logistics. Given a list of deliveries that need to be made, and the time windows in which they'd been booked, what is the optimal order in which to make those deliveries?
This problem gets particularly interesting when being applied to deliveries between 4pm and 10pm in London, because you have to start taking into account things like rush hour traffic, road closures, and football matches. You also occasionally have to make tradeoffs like deciding whether it's better to deliver 4 small orders a little late, or one large order really late - for those situations we could reschedule those orders and allow the routing system to generate a new route.
- fred_is_fred 9y agoI know this is grossly simplifying but it seems the algorithm works exactly how a sane delivery company would work. Imagine a company in Paris that has multiple UK deliveries coming up. First let's lump together all the deliveries in London. Then let's lump together all the deliveries in South London, then let's lump together everything in neighborhood Foo in South London. Then the routes you worry about are your longest ones, like getting to London or into London in the first place. This makes the assumption that it's quicker to get from a spot in South London to neighborhood Foo than it is from South London to say Leeds. It didn't appear to me from this article that any consideration was given to large late orders or what you mentioned, but that would up the complexity.