If you’ve studied computer science or are tech-savvy, you’ve probably heard of the traveling salesman problem — also called the traveling salesperson problem or TSP. It’s a famous topic in theoretical computer science and operations research that can be explained in a simple question:

"Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

hero-bp-travelling-salesman-problem

The OutSystems Developer Conference is back

Join us on June 21-22 in Denver and prepare to get inspired, test-drive the latest features of OutSystems, and take the next step in your career.

Register now

Table of contents:


In this article, I’ll share how I faced this problem in real life and created a solution that solves it with low-code.

A real-life example of the traveling salesman problem

During the COVID-19 pandemic, many businesses had to re-shift their operations almost overnight. That was the case of a good friend of mine who owns a restaurant serving traditional food and drinks all week in a neighborhood in Lisbon’s city center.

Government restrictions demanded restaurants to close their doors to the public. For months, restaurants could only do business by delivering food to their clients’ homes. Even using a third-party takeaway service like UberEats wasn’t possible because the lockdown forced the general population to stay at home. (Remember those times?) 

I’m a curious guy so I asked my friend how this shift impacted his operations; how a small team that runs a typical and traditional restaurant adapted to this new reality and solved the food delivery problem.

I was especially interested in understanding how they planned the multiple food delivery orders for peak times — lunch and dinner.

The solution was an Excel sheet with the order details (delivery expected time, address). The route was planned on the go.

Turns out, due to the atypical circumstances, the streets were empty, so deliveries didn’t take much time. Clients were always at home; if the order took more than 10-20 minutes than expected, that wasn’t a huge problem, as everyone understood the special circumstances.

The problem

As I was also at home, with extra time, I decided to give my friend a hand and build something that could help plan and optimize the route to deliver the food orders across the city in the most efficient way.

I come from a computer engineering background, so the traveling salesman problem immediately came to mind.

So, how could I solve it?

The most obvious approach in 2023 would be asking ChatGPT:

Chat GPT solution to the travelling salesman problem

Thanks, ChatGPT, but the solution is not that easy.

No one goes around different coordinates across the city in straight lines; there are apartment blocks in the way and different roads to take you there. Additionally, there is also the need to display the best route to the user in a graphical way, preferably on the map, so the driver understands which way to go.

Someone with a computer science background certainly knows that solving the TSP is an NP-hard problem in combinatorial optimization.

In other words, it’s not that simple.

Iterating all the possible combinations of solutions and measuring the outcome of each one works ok but up to a limit of cities. Each new city added to the problem will increase the response time exponentially.Nearest Neighbour algorithm to solve the TSP with 7 cities

Progressive improvement algorithms that use techniques that resemble linear programming work well for up to 200 cities.

Different approaches to this problem have created and developed multiple algorithms over the years, and there’s a lot of literature on this topic.

Fun facts about the traveling salesman problem:

The TSP has several applications, even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing.

I was at home with extra time, but not enough extra time to go back to my academic and engineering background. Plus, I didn’t want to overcomplicate the solution. How difficult could it be?

Famous last words.

I couldn’t find anything that was easy to set up and certainly not for free.

I needed something where the user would insert the list of addresses, the starting and end point, and the solution would provide the most efficient route that passed through all the inputted addresses.

So I decided to roll my sleeves up and get to work.

Solution

My approach was using the Mapbox GL JS to display the map and the Optimization API to calculate the best route.

Bye-bye, complex algorithms. By providing a list of coordinates, Mapbox not only gives you the shortest route and displays it on the map but also returns important metadata like estimated arrival time and distance between the different coordinates.

I also ended up using the Google Maps API for reverse geocoding (if a user clicks on the map, Google tells them what the address of that location is) and Google APIs that provide the right and complete address and have auto-completing capabilities, so users don’t have to type the full address.

After six hours of investigation and implementation, I solved the problem and shared it as a forge component so other users of the OutSystems community can take advantage of this approach.

How can you use this component?

Now, this component is available to all OutSystems users and can be found on the Forge — our Github for low-code components.

If you haven’t heard of OutSystems, it’s the #1 low-code platformⓇ (literally). The platform was designed to radically accelerate developer productivity and enable dev teams to build and deploy business-critical applications fast.

How can you start exploring the OutSystems platform? Here are two simple steps:

  1. Set up your Personal Environment: a free, full-fledged cloud environment to explore the platform's capabilities. Before you start, I recommend you check out all the limitations and uses of the free tier edition right here (scroll down to the bottom of the page to see a list).
  2. Proceed with the “Build a Mobile App in 5 min” tutorial: you can find it in the IDE after setting up your environment.

If you’re having trouble setting up your environment, take a look at this article. You can also check out our on-demand product demos. In addition, to ensure you’ve everything you need, we’ve also summed up what you need to get started with OutSystems.

Additional resources include:

 

And now you’re ready to solve the Traveling Salesman Problem.