The Travelling Salesman Problem: A New Approach?

Of all of the classic computer-science problems, the Travelling Salesman Problem--a problem in discrete or combinatorial optimization--is the one I like most. Probably because it is among the ones I first puzzled over, not to mention that it is so darn practical.

In a nutshell, the problem statement for the TSP is: Given a number of cities and the costs of travelling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city?

If you've paid to fill up the gas tank of a car or delivery van recently, you know why this question is probably more relevant today than when it was first tackled more than 100 years ago. Clearly, any way to cut fuel costs is a win for the person paying for the fuel.

Which is where T.T. Narendran, a professor at the Indian Institute of Technology-Madras, and Chandra Sunil Kumar, a Ph.D. student who specializes in Logistics Management, enter the picture. What they've done is develop an update to the TSP algorithm and built a computer model to implement it.

In their paper "Heuristics for the Real-Time Pickup-and-Delivery Travelling Salesman Problem" to be published in the International Journal of Logistics Systems and Management, Narendran and Kumar assume a single vehicle operating within a region. Each day, there are calls from customers, packages to deliver, and others to collect and deliver elsewhere. Static customer requests are those that are known in advance, while dynamic requests arise as the day progresses. The vehicle starts from the depot, and moves to serve static customers according to a schedule of advance requests. As the day progresses, new requests come in and the dispatcher has to re-route to fulfill these new requests while minimizing the total distance traveled in accommodating advance bookings.

The vehicle then follows the latest determined route until a new dynamic request arrives. At that time, the vehicle is between the start and finish of the original plan. Now the plan has to add a pickup and delivery point into the unexecuted part of the plan so that the additional distance to be traveled is minimized. At this juncture, the computer model inserts a heuristic. In one method, the customer's new request is positioned appropriately between two of the places to be visited as per the original plan. In the second approach, the entire sector remaining to be served is reframed with the inclusion of the new request; this part of the problem is solved using an optimization approach.

Narendran and Kumar have tested the model computationally and found that the distance traveled by the vehicle increases with increasing numbers of new requests. However, the heuristics can work in real time and every time a new request arises, they can process the information and re-route the vehicle to keep the total distance as low as possible.

And less distance, less cost.

Posted by Jon Erickson at 10:07 AM  Permalink