Hello my family of FME’ers,
Being the FME Evangelist is both easy and difficult at the same time.
You know how FME saves you so much time and effort? Well it’s the same for me. It’s so easy for users to see the power of FME, I hardly have to evangelize that at all. And the user endorsements we get are worth ten times my word on the subject! We have products and users that evangelize themselves. How great is that?!
The more difficult part is that our developers are so busy adding new functionality that it’s hard for me to keep up. And sometimes the buzz about GREAT new formats and GREAT new transformers drowns out other tools that are merely very good!
Today’s article is about one of those overshadowed pieces of functionality. In 2016.1 we made updates to the ShortestPathFinder transformer that let us deal with a classic GIS task: the Travelling Salesman Problem. I don’t think many users are aware of this enhancement and so I wanted to cover both it, and some updates that are coming for 2017.
The Travelling Salesman Problem
Quoting from Wikipedia, this is a geographical problem concerning optimization of routes.
The idea is a salesperson wants to travel between n cities. The order of travel does not matter so much as the need to take the shortest route.
For example, here is a map of German cities with the optimum route between them.
It looks simple, but it’s quite hard to compute. It’s an optimization problem where you start out with one solution and then try different iterations to hopefully reduce the distance (or cost) to the optimum.
If you’re interested, it’s what’s called an NP problem, because it’s really easy to verify the result but very difficult to create that result in the first place. If you can think of a way to generate a result as quickly as it can be checked, then click here to claim your million-dollar prize!
The Travelling Salesman Solution in FME 2016.1
Prior to this, FME could create the shortest route between two points of a network, and even allowed for intermediate stops along the route. But what it didn’t allow was rearranging those intermediate points.
So, in the above map, if we had Essen-Hamburg-Duisberg in that order, then the route would go through the cities in that order, when obviously Duisberg-Essen-Hamburg would be more logical.
But in FME2016.1 we added a bunch of new parameters for optimizing the route:
By default it’s set to not reorder the stops on your route, but if you turn on that parameter you can choose to either reorder all of the points, or just reorder the intermediate points and leave the start and end as they are.
The other parameters allow you to define the number of iterations the process goes through, and how many times in those iterations the same route must be found in order to be accepted. Basically the higher those numbers the longer the process will take, but the more optimized the route will be.
The default number of iterations is 10,000, but in the following example I increased it to several million without performance degrading much at all. But I’m also guessing that the more points you have to start with, the longer the processing will take, so that’s a factor.
The desired cost parameter is a way to set the maximum cost incurred by the route. The cost could be time or distance so, for example, you could choose to not return any route that is more than X kilometres in length.
I’m told we use a “metaheuristic” technique to find a solution, which is a definite candidate for my word of the week!
Example: A City of Vancouver Artwork Tour
Do you remember my recent post about HTML reports and artwork in the city of Vancouver? I kinda joked that you might like to look at some of the artwork when you are here for the FME International User Conference next year.
But what if you really did want to do that? How could I make that easier for you? Well – if you haven’t guessed by now – I thought I could create a workspace that lets you pick pieces of public art and then tells you the optimum route to visit them.
Let’s call it the Travelling FME Art Connoisseur Problem.
So here’s the workspace (click to enlarge):
It’s not quite ten transformers or fewer, but most of this is data preparation. For example, the first section is this:
What I’d done is create a published parameter that lets the user choose a set of artworks. It’s a multiple selection parameter, so this section is reading that parameter and splitting it off into the separate selections. It then uses a FeatureMerger as a way to match the artworks dataset to those that have been selected. Basically filtering the source data to your selection of artworks.
The next part is this:
This section reads the road network and deals with an issue I hadn’t realized. It turns out that intermediate points in a From-To line have to sit exactly on a network end node. I didn’t know that, and it was the big ‘gotcha’ for me. Without it the workspace didn’t work (in fact it crashed, oops!) so what I’ve done is:
- Add a Chopper transformer to turn every network link into a 2-point line (which turns intermediate nodes into end nodes)
- Use an AnchoredSnapper to snap each artwork onto the nearest road node
I set a snapping tolerance of 1,000 metres, which seems like a lot but isn’t really an issue. We’re just trying to get you to the nearest point to the artwork. The final transformer – the PointConnector – joins together the artwork into a single line. The order of the points doesn’t matter, because the ShortestPathFinder is going to sort that out for us. Speaking of which…
There it is! I set it to reorder all points, including the start and end point. In reality we might fix the start and end point – maybe using transit stations as the start/end to give you a complete route – but we’ll leave it for now.
The number of iterations is an interesting problem. The user could choose two or three artworks (wouldn’t need many iterations) or choose all 100+ of them (would need a lot of iterations). I set it to 5,000,000 but I’m wondering what would happen if I used the arithmetic editor to set (100,000 * NumberOfArtworks)? I may try that out.
Results
So I ran the workspace and chose a number of artworks. I cursed when I found the result was incorrect, found the problem (my poor handling of the published parameter), decided to deal with it later, did a workaround (picked only artworks that matched my faulty assumptions), and found these layers in the Data Inspector:
Those are the five pieces of artwork I chose to visit, and the initial order in which they are connected. This layer:
…is the order that the ShortestPathFinder thinks I should use, and it’s hard to argue with. The path it determined to visit those is this:
At first that looked a bit odd to me, especially that route going up north from points 3-4 (starting at the bottom left). But consider that North American cities are usually laid out in rectangular blocks, so it doesn’t matter which side of a block you travel along, and in fact that little angle at the top probably shaved off a little distance compared to any other route.
One thing I found is that the reorganization of points only works for five points or more. If you only have four points it doesn’t want to reorder them. I guess that’s reasonable and I’m told that FME2017 will explicitly log a warning about that case.
Incidentally, that took 18 seconds to run the workspace and output the result; so I wondered what it would take to do more points – a lot more points! So I selected 40 artworks – that really would be a long walk – sat back and waited for the workspace…..
It seemed like this would be very quick too. The workspace started out at a storming rate and the log said this…
2016-11-10 10:19:20| 15.1| 3.0|STATS |ShortestPathFinder(NetworkFactory): Completed 75% of intermediate processing
75% in fifteen seconds! But I’m not sure that was 75% of the travelling salesman because then it slowed down a bit…
The final time: 2 minutes 23 seconds. But I’d say that’s pretty good. The results, this:
Original points and ordering on the left, FME’s suggested ordering (black) and route (red) on the right. It looks a good route – but I could always increase the iterations and verifications if I wanted to make really sure it’s as good as it could be.
Oh, I also didn’t factor in one-way streets (though I could, they are flagged in this dataset) so if you do use this, make sure you are walking not driving! Speaking of which…
Please do download the workspace and source data and try this for yourself. I think there are some great possibilities with this functionality.
Really this would be a great project to deploy on FME Server and I so wanted to add this as an online web service that takes your selection of artwork, creates a route, and streams it out to KML (or ideally plot it to an online web map), but I just couldn’t find time in my schedule to do that. Another time I guess.
Travelling Salesperson Updates for FME 2017
So, not only did we add those updates in 2016.1, we’ve also added a bunch more improvements for this transformer in 2017. To quickly list these they are…
- A new cost type: Straight Lines. Lets you run the reordering without using a network, so I can select the order of my artwork without having to define a route for it.
- A new parameter: Allow U-Turns. By setting this to “No” I prevent u-turns being allowed, even if the route might be slightly longer (or more costly).
So a path A-B-C-B-A would not be allowed (u-turns from B to C and back to B), but a path A-B-C-D-B-A is fine (no u-turns in there).
Also there are new optimization options, specifically around when the complete an analysis…
- New Finish Conditions: Basically you can continue iterating until your desired cost or number of verifications is met
- Iteration Rounds: The ability to repeat your set of iterations for a number of rounds, to get a better result or verify the existing result
- Time: The ability to stop the analysis after a set number of minutes, returning the best result up to that point.
The Time setting I especially like, because if I set the other values too high I can still cut off my workspace before it goes on for hours, optimizing a route that might already be pretty good. These new options integrate with the existing ones to provide much more fine-grained control of when to complete the optimization.
We also:
- Improved the handling of from-to lines, including better handling of duplicate points and points that snap to duplicates.
Summary
With these updates – and the ones to come in 2017 – you’ll have a pretty comprehensive FME solution to shortest path problems of this type. The artwork tour is just one example of what you might use it for. I can think of a few more scenarios (optimizing the FME World Tour for one), but I’m interested in your ideas too. If you can think of a good use for this in your organization then do let me know by email or as a comment below,
Regards
NB: Where I’ve used “travelling salesman” instead of “travelling salesperson” in this article it’s where I’m quoting a recognized term (e.g. that’s what Wikipedia uses). If you’re interested I just counted the folk who come under the umbrella of Sales at Safe, and 75% are women, with 50% having a title of director or manager. So much for the “salesman” myth! I also notice that all our real travelling salesfolk – the FME World Tour teams – are all mixed. We don’t send out any all-male teams. In an industry that is not always known for gender equality, it’s great to work at a company that really makes an effort. And we’re still hiring for developers, GUI, web, support, and QA.
Mark Ireland
Mark, aka iMark, is the FME Evangelist (est. 2004) and has a passion for FME Training. He likes being able to help people understand and use technology in new and interesting ways. One of his other passions is football (aka. Soccer). He likes both technology and soccer so much that he wrote an article about the two together! Who would’ve thought? (Answer: iMark)
