The Traveling Salesperson Problem

Every working day, without knowing its name, a courier in Jakarta solves a variation of a problem that has occupied the best mathematical minds for nearly a century. Given a list of stops and their distances, what is the cheapest route that visits each one exactly once before returning to the depot?

That question is the Traveling Salesperson Problem, also known as the Traveling Salesman Problem in older literature, and its reputation as a puzzle greatly underestimates its scope. It is less of a problem than a shape, a hidden structure that appears whenever a limited resource must pass through a large number of points in an intelligent order.

Understanding that shape and why it cannot be solved perfectly at scale is one of the most useful things a manager can learn. Most writing about the Traveling Salesperson Problem ends with delivery vans. This article argues for something bigger.

The problem is worth studying in business school not because it explains logistics, though it does, but because it provides a disciplined answer to a question that every executive must face: what should you do when the perfect decision is demonstrably out of reach and time is running out?

The problem's solution, refined over seventy years of research, is a doctrine for acting effectively under intractability that extends far beyond the road.

What the Traveling Salesperson Problem Really Asks

The formal statement is almost embarrassingly simple. A traveler has a list of cities and a distance table and wants to find the shortest closed tour that passes through each city once. Anyone can understand the goal, and for five or six cities, anyone can determine the answer thru inspection. Every word contains the potential for trouble.

The number of possible tours grows rapidly as cities are added. Ten stops already enable 181,440 distinct routes. Twenty stops allow for more than sixty quadrillion. A route with the number of stops a single delivery driver makes in a morning generates more possible orderings than there are atoms in the observable universe, so no amount of optimization or computing power can simply try them all.

This complexity is the property that distinguishes the problem as profound rather than fiddly. The Traveling Salesperson Problem is classified as NP-hard by mathematicians, which means that no known method can guarantee the optimal tour for large instances without, in the worst-case scenario, exerting more effort than any machine can sustain.

The result, formalized through the theory of computational complexity in the 1970s, established that a genuinely fast and always optimal algorithm for the problem would resolve one of the deepest open questions in all of computer science, but none has emerged after decades of effort (Mathematical Association of America, 2006).

The problem is simple to pose, simple to validate once an answer is provided, and extremely difficult to solve with certified perfection. The entire practical value of the subject lies in the space between these three facts.

The Same Shape Everywhere: Beyond the Delivery Van

The first novel concept worth considering is that routing goods is only the most visible aspect of the problem. The same mathematical shape governs a surprising variety of activity. In electronics manufacturing, a machine that drills thousands of holes in a printed circuit board solves a traveling salesman problem by determining how many boards the factory can produce in a shift.

One of genomics' earliest scientific applications is the reassembly of fragments of sequenced DNA into a whole genome. In astronomy, scheduling a telescope that must slew between celestial targets while wasting as little time as possible, a task now relevant to massive modern surveys, is essentially the same question (Gurobi Optimization, n.d.; A comprehensive review of metaheuristics, 2026).

It is used to aim instruments in crystallography, route robotic inspection arms, and order jobs on machines. When applied to work that does not clearly require travel, the concept becomes genuinely useful to a manager. A field service company scheduling engineers across a region, an auditor planning site visits, a sales team designing territories, and a warehouse worker walking an order-picking route between shelves are all examples of a Traveling Salesperson Problem or its close relative.

Recognizing the shape is a managerial skill in and of itself, because what appears to be an unavoidable cost of operations is often a routing problem in disguise, and routing problems can be improved.

The Price of Intractability as a Management Doctrine

Herein lies the most profound lesson and the reason the problem appears in a management curriculum rather than just a mathematics one. Because certified perfect answers are unattainable at realistic sizes, the practical world avoids pursuing them, and the manner in which it does so is instructive.

The field categorizes its tools by purpose. When optimality is truly important and time is abundant, as in the layout of a circuit that will be manufactured in the millions, exact methods such as the cutting plane and branch-and-cut algorithms inside solvers like Concorde can prove the best answer for surprisingly large instances, a lineage that runs straight back to the 1954 breakthrough in which Dantzig, Fulkerson, and Johnson solved a forty-nine-city tour of the United States and proved it optimal (Dantzig, Fulkerson, & Johnson, 1954). The largest instance ever solved to proven optimality, a pattern of 85,900 points from microchip design, was cracked in this manner in 2006 (Gurobi Optimization, n.d.).

