The multiple traveling salesman problem (mTSP), with constraints, is a well-known mathematics problem that has many real-world applications for those brave (or foolish) enough to attempt to solve it.
Obviously, being able to determine the shortest route has great financial implications for companies that do a lot of traveling – such as delivery and courier services.
Imagine being told that, at the click of a button you could reduce your travel distances and transport costs by 10%, 20%, or even 30% and more? Let alone the savings in fuel, your maintenance and wear and tear costs would be drastically reduced.
This article highlights how I have developed a PHP based Web service that is capable of returning high quality solutions to the mTSP in the “real world” – i.e. for multiple vehicles that have constraints (such as load capacity, range, etc), and locations that have constraints (such as delivery time, cold chain, visit sequence for pick up and drop off deliveries, etc).
What is the mTSP?
The mTSP can be used to find a class of minimal solutions to a wide variety of problems.
The most common one being:
“If I have several salesman who have to visit a number of points, what is the quickest way for them to do it?”
The multiple traveling salesman problem is what’s known as an NP-hard (that’s Non-deterministic Polynomial-time hard) problem that is notoriously difficult to solve.
The reason is because as the number of points increase, so the complexity of the problem increase polynomially. That’s polynomially – faster than exponentially.
How hard is the mTSP to solve?
To give you an idea of the sheer difficulties involved in designing and programming a solution to the mTSP, let’s do some quick calculations.
The image in this post shows one of the solutions generated using my Web service for two vehicles with 50 points. Looks sensible right? How hard can it be?
Well, to calculate the number of potential solutions for one vehicle, your reasoning would go like this:
- Choose one point out of a potential 50
- Choose the next point out of 49 remaining
- Choose the next point out of 48 remaining
There is a mathematical operator that allows us to calculate this number (called bang), and:
50 bang (written 50!) = 3.041 x 10 to the power of 64 = 30 410 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
Hopefully I got the right number of zeros in there.
But, we have two vehicles, so the number is actually a lot bigger – and, when you factor in constraints, which in the real world could be numerous, the problem is intractable.
In fact, the number of potential solutions are simply to numerous to calculate directly using a computer.
So where did I begin?
Solving the mTSP
Because no self respecting computer would attempt to go through all the possible solutions to find the best one (at least not in our lifetimes), I had to cheat.
I use what’s known as a heuristic method. You can think of a heuristic method as a way of building learning, experience and intelligent guesses into computer software.
The one I developed is based loosely on a particularly ingenious method invented, and used by, ants.
The Ant Colony Optimization method (ACO) mimics how ant colonies build efficient pathways between their nests and food sources. Basically ants head out in all directions foraging. The ones that return early with food, leave a pheromone trail that influence the decisions of other ants.
In this way, strong pheromone trails are built up with time sucking in more and more ants until they have a nice straight path to the food that everyone can follow.
But, while I use the ACO as the fundamental basis of my solution (which, incidentally, is developed using OO PHP, JSON, the GDM API, and plenty more), I had to take a few extra steps to speed up the process and improve the results.
While I can’t tell you exactly how I developed it (because this would cause no small amount of consternation from my employer), I did, amongst other things, incorporate mutations to help my ants learn faster.
Mutations are part of another heuristic method that mimic the principles of random genetic mutations to build up successively fitter generations of solutions.
So basically, I used the ACO, modified it with my own algorithms that help speed up calculations in mTSP problems with constraints, and combined this with aspects of genetic algorithms.
Performance of my mTSP ACO solution with constraints
Naturally, performance plays a big role in how good mTSP solutions are.
Initially, I ran into some serious problems because my constraint checking code was hogging too much processing time and not allowing the ant colony to learn enough about the solution.
Fortunately, by cheating once again, I was able to drastically improve the performance to the point where, as you can tell by looking at the two vehicle, 50 point solution in the image above, excellent solutions for a moderate number of points is now feasible.
For the purposes of my current contract, I need to get reliable, high quality solutions for up to 7 vehicles and around 100 points (with all the real world constraints that apply to delivery companies and courier services – like multiple depots, refueling, capacity, range, cold chain, height, vehicle size, delivery times, and so on).
Once that’s done, I can start working on bigger data sets, but at that stage, it is likely that we’ll start needing to up our processing capacity and possible modify the hardware to work in parallel – like utilizing a Beowulf super computing cluster.
Does your business make deliveries? How would significantly reducing your transport costs affect the profitability of your business?
Share your thoughts on the mTSP, and whether or not you would consider using this as a Web based productivity tool to save your business from rising costs of transport.
More Business articles from Business 2 Community: