If your problem is a pure traveling salesperson problem, Gurobi probably should not be your first choice. Yes, you read that right, and yes you are on the Gurobi website. A specialized TSP solver is built specifically for that mathematical structure and will usually be the more natural baseline. Concorde is an example of a purpose-built solver (which was co-developed by one of the Gurobi founders, Bob Bixby) that has been around for over 25 years and still remains extremely performant for pure TSPs.

But most large routing problems in business are not pure TSPs.

They include vehicle capacities, customer time windows, driver rules, technician skills, inventory dependencies, charging stops, production schedules, service priorities, forbidden combinations, and company-specific logic. Once those requirements enter the model, the question changes from “What is the shortest tour?” to “What is the best feasible operating plan across all of our decisions and constraints?”

That is where Gurobi becomes valuable. It is not a specialist trying to win a pure-TSP speed contest. It is a general-purpose mathematical optimization solver that can model the routing problem the business actually has—and, when the solve reaches the required termination criterion, quantify or prove the quality of the result.

The practical guidance is simple:

• For a large, standard TSP, start with a specialized TSP solver.

• For a large routing problem dominated by speed and where a good feasible answer is enough, benchmark routing heuristics.

• For a TSP-like business problem with heterogeneous constraints, linked decisions, or a need for an optimality gap, benchmark Gurobi on the complete model.

Test the real decision: Request a free Gurobi evaluation license and benchmark the complete formulation—not a stripped-down TSP that omits the rules that matter in production.

Gurobi is not a specialized large TSP solver

The classical TSP asks for the shortest cycle that visits every location exactly once and returns to the start. That clean definition has inspired decades of specialized algorithms, cuts, heuristics, edge-elimination techniques, and data structures.

Gurobi can model and solve a TSP as a mixed-integer program. Its official example uses binary edge variables, degree constraints, and lazy constraints that eliminate disconnected subtours as they appear. This is a useful demonstration of branch-and-cut, but it is not evidence that a straightforward Gurobi formulation is the best implementation for a huge pure TSP.

Scale appears before the solver even begins its search. A dense symmetric model with one variable per undirected edge has

n(n − 1) / 2

possible edges. At 10,000 nodes (which is not very many, if one considers how many nodes even a small last-mile operation such as mail in a small suburb would handle in a given day), that is 49,995,000 binary variables. A directed model can contain 99,990,000 possible arcs.

Real routing problems only look like TSPs from a distance

A TSP has one route and one central rule: visit each node once. A production routing problem may have dozens of interacting rule families.

Consider a field-service operation. The plan may need to decide:

• which technician serves each job;

• the order of jobs on each route;

• whether the technician has the required certification and equipment;

• whether replacement parts are available;

• whether the appointment falls inside a customer time window;

• when breaks and overtime occur;

• which urgent jobs may displace lower-priority work;

• whether a job should be postponed at a stated penalty; and

• how routing choices affect inventory, staffing, or service-level targets.

This is not a TSP with a few decorative constraints. Assignment, scheduling, resource allocation, and routing are coupled. A route that is excellent in isolation may be infeasible—or expensive—for the business.

The same pattern appears in delivery, manufacturing, and network design:

• A delivery model can combine multiple depots, heterogeneous vehicles, capacities, loading compatibility, driver hours, time windows, pickups, returns, and electric-vehicle charging.

• A manufacturing sequence can combine travel or setup costs with tool changes, precedence, machine eligibility, batch rules, due dates, and downstream production capacity.

• A network plan can choose facilities, inventory levels, transportation modes, capacities, and routes together.

A specialist is powerful because it makes assumptions about structure. When business logic violates those assumptions, the choices are often to simplify the real problem, bolt on bespoke procedures, decompose it, or move to a modeling framework that can express the complete decision.

Gurobi’s strength is that capacities, logical implications, piecewise-linear costs, multiple objectives, resource balances, assignment decisions, and scheduling relationships can live in the same optimization model. The important comparison is no longer “How fast does each solver close a pure TSP?” It is “Which approach can solve the decision we actually need to make?”

