Maximizing efficiency, minimizing costs

Maria João Silva

In 1736, Leonhard Euler solved the problem of the “Seven Bridges of the City of Königsberg.” His ingenious demonstration that no path crossed all seven bridges without visiting at least one bridge more than once gave rise to a new field of mathematics called Graph Theory. In the 1920s, this problem was expanded when Karl Menger formulated the “Messenger Problem.” It would become better known as the “Travelling Salesman Problem”, or TSP, but the premise was as simple as its precursor’s: what is the shortest path connecting a given number of locations that can be visited only once?

A depth of complexity hides underneath this deceptively simple question. And its relation to messengers and salesmen is only superficial. In fact, the TSP is one of the most famous problems in the field of optimization. It has inspired thousands of pages of books and articles throughout the 20th century and continues to do so to this day. It encompasses a vast body of knowledge that can be tapped into and applied to multiple scenarios.

The TSP, as formulated above, is the standard version of this optimization problem. As more and more constraints are added – perhaps there is more than one salesman, or each location is only accessible during a certain period of the day – its variants almost threaten to exhaust the alphabet: MTSP; MTSPTW; M/G-R/NR-TSP; etc.

In the real world, the most direct use-cases of the TSP would be the design of efficient transportation and delivery systems, optimizing distance travelled, time expended, and fuel costs. Its application to e-commerce delivery scheduling, airline routing, or car-sharing problems is almost immediate. Yet, it translates into a variety of other, sometimes unexpected, situations. In robotics, the TSP can help cut the time required by a robotic device to perform a sequence of operations. In operations planning, to determine the most efficient way to distribute jobs across workers. It can even apply to the development of efficient weapons targeting systems for military Defense systems.

As varied as its applications are, so are the solutions that have been envisioned over the years. Research efforts have proven Alexander Pushkin correct: “imagination is as necessary in geometry as it is in poetry.” Purely mathematical solutions to the TSP exist, though they are sometimes costly or impracticable. Often, it is preferable to use alternative heuristics to achieve a proper balance between implementation costs and potential gains.

A popular trend in heuristics is the emulation of nature. Genetic algorithms make use of the natural selection principle, implementing virtual evolution processes. Other algorithms take inspiration in the behaviour of social animals: from the use of pheromones by ants marking paths and communicating the location of food to the colony to the collective intelligence that emerges from the interactions between individuals within a flock of starlings in flight or a school of fish in the ocean. To add even more variety, these heuristics can be adapted and combined into hybrid models to fit any problem requirements and provide actionable solutions.

Optimization systems are a reality, feasible and reliable. The question then becomes: is all this added complexity necessary to answer the needs of day-to-day operations? Human know-how and experience can go a long way towards implementing a good-enough solution without incurring extra costs, but there are decisive benefits to using systematic optimization algorithms.

The difference between a good-enough and an optimal solution can be substantial, especially as operations grow. For example, what would even a small increase in efficiency represent for a factory? How much revenue would a manufacturer stand to gain if they could produce more in less time? The gain is two-way: maximizing production line output while minimizing the number of work hours required and machinery wear and tear.

Another potential benefit relates to business resiliency, especially in times of crisis. Worker know-how and experience are inextricable from the workers themselves, which can lead to bottlenecks and heavy dependence on a single irreplaceable element. This presents a risk factor. Process automation and the use of optimization tools as work-aids lessens risk, promotes flexibility and staff interchangeability, and relieves the pressure on workers.

Better management of human and material resources, better job allocation strategies, waste reduction, and increased business resiliency and efficiency: these are some of the potential benefits in the application of optimization systems.


Do you want to know more? Schedule a meeting with us here.

We will be glad to share our experience and success stories.