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.

EvangelistBanner7

The Travelling Salesman Problem

TravellingSalesmanGermany

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!

EvangelistBanner7

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!

EvangelistBanner7

Example: A City of Vancouver Artwork Tour

TravellingSalesman15-ExtraImageDo 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):

TravellingSalesman3-Workspace

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:

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.

EvangelistBanner7

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:

TravellingSalesman7-OutputA

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:

TravellingSalesman10-OutputD

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.

EvangelistBanner7

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…

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…

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:

EvangelistBanner7

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

NewBlogSignature

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.

About FME AnchoredSnapper Chopper FeatureMerger FME Evangelist GIS ShortestPathFinder Web Services

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)

Comments

5 Responses to “FME 2016.1 Use Case: The Travelling Salesman and FME”

  1. Takashi Iijima says:

    I’m very interested in the implementation for the optimization. There should be some known metaheuristic algorithms which can be applied to the travelling salesman problem, such as Genetic Algorithm, Ant Colony Algorithm, Tabu Search, etc. I’d like to know which algorithm you’ve adopted to implement the optimization in the ShortestPathFinder.
    And, after testing your workspace with different parameters setting, I’m still unclear how the “Number of Verifications” parameter works. It’s hard to understand the description in the help doc: “The number of times the optimization algorithm needs to return the same potential result before it is accepted.” What is the “potential result”?

  2. Takashi Iijima says:

    Hello, thanks for the great enhancement and your excellent demo.
    I’m very interested in the implementation of the optimization option. There are some known metaheuristic algorithms which can be applied to the travelling salesman problem. e.g. Genetic Algorithm, Ant Colony Optimization, Tabu Search, etc. I’d like to know which algorithm is used in the ShortestPathFinder in fact.
    Then, after testing your demo workspace with several parameters setting patterns, I’m still unclear how the “Number of Verification” parameter should work. The help doc says “The number of times the optimization algorithm needs to return the same potential result before it is accepted”, but I cannot understand what the “potential result” indicates. Could you please explain about the parameter in a bit more detail?

  3. Jelle De Zwaef says:

    Some screenshots are missing. Any Chance of bringing them back?

    • Mark Ireland says:

      Hi Jelle – for sure. I don’t know what happened to those screenshots, but I fixed them now. Please do let me know if it happens again.

  4. Kamrul Kashem says:

    Thanks for this useful article.

    If U-Turns are turned on, the network obviously looks pretty joined up together as opposed to the network you’ve made above so its hard to determine where the start is and which way it’s telling you to go. How do I determine which points it’s telling me to use first? It would be useful to actually get the points back in the order. So if they were addresses it would give me a list of addresses in order of which one to visit first, second, third etc. It just returns one big aggregated line feature?

Leave a Reply

Your email address will not be published. Required fields are marked *

Related Posts