Distance & Duration Matrices¶

The solver requires travel costs between all pairs of locations. These are provided as one or two square matrices (N×N, where N is the total number of unique locations including depots):

Distance matrix — travel distance between locations (e.g., meters, km, or abstract units)
Duration matrix — travel time between locations (in seconds)

Single Matrix Behavior

You must provide at least one matrix. The solver always optimizes travel duration — the duration_matrix drives the objective function and all time-related scheduling. If you provide only distance_matrix, it is also used as the duration matrix.

The distance_matrix is used only for the max_distance vehicle constraint, which is measured on it. Set max_distance only on an instance that has a distance_matrix — otherwise validation will reject the input. Provide both matrices when your distances and durations differ: max_distance then limits real distance while the objective stays on duration.

Overview of Matrix Options¶

TQrouting offers several ways to obtain distance and duration matrices:

Direct matrix — provide a precomputed matrix
Euclidean distance — compute straight-line distances from coordinates
OSRM — compute road-network distances and travel times (remote server or local Docker)
Google Maps Routes API — production-grade global routing data

Each method is described in detail below.

Providing a Matrix Directly¶

The simplest approach — pass a precomputed matrix when creating the instance:

from tqrouting import VRPInstance, Customer, VehicleType, Location

instance = VRPInstance(
    customers=[
        Customer(location=Location(matrix_id=1), delivery_load=9),
        Customer(location=Location(matrix_id=2), delivery_load=4),
    ],
    fleet=[
        VehicleType(
            start_location=Location(matrix_id=0),
            end_location=Location(matrix_id=0),
            capacity_load=20,
            n_vehicles=3,
        ),
    ],
    distance_matrix=[
        [0, 10, 25],    # from location 0
        [10, 0, 15],    # from location 1
        [25, 15, 0],    # from location 2
    ],
    duration_matrix=[
        [0, 120, 300],  # seconds from location 0
        [120, 0, 180],  # seconds from location 1
        [300, 180, 0],  # seconds from location 2
    ],
)

The matrix is indexed by matrix_id — row i, column j gives the travel cost from location i to location j.

Any nested sequence works: a list of lists, tuples, a NumPy array or a pandas DataFrame (converted with tolist() / to_numpy() when the instance is serialised). NumPy scalars such as np.int64 or np.float64 are accepted in every numeric field (matrix_id, loads, capacities, times, n_vehicles, custom ids).

Matrix Size

The matrix must be square and include all locations: customers + depot(s). If you have 5 customers and 1 depot, the matrix is 6×6.

It must also include nothing else: the solver requires exactly max(matrix_id) + 1 rows. A matrix precomputed for more locations than this instance uses (for example one big matrix for all your addresses, solving a subset per day) is rejected by validation — slice it down to the rows and columns you reference first. Every customer needs its own matrix_id; two customers at the same address still get two rows (which may hold zeros), while a customer may share a depot's row.

Euclidean Distance (Coordinates)¶

EuclideanMatrixProvider computes straight-line (Euclidean) distances from Cartesian x/y coordinates. No external dependencies required — it ships with the base tqrouting package.

Most benchmark instances in the VRP literature use Euclidean distances, and often assume that duration equals the Euclidean distance. Many benchmarks also round distances to various precision levels. TQrouting supports this via the round_to parameter.

Beyond academic benchmarks, Euclidean distances are also useful for intra-logistics scenarios (e.g., warehouse routing, factory floor planning) and other problems where straight-line distance is a reasonable approximation.

from tqrouting import VRPInstance, Customer, VehicleType, Location
from tqrouting.matrix import EuclideanMatrixProvider

instance = VRPInstance(
    customers=[
        Customer(location=Location(x=20, y=35), delivery_load=9),
        Customer(location=Location(x=42, y=18), delivery_load=4),
        Customer(location=Location(x=55, y=60), service_time=5),
    ],
    fleet=[
        VehicleType(
            start_location=Location(x=0, y=0),
            capacity_load=20,
            n_vehicles=3,
        ),
    ],
)

# Computes sqrt((x1-x2)² + (y1-y2)²) for every pair
provider = EuclideanMatrixProvider()
instance.compute_distance_matrix(provider)

Options:

# Round to integers (common in CVRP benchmarks):
provider = EuclideanMatrixProvider(round_to=0)
instance.compute_distance_matrix(provider)

# Round to 2 decimal places:
provider = EuclideanMatrixProvider(round_to=2)
instance.compute_distance_matrix(provider)

# If distance == duration in your problem (common for benchmarks):
provider = EuclideanMatrixProvider()
instance.compute_distance_matrix(provider)
instance.compute_duration_matrix(provider)

EuclideanMatrixProvider parameters:

Parameter	Type	Default	Description
`round_to`	`int` or `None`	`None`	Decimal places to round. `0` for integer distances (common in CVRP benchmarks). `None` keeps full precision.

Matrix precision¶

Before searching, the solver rounds every duration matrix — computed by a provider or supplied by you — to decimal decimal places, 1 by default. Reported durations and arrival times are computed on the rounded values, and so are the arrival windows the SDK computes afterwards (earliest_arrival, latest_arrival, set_departure_time()), so they agree with the solver's eta. Your own duration_matrix is left untouched. When you supply no distance_matrix, distances are read from the duration matrix, so distances and a distance_weight objective are rounded with it.

Why: the solver treats any time-window overrun as a violation, however small. A matrix carrying more decimal places than your time windows lets arithmetic noise produce overruns of a tiny fraction of a unit; those surface as spurious violations in the result and the search spends its time on them. Rounding to a tenth of a unit puts a floor under every real overrun.

decimal counts decimal places in the unit of your matrix. One place is right for fine units; with OSRM durations in seconds, for example, it is a tenth of a second. When your time windows and service times are whole numbers, decimal=0 is better still: the floor under an overrun is then a whole unit, and on large time-windowed instances we have seen the search settle faster and on better routes, at the price of durations rounded to whole units. With a coarse unit such as hours, pass decimal=2 or 3 so that rounding stays well below the precision of your time windows — the solver warns when your time data carries more decimal places than the rounding keeps.

solution = router.solve(instance)             # durations rounded to 0.1 (default)
solution = router.solve(instance, decimal=0)  # integers
solution = router.solve(instance, decimal=3)  # coarse units, e.g. hours; warns
solution = router.solve(instance, decimal=-1) # no rounding; warns

Anything other than 0 or 1 is at your own risk and emits a UserWarning. The engine accepts -1 to 9.

Note

compute_distance_matrix() and compute_duration_matrix() assign matrix_ids for you: each customer gets its own, and depots at the same coordinates share one. When every location already has a matrix_id, the ids are kept and the matrix is computed in their order. If the other matrix is present and some location has no matrix_id, the call raises a ValidationError.

OSRM (Street Network Routing)¶

OSRM provides road-network distances and durations based on OpenStreetMap data. TQrouting supports two OSRM workflows:

Remote OSRM Server¶

Connect to any running OSRM instance. Use this when you already have an OSRM server (self-hosted or the public demo server for small problems). No Docker required.

Warning

The public OSRM demo server (router.project-osrm.org) has a limit of 50 locations per table request. For larger problems, use a self-hosted OSRM instance or OSRMLocalManager.

from tqrouting import VRPInstance, Customer, VehicleType, Location
from tqrouting.matrix import OSRMMatrixProvider

instance = VRPInstance(
    customers=[
        Customer(location=Location(lat=48.137, lon=11.575), delivery_load=9),
        Customer(location=Location(lat=48.265, lon=11.671), delivery_load=4),
    ],
    fleet=[
        VehicleType(
            start_location=Location(lat=48.140, lon=11.558),
            capacity_load=20,
            n_vehicles=3,
        ),
    ],
)

provider = OSRMMatrixProvider(base_url="https://router.project-osrm.org")
instance.compute_distance_matrix(provider)    # meters
instance.compute_duration_matrix(provider)    # seconds

OSRMMatrixProvider parameters:

Parameter	Type	Default	Description
`base_url`	`str`	`"https://router.project-osrm.org"`	OSRM server URL
`profile`	`str`	`"car"`	Routing profile (`"car"`, `"bicycle"`, `"foot"`)
`timeout`	`int`	`60`	HTTP timeout in seconds
`max_workers`	`int`	`4`	Parallel threads for chunk requests (see below)
`max_snap_distance`	`float` or `None`	`5000`	Largest distance in meters between a location and the road OSRM snaps it to; a location farther away raises `OSRMError`. `None` disables the check

Parallel Matrix Computation¶

For large coordinate sets (more than 50 locations), OSRMMatrixProvider automatically splits the matrix computation into parallel chunk requests. Each chunk computes a slice of matrix rows by sending a separate HTTP request with a subset of sources indices. This typically yields a 2–4× speedup on multi-core machines.