When speed is more important than the final fraction of a percent, as it is for a courier replanning routes in the morning, managers turn to heuristics and metaheuristics, such as nearest neighbor construction, local search, and Lin and Kernighan's celebrated procedure, which finds excellent tours in seconds without promising the theoretical minimum. The economist and Nobel laureate Herbert Simon coined the term "satisficing," which refers to the deliberate acceptance of a solution that is good enough rather than perfect, on the grounds that the pursuit of perfection can cost more than the imperfection it eliminates.

A route that is within two percent of the theoretical best and is completed before the vans leave is far more valuable than a perfect route that arrives a week late. Learning to distinguish which problems merit the pursuit of optimality and which are better served by a quick and sufficient answer is one of the most transferable skills a leader can possess, and the Traveling Salesperson Problem teaches it with clarity that no abstract lecture on decision-making can.

The UPS Case, and Its Uncomfortable Second Half

The most well-known business application is that of the American carrier UPS, whose operations research group spent nearly a decade developing a routing system known as ORION, which stands for On Road Integrated Optimization and Navigation, and which the company describes as solving the traveling salesman problem throughout its network.

A single route, with roughly one hundred and twenty to one hundred and seventy-five stops, can be sequenced in approximately two hundred thousand ways, far exceeding human intuition. ORION is expected to save approximately one hundred million miles of driving and ten million gallons of fuel per year, reduce carbon emissions by approximately one hundred thousand metric tons, and deliver annual savings of $300 to $400 million, earning UPS the profession's Franz Edelman Award in 2016 (Institute for Operations Research and the Management Sciences, 2016).

The system's preference for right turns, which saves drivers the time and risk of crossing oncoming traffic, has become a well-known example of counterintuitive optimization.

However, a research-level account must include the second half of the story, which is often omitted in celebratory summaries. Route optimization isn't neutral. ORION is powered by a continuous stream of telematics and location data from over a hundred and twenty-five thousand vehicles, which means that the same system that saves fuel also monitors drivers minute by minute, and experienced drivers initially resisted sequences that contradicted their hard-earned knowledge of their territories (Klover.ai, 2025).

A single algorithm produces both efficiency gains and increased workplace surveillance, and the 2023 labor contract covering UPS drivers included no specific protection against job losses due to automation, a silence that foreshadows more difficult negotiations to come (Klover.ai, 2025). For a business school, the goal is not to condemn technology but to teach students that an optimization includes a human ledger in addition to a financial one and that a competent manager reads both columns.

The mathematics that saves a mile also transforms a job.

The Traveling Salesperson Problem in Jakarta

For an Indonesian reader, the issue is not an imported abstraction, but rather a local condition of unusual weight. Indonesia is an archipelago of over seventeen thousand islands, and moving goods across it is extremely difficult, which is why national logistics costs have been estimated at 14.29 percent of GDP under the government's own standardized assessment, one of the highest ratios in the region. Lowering that figure to around 8% has become an explicit policy goal, implying that vehicle routing efficiency is a lever for national competitiveness rather than a private optimization (Ken Research, 2025; Global Risk Community, 2025).

In this context, applying the mathematics of the shortest tour yields a public benefit. The pressure is increasing because online retail is outpacing the infrastructure that supports it. Indonesian online commerce reached a gross merchandise value of nearly $71 billion in 2025, within a digital economy that research by Google, Temasek, and Bain and Company projects will exceed $130 billion, and fulfilling those orders has made last-mile delivery the largest and fastest-moving segment of the country's logistics market (Global Risk Community, 2025; Mordor Intelligence, 2026).

The city's dense and often improvised delivery networks, from parcel couriers to on-demand riders who thread between cars, are constantly running crude and continuous solutions to the traveling salesperson problem. Jakarta, the most congested delivery environment in the country, is where arithmetic bites the hardest, and a student can see problems being solved imperfectly on every street.

The Frontier, Honestly: Machine Learning and Quantum Hope