See what belongs in the model: Review Gurobi’s vehicle routing FAQ for common routing decisions, constraints, and variants.

Heuristic solutions do not come with an optimality guarantee

Many routing products (ones that can handle more than the pure TSP) emphasize how quickly they can produce a route, even with business constraints. If a dispatcher needs a workable plan in 30 seconds, a fast heuristic may be more useful than an exact method that spends minutes improving a bound.

But “found a route” and “solved the model” are different claims.

A heuristic can return a feasible solution without a trustworthy lower bound. In that case, it cannot tell you whether the plan is optimal, 0.5% from optimal, or 20% from optimal. Running longer may improve the route, but improvement alone does not prove how much opportunity remains.

Gurobi tracks both sides of the problem when a valid bound is available:

• the incumbent, which is the best feasible solution found; and

• the bound, which limits how good any undiscovered solution could be.

For a minimization model, the relative MIP gap is based on the difference between those values. A 2% gap means something precise about the model: given the incumbent and valid bound, the solver has bounded the possible improvement to the reported gap. If it closes the gap to the required tolerance and returns an optimal status, it has proved optimality for that mathematical model, subject to the stated numerical tolerances.

How to choose the right approach

Start by classifying the real problem you are trying to solve.

Choose a specialized TSP solver when:

• the problem is genuinely a standard symmetric or asymmetric TSP;

• TSP-specific scale and performance matter most;

• the specialist supports the exact variant you need; and

• additional business rules are absent or limited enough to handle safely.

Choose a routing heuristic when:

• a good feasible route is more important than a quantified gap;

• decisions must be made under a very short deadline;

• the operational environment changes faster than an exact search can add value; and

• the product supports every constraint that determines real-world feasibility.

Choose Gurobi when:

• routing is coupled with assignment, scheduling, inventory, capacity, or network decisions;

• constraints are heterogeneous, unusual, or frequently changing;

• simplifying the model would create operationally invalid plans;

• a lower bound or optimality proof has business value; or

• the organization needs explicit control over the objective, tradeoffs, and stopping criteria.

Hybrid architectures are also common. A heuristic can supply an initial solution to Gurobi. A decomposition method can assign work in a master model and solve routing subproblems separately. Clustering can reduce scale, provided the team is honest about whether it preserves global optimality. There is no requirement that one algorithm do everything.

Large TSP solver FAQ

Is Gurobi a good solver for a pure TSP?

Usually not as the first choice. Yet, most real-world problems are not the canonical TSP.

When is Gurobi a better fit than a specialized TSP solver?

Gurobi becomes compelling when the route is only one part of a larger decision involving time windows, capacities, multiple resources, assignment, scheduling, inventory, logical rules, or custom business tradeoffs. The advantage is the ability to optimize these decisions together.

Does Gurobi guarantee the optimal solution?

If Gurobi terminates with an optimal status, it has proved optimality for the encoded model within the applicable tolerances. If it stops early, it can often report the best feasible solution, a valid bound, and the remaining MIP gap. It does not guarantee that every model will reach a proof within a practical time limit.

Do heuristic routing solvers guarantee optimality?

Generally, no. They may produce excellent solutions quickly, but without a valid bound they cannot quantify how far those solutions are from optimal. Some specialized TSP solvers are exact, however, so “specialized” and “heuristic” should not be used as synonyms.

Can a heuristic and Gurobi be used together?

Yes. A heuristic route can be supplied as a starting solution, while Gurobi enforces the full constraint set and attempts to improve the plan and its bound. A good start may help, but it does not guarantee a faster proof.

What should I benchmark?

Benchmark the full production problem on representative data and hardware. Compare feasibility, business objective, first-solution time, quality at fixed time limits, valid bounds, final gap, memory, and end-to-end runtime. The best tool is the one that meets the actual operational requirement.