Below 50 locations — a single request (no overhead from chunking)
Above 50 locations — sources are split into max_workers chunks (minimum 50 sources per chunk)
Set max_workers=1 to disable parallelism

# Speed up large matrices with more parallel workers:
provider = OSRMMatrixProvider(
    base_url="http://my-osrm-server:5000",
    max_workers=8,
)

Install the extra

pip install tqrouting[osrm]

The package comes from the Terra Quantum index — register it once as described in Installation.

Local OSRM with Docker (OSRMLocalManager)¶

Automatically downloads map data, preprocesses it, and starts a local OSRM server in Docker. Use this when you don't have an OSRM server running and want a fully automated setup. Map data is cached locally for fast subsequent runs.

from tqrouting.matrix import OSRMLocalManager

with OSRMLocalManager(region="europe/germany/bayern") as provider:
    instance.compute_distance_matrix(provider)
    instance.compute_duration_matrix(provider)

solution = router.solve(instance)

The manager handles the full lifecycle:

Downloads the .osm.pbf file from Geofabrik (cached on disk)
Preprocesses the map data for fast routing (cached on disk)
Starts a Docker container with the OSRM HTTP server
Stops the container when the context manager exits

OSRMLocalManager parameters:

Parameter	Type	Default	Description
`region`	`str`	—	Geofabrik region path (e.g., `"europe/germany/bayern"`)
`profile`	`str`	`"car"`	Routing profile
`algorithm`	`str`	`"mld"`	Preprocessing algorithm (`"mld"` or `"ch"`)
`data_dir`	`Path`	`~/.cache/tqrouting/osrm`	Cache directory
`port`	`int`	`5001`	Host port for the OSRM server
`max_table_size`	`int`	`10000`	Max coordinates per table request (`--max-table-size` flag)
`max_workers`	`int`	`4`	Parallel threads for the returned `OSRMMatrixProvider`
`max_snap_distance`	`float` or `None`	`5000`	Passed to the returned `OSRMMatrixProvider`
`auto_update`	`bool`	`True`	Check for map updates on each start (set `False` to use cached data without network calls)
`force_download`	`bool`	`False`	Re-download map even if cached
`force_preprocess`	`bool`	`False`	Re-preprocess even if cached
`stop_behavior`	`StopBehavior`	`KEEP`	What to clean up on exit

Stop behaviors:

Value	Container	Cached Data	Next Start
`StopBehavior.KEEP`	Stopped (kept)	Kept	Instant restart
`StopBehavior.REMOVE`	Removed	Kept	New container, skip download
`StopBehavior.REMOVE_ALL`	Removed	Deleted	Full re-download

Geofabrik regions follow the URL structure at download.geofabrik.de. Examples:

"europe/germany/bayern"
"europe/france"
"north-america/us-west"
"asia/japan"

Install the extra

pip install tqrouting[osrm-local]

The package comes from the Terra Quantum index — register it once as described in Installation.

Requirements

Docker must be installed and running.

Google Maps Routes API¶

For production-grade global routing data:

from tqrouting.matrix import GoogleMatrixProvider

provider = GoogleMatrixProvider(api_key="YOUR_GOOGLE_MAPS_API_KEY")
instance.compute_distance_matrix(provider)    # meters
instance.compute_duration_matrix(provider)    # seconds

Authentication (in priority order):

api_key parameter in the constructor
GOOGLE_MAPS_API_KEY environment variable
Application Default Credentials (ADC) — for GCP deployments

GoogleMatrixProvider parameters:

Parameter	Type	Default	Description
`api_key`	`str`	`None`	Google Maps API key
`travel_mode`	`RouteTravelMode`	`DRIVE`	Travel mode
`max_workers`	`int`	`8`	Concurrent API requests for large matrices

For large coordinate sets, the provider automatically chunks requests (max 25×25 per API call) and runs them concurrently.

Install the extra

pip install tqrouting[google]

The package comes from the Terra Quantum index — register it once as described in Installation.

Summary¶

Method	Provider Class	Coordinates	Extra Required
Direct matrix	—	`matrix_id`	None
Euclidean	`EuclideanMatrixProvider`	`x`, `y`	None
OSRM (remote)	`OSRMMatrixProvider`	`lat`, `lon`	`tqrouting[osrm]`
OSRM (local Docker)	`OSRMMatrixProvider` via `OSRMLocalManager`	`lat`, `lon`	`tqrouting[osrm-local]`
Google Maps	`GoogleMatrixProvider`	`lat`, `lon`	`tqrouting[google]`