Because the problem is a standard benchmark for new computing ideas, it receives a lot of attention, and a truly useful article should separate the signal from the noise. Two frontiers dominate the current excitement.

The first is machine learning, in which researchers train neural networks to create effective tours by learning a routing heuristic from data rather than designing one by hand, an approach pioneered in work on neural combinatorial optimization (Bello, Pham, Le, Norouzi, and Bengio, 2017).

These methods are promising, particularly for generating fast approximate solutions at scale, but they have not replaced the mature classical heuristics that continue to dominate industrial routing. The second frontier is quantum computing, and honesty is especially important here because marketing often outperforms evidence.

Careful benchmarking reveals that current quantum methods for the Traveling Salesperson Problem are constrained by hardware noise and low qubit counts, struggling even with instances of fewer than ten cities, whereas a well-tuned classical method such as simulated annealing routinely achieves solutions that are extremely close to optimal across a wide range of sizes (Scientific Reports, 2025; Grover et al., 2026).

Recent literature generally agrees that a decisive quantum advantage for this problem is unlikely to arrive soon using general-purpose approaches. The managerial lesson is valuable: a leader who understands why the shortest route is difficult can also recognize when a vendor's promise of a technological miracle warrants skepticism rather than a signature.

Why the Traveling Salesperson Problem Belongs in a Business Classroom

The Traveling Salesperson Problem is almost an ideal case at Raffles Jakarta, an international design and business school on Jalan M.H. Thamrin, because it refuses to be contained within a single subject. It teaches students mathematics, operations management, information systems, cost economics, and automation ethics all at the same time, and it demonstrates that a formula and a profit margin are frequently the same object when viewed from two perspectives.

The Business Administration program, which combines core management skills with digital commerce, contemporary marketing, and a strategic management capstone, is ideal for testing a routing case as a real-world business decision rather than a textbook exercise (Raffles Jakarta, 2026a).

The Master of Business Administration program expands on the analysis with modules in Managerial Economics; Information System Management and Strategy; Research Methodology; and Ethics, Corporate Governance, and Social Responsibilities, the latter of which addresses the labor and surveillance issues raised by route optimization (Raffles Jakarta, 2026b).

The purpose of teaching a case like this is not to transform business students into algorithm designers. It is to provide them the confidence to sit across the table from the analysts and engineers who create these systems, to ask the right questions, to weigh a saved mile against a monitored worker, and to judge both the numbers and the vendors who supply them.

A graduate who understands why the Traveling Salesperson Problem is difficult, why a sufficiently effective enough route is usually the best commercial choice, and how much such choices cost the people who make them is one who can turn mathematics into money without losing sight of the consequences.

That is not an academic refinement in a city where logistics is both a daily source of frustration and a tremendous opportunity. It is a competitive advantage.

Conclusion

The Traveling Salesperson Problem has captivated scholars and businesses for nearly a century because it balances two truths that rarely coexist. It is simple enough for a child to state but difficult enough that even the best mathematicians cannot solve its most complex cases to perfection, and the space between those facts is precisely where real management occurs.

Its structure is hidden within logistics, manufacturing, science, and knowledge work alike; its refusal to accept a perfect answer teaches the discipline of making a good enough decision; and its most famous success story contains an honest warning about the human cost of optimization.

For a business school and for a city like Jakarta, where problems are solved and resolved on every congested street, the final lesson is the most important to carry into a career: wisdom is not the refusal to accept imperfection but the judgment to know when a very good answer, arrived at in time to act on, is the best of all.

FREQUENTLY ASKED QUESTIONS

What is the Traveling Salesperson Problem?The Traveling Salesperson Problem is a classic optimization question that asks for the shortest possible route that visits a set of locations exactly once and returns to the starting point. It is a foundational problem in mathematics, computer science, and operations research, and it appears in logistics, manufacturing, and scientific scheduling.

Why can the Traveling Salesperson Problem not be solved perfectly? It cannot be solved perfectly at scale because the number of possible routes grows explosively with each added stop, and the problem is classified as NP-hard. No known method guarantees the optimal route for large instances within a practical amount of time, so businesses rely on approximate methods that yield excellent routes quickly.

