What question did this study set out to answer?

The aim is to improve routing efficiency in the classical business traveler problem using new heuristics alongside traditional methods.

January 23, 2026Open Access

I- From Maps to Matrices: Revisiting the Business Traveler Problem

Key Points

The aim is to improve routing efficiency in the classical business traveler problem using new heuristics alongside traditional methods.
Revisiting classical algorithms like Dijkstra's and TSP
Introducing Greedy Matrix Reordering Method
Developing Coordinate-Based Combinatorial Optimization Model
Comparative evaluation of different routing techniques
New heuristic models yield faster and more optimal paths
Comparative evaluation shows effective convergence of discrete graph theory and linear programming
Unveiling scalable solutions for real-world navigation challenges

Abstract

The classical business traveler problem seeks the most efficient route between multiple cities, balancing cost and complexity.This study revisits its classical formulations—Dijkstra’s algorithm for exact single-source paths, the Traveling Salesperson Problem (TSP) for global tours, and the linear programming (LP) relaxation—and introduces two new heuristic models designed for modern routing: the Greedy Matrix Reordering Method and the Coordinate-Based Combinatorial Optimization Model. The first operates directly on distance matrices to yield fast, deterministic, and locally optimal paths. The second embeds cities in geometric space, applying convex-hull ordering, clustering, and quantum-compatible QUBO encoding for hierarchical optimization. Comparative evaluation shows how discrete graph theory, linear programming, and geometric heuristics converge toward scalable, interpretable solutions for real-world navigation systems.

I- From Maps to Matrices: Revisiting the Business Traveler Problem

Key Points

Abstract

Cite This Study