The Travelling Salesman

THE TRAVELLING SALESMAN

Interview with Dr Vladimir Deineko, Associate Professor of Operational Research

With our ever-increasing workloads, it is desirable to find the most time-effective way of completing a task. The 'Travelling Salesman' problem is used by mathematicians to model this common conundrum - what is the best way to complete your task while minimising output?

What do a bee hive and the Royal Mail have in common? I will let you come up with your own punch lines if this looks like the start of a promising joke. I have trade secrets to share instead: the answer is they both face their own 'travelling salesman' problem. Bees need to choose a route around the flowers in a garden so they collect lots of nectar without running out of buzz; postmen need to take the best route around the houses to minimise the amount of petrol, or pedal power, as they deliver our parcels. There is no way, at the moment, to guarantee finding an optimal solution in all cases. All that can be done is test all the possible routes to find out which is the best option or settle for a route that wastes lots of time, and therefore money.

This might sound ok in principle, but the number of options that need to be tested increases rapidly with the number of flowers to be visited, or parcels to be delivered. In technical terms, it has a factorial growth rate:

The number of options to be tested = number of flowers ! = Number of flowers x (Number of flowers - 1) x (Number of flowers - 2):..x 3 x 2 x 1

In specific cases, where you introduce some constraints, it is possible to write an algorithm that will come up with a near-optimal solution. This is already software available to help you do this that you can buy off the shelf - but it cannot guarantee the generation of an optimal solution. The more information you have about the specific case, the better the result. Sometimes the old-fashioned pins on a map is the best option as humans can know the intricate detail of an area better than a computer is able to.

The future of GPS promises intelligent advice on which route to take via an internet enabled Tom Tom which is constantly crunching real-time data on traffic jams and road closures. Again, however, it often won't guarantee the best result; humans do have the chance to be even better (an argument often made by London Cab drivers with "The Knowledge").

This type of problem, which can only be solved indirectly, is not confined to mapping issues. There are all kinds of other scenarios where the practitioner is forced to test out a series of prototypes, getting incrementally closer to a workable solution each time. A frustrating way of working no doubt. Timetabling is another great example - how do you arrange lessons so the largest number of students avoid lecture clashes? The computer keyboard? Different languages need different keyboards as the letters are arranged to minimise the distance your fingers have to travel, based on the most common sequences of letters in that particular language.

Prof Deineko has written a programme to solve a common administrator problem of how to split a new cohort of students into tutorial groups. "We have students from all over the world on our masters with a range of experiences and they all pay the same price. I wanted to find a way to make sure the groups were all equitable and that everyone got to mix. Balanced Groups was my solution. The people I know who use it here seem very happy with it!" Prof Deineko makes a very good point: "Collaborative learning in groups is a resource to be utilised in certain circumstances but it is only fair if the groups are a mix of mathematic ability and professional experience so that everyone gets to learn something."

The particular courses he speaks of are the two specialist MSc programmes run by the ORMS group - the long-established MSc in Management Science & Operational Research and the new MSc in Business Analytics & Consulting. Both involve a three-month summer project where students solve a real-life problem for industry by designing a customised algorithm. One student worked for Coventry City Council: the council have to pick up clinical waste from various facilities in the area and deliver it to a waste disposal unit (one is in Birmingham and one is in Coventry). On a Friday they only work half days. Using these constraints the student was able to map out time-saving routes for the lorries that promised potential fuel savings of up to 20% (the two solutions are visualised on the map).

While this is obviously a pleasing result, the problem for organisations is that these algorithms are complicated to understand and difficult to apply if they are not built into a usable software package. Money saved has to be pitted against costly consultation processes and implementation costs. Prof Deineko explains: "I have no doubt there will always be work for researchers like me in this area, because there is no general solution. For each specific case an algorithm has to be specially adapted. The devil is in the detail. It is always a matter of prototyping. Design a solution and test it, then design a new one to see if you can do better." This methodology must be frustrating for a mathematician since, temperamentally, they prefer elegance and precision.

Although Prof Deineko is often called upon to apply his knowledge in this area, his academic research is concerned with this problem on a much deeper theoretical level. He is part of a community of mathematicians who trouble themselves with what is known as the P vs. NP problem. It was named as one of the seven millennium problems for mathematicians in 2000 by the Clay Mathematics Institute: solve the problem and you are in line for $1,000,000 prize money! He does not hold out much hope for securing the jackpot however: "It is really very hard to shine light on this problem - I do not believe it will ever be solved, but I cannot say for certain. That is my conjecture."

The P vs NP problem may not be the catchiest title but you don't have to think about it for long to realise that the travelling salesman conundrum is one faced by businesses in all kinds of contexts, all the time. As Prof Deineko neatly summarises: "This is really about making an optimal decision based on a structural way of thinking with quantitative support. It is hard to imagine an area of activity where these skills are not in demand."

Dr Vladimir Deineko is an Associate Professor of Operational Research. He is part of the ORMS of WBS but is also affiliated with the Centre for Discrete Mathematics and its Applications which was established to facilitate collaborations between mathematicians, computer scientists and operational strategists.

He has thirty years of teaching experience in a varitey of cultural environments; formerly associate professor at Dnepropetrovsk State University, Ukraine, and invited researcher at University of Technology, Graz, Austria. Participation in consultancy projects related to problem solving in industry, commerce, and the public sector.

Research interests include algorithmic aspects of the problem solving process with the main focus on the analysis of efficiently solvable cases of hard optimisation problems such as travelling salesman problem and quadratic assignment problem; design and implementation of exact and approximate algorithms for combinatorial optimisation problems: vehicle routing problem, bin packing problem, network optimisation problems etc.

By Amy McLeod