Where is the Traveling Salesperson Problem used besides deliveries? Beyond delivery, the problem governs printed circuit board drilling, DNA sequencing, telescope observation scheduling, robotic inspection, and machine job ordering. It also underlies office tasks such as field service scheduling, audit visit planning, sales territory design, and warehouse order picking.

How does UPS use the Traveling Salesperson Problem? UPS uses a route optimization system called ORION that solves Traveling Salesperson-style problems across its network. It is estimated to save the company around one hundred million miles of driving and three hundred to four hundred million dollars each year, though it also intensifies data-driven monitoring of drivers.

Why does the traveling salesman problem matter for Indonesia?It matters because Indonesia's national logistics costs are high, estimated at 14.29 percent of gross domestic product, and the government aims to reduce them. Efficient routing across the country's archipelagic geography is a genuine economic priority, and Jakarta is its most demanding testing ground.

Can quantum computers solve the Traveling Salesperson Problem better than classical ones?Not yet, according to current evidence. Quantum methods still struggle with noise and small qubit counts, even for small instances, while well-tuned classical heuristics like simulated annealing consistently find near-optimal routes. Claims of an imminent quantum breakthrough for this problem deserve caution.

Arman PourEisa

Marketing Manager

Raffles Indonesia

References

Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2017). Neural combinatorial optimization with reinforcement learning. arXiv. https://arxiv.org/abs/1611.09940

A comprehensive review of metaheuristics for the modern traveling salesman problem and drone-assisted delivery. (2026). Algorithms, 19(4), 278. https://doi.org/10.3390/a19040278

Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a large-scale traveling-salesman problem (Paper P-510). RAND Corporation. https://www.rand.org/pubs/papers/P510.html

Global Risk Community. (2025, October 6). Indonesia e-commerce logistics market growth, size, share, and report 2025-2033. https://globalriskcommunity.com/market_research/indonesia-e-commerce-logistics-market-growth-size-share-and-repor

Grover, K., et al. (2026). A quantitative framework for comparing classical and quantum algorithms for the traveling salesman problem. arXiv. https://arxiv.org/html/2607.24581

Gurobi Optimization. (n.d.). The traveling salesman problem demo. https://www.gurobi.com/resources/demos/the-traveling-salesman-problem-demo

Hoffman, K. L., Padberg, M., & Rinaldi, G. (2013). Traveling salesman problem. George Mason University. http://seor.vse.gmu.edu/~khoffman/TSP_Hoffman_Padberg_Rinaldi.pdf

Institute for Operations Research and the Management Sciences. (2016). UPS: O.R. and analytics success story. https://www.informs.org/Impact/O.R.-Analytics-Success-Stories/UPS

Ken Research. (2025). Indonesia logistics market 2025-2031. https://www.kenresearch.com/industry-reports/indonesia-logistics-market

Klover.ai. (2025, July 28). UPS's AI strategy: Analysis of dominance in logistics AI. https://www.klover.ai/ups-ai-strategy-analysis-of-dominance-in-logistics-ai/

Locus. (2025, May 30). Traveling salesman problem: What is it and how to solve it. https://locus.sh/blogs/travelling-salesman-problem/

Mathematical Association of America. (2006). The traveling salesman problem: A computational study [Review]. https://old.maa.org/press/maa-reviews/the-traveling-salesman-problem-a-computational-study

Mordor Intelligence. (2026). Indonesia e-commerce logistics market size, share, and growth trends report. https://www.mordorintelligence.com/industry-reports/indonesia-ecommerce-logistics-market

Raffles Jakarta. (2026a). Business Administration. https://www.raffles-indonesia.com/business-administration

Raffles Jakarta. (2026b). MBA Jakarta 2026: Think Bigger. https://www.raffles-indonesia.com/think-bigger-mba-jakarta

Routific. (2024, April 18). Algorithms for the traveling salesman problem. https://www.routific.com/blog/travelling-salesman-problem

Scientific Reports. (2025). Quantum annealing applications, challenges, and limitations for optimisation problems compared to classical solvers. Scientific Reports, 15. https://www.nature.com/articles/s41598-025-96220-2