By:
September 14 2017

The traveling salesman, Tacton and orienteering

Believe it or not, traveling salesmen and product configuration go hand in hand. Here's a story of a mathematical problem we used to stimulate the minds of our employees – the Tactonites – during our company's spring kickoff. So, what do traveling sales consultants have to do with Tacton and the navigational sport of orienteering?

 

The traveling salesman

The traveling salesman problem, or TSP, is a classic. Basically, this problem presents the challenge of finding the most optimal route between a number of nodes. If you have appointments in 10 different cities in a week, how do you travel between these appointments? If each city is connected to all other cities and each direction is counted individually, that's 100 different possible paths. What is the most optimal path the traveling salesman should take to visit each city only once?

To solve this quest, it's often helpful to visualize it as in the map of France below. The human mind is great at solving these types of puzzles to a certain extent. We use our experience about certain paths and reuse them easily, visualizing them with maps that support us in our decision-making. But the human mind is limited and biased. We can really only understand patterns and paths of certain sizes. The TSP website offers an excellent example of how to solve visiting 24,978 towns in Sweden in the most optimal way.

 

The TSP has been around since the 1800's, and ever since the 1950's people have been trying to solve it in different and better ways. (If you're interested in computational theory, you can read here on Wikipedia about how the TSP is a “NP-complete problem” and thus “NP-hard” to solve.)

It turns out that one great way of solving such problems is using the Tacton configurator. The configurator engine is state-less and uses constraints instead of sequential rules to solve the problem. Finding the right nodes to use and understanding which paths connect them presents a similar challenge for the traveling salesman as for product configuration.

Reducing the paths is the same as creating constraints. We don't want to travel too far on some days, too little on the next, we don't like to backtrack and revisit the same place, maybe some nodes aren't directly connected, and so on.

Orienteering at Tacton

Quite a few of us at Tacton do sports, and we have an athletic section focused on a quirky outdoor sport that combines brains with brawn – orienteering. Originally a military exercise, orienteering has its roots in 19th-century Sweden and combines racing with navigation. Participants use a specially created map to select their route and navigate as quickly as possible through often-unfamiliar terrain (usually in a forest). We've participated in the world's biggest orienteering relay, Jukola, plus local orienteering competitions. We even go out running during lunch breaks. You can follow us at https://www.instagram.com/tactonok/.

 

For this year's kickoff, our team wanted to introduce more people to this fun sport. So, true to our corporate and cultural heritage, we built an orienteering course configurator and made sure that everyone at Tacton could enjoy the sport based on their own abilities, not just for the sake of competition. The organizers asked employees questions about the pace they wanted and the level of complexity of the controls (nodes) they felt they could manage. We then created a configured map based on their input. In short, we provided them with some guided selling options to create a valid, optimal solution based on their input. The “users” could even add more controls, add more minimum distance, or decide to take part in the competition if they wanted to.

 

In orienteering, the competitors have to visit each control in a specified order. Basically, they've got to execute the traveling salesman route that someone has set up. This time, we used the Tacton configurator engine (our so-called constraints solver) to help the competitors set up their individual courses, which they then got to execute.

Solving the TSP when orienteering

First, we took the map of the area where the kickoff was held and charted out 40 different nodes, thus creating 1,600 possible paths assuming that each node should connect to the other. Each path was documented with its length, bearing (direction angle compared to north), difficulty, and the From and To nodes it connected. Next, we removed all the paths that were too short (<50 meters) or too long (>600 meters), leaving us with 1,274 paths.

 

Then, some constraints were applied:

The sum of all individual path lengths in a course must be longer than the guided selling input.

The sum of all difficulty points for each node had to adhere to the user input.

 

Since orienteering includes changing bearings for each control, the course was designed so that no next control could be in a sector ±50° within the bearing ahead or behind the path leading up to the initial control.

 

 

In order to create a spread of the courses, we inserted a JavaScript randomizer that outputted different starting points within a given cluster of nodes. If we hadn't done this, the people with same inputs would have received matching courses, and we wanted to create a disruption by having a wider spread.

 

The courses we created were integrated to an orienteering course-creating tool and then printed at the venue. Each competitor received their individual map and a compass. And when they ran their course, they helped create a great event utilizing our own IT tool!

 

In the end, we had 149 participants on 59 different configured courses, apart from the 28 in the competition class. Who knows what future developments at Tacton will bring?

Related Blogs

Leave a Reply

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

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>