Routing API

Optimal path finding and route optimization for geographic points.

Main Functions

allocator.shortest_path(data: str | DataFrame | ndarray | list, method: str = 'christofides', distance: str = 'euclidean', **kwargs) → RouteResult[source]

Find shortest path through geographic points (TSP).

Parameters:

  • data – Input data (file path, DataFrame, numpy array, or list)

  • method – TSP solving method (‘christofides’, ‘ortools’, ‘osrm’, ‘google’)

  • distance – Distance metric (‘euclidean’, ‘haversine’, ‘osrm’, ‘google’)

  • **kwargs – Additional method-specific arguments

Returns:

RouteResult with optimal route and total distance

Example

>>> result = shortest_path('points.csv', method='ortools')
>>> print(result.route)  # Optimal visiting order
>>> print(result.total_distance)  # Total route distance

Core Routing Module

Modern routing API for allocator package.

allocator.api.route.shortest_path(data: str | DataFrame | ndarray | list, method: str = 'christofides', distance: str = 'euclidean', **kwargs) → RouteResult[source]

Find shortest path through geographic points (TSP).

Parameters:

  • data – Input data (file path, DataFrame, numpy array, or list)

  • method – TSP solving method (‘christofides’, ‘ortools’, ‘osrm’, ‘google’)

  • distance – Distance metric (‘euclidean’, ‘haversine’, ‘osrm’, ‘google’)

  • **kwargs – Additional method-specific arguments

Returns:

RouteResult with optimal route and total distance

Example

>>> result = shortest_path('points.csv', method='ortools')
>>> print(result.route)  # Optimal visiting order
>>> print(result.total_distance)  # Total route distance
allocator.api.route.tsp_christofides(data: DataFrame | ndarray, distance: str = 'euclidean', **kwargs) → RouteResult[source]

Solve TSP using Christofides algorithm (approximate).

Parameters:

  • data – Input data as DataFrame or numpy array

  • distance – Distance metric

  • **kwargs – Additional arguments

Returns:

RouteResult with approximate optimal route

allocator.api.route.tsp_google(data: DataFrame | ndarray, api_key: str, **kwargs) → RouteResult[source]

Solve TSP using Google Maps distance matrix and nearest neighbor heuristic.

Parameters:

  • data – Input data as DataFrame or numpy array

  • api_key – Google Maps API key

  • **kwargs – Additional arguments

Returns:

RouteResult with route using Google’s road network

allocator.api.route.tsp_ortools(data: DataFrame | ndarray, distance: str = 'euclidean', **kwargs) → RouteResult[source]

Solve TSP using Google OR-Tools (exact for small problems).

Parameters:

  • data – Input data as DataFrame or numpy array

  • distance – Distance metric

  • **kwargs – Additional arguments

Returns:

RouteResult with optimal route

allocator.api.route.tsp_osrm(data: DataFrame | ndarray, osrm_base_url: str | None = None, **kwargs) → RouteResult[source]

Solve TSP using OSRM distance matrix and nearest neighbor heuristic.

Parameters:

  • data – Input data as DataFrame or numpy array

  • osrm_base_url – Custom OSRM server URL

  • **kwargs – Additional arguments

Returns:

RouteResult with route using real road network

Routing Algorithms Module

Pure routing/TSP algorithm implementations.

allocator.core.routing.solve_tsp_christofides(points: ndarray, distance_method: str = 'euclidean', **distance_kwargs) → tuple[float, list[int]][source]

Solve TSP using Christofides algorithm (approximate).

Parameters:

  • points – Array of [lon, lat] coordinates

  • distance_method – Distance calculation method

  • **distance_kwargs – Additional args for distance calculation

Returns:

(total_distance, route) tuple

allocator.core.routing.solve_tsp_google(points: ndarray, api_key: str, **kwargs) → tuple[float, list[int]][source]

Solve TSP using Google Maps Directions API.

Parameters:

  • points – Array of [lon, lat] coordinates

  • api_key – Google Maps API key

  • **kwargs – Additional arguments

Returns:

(total_distance, route) tuple

allocator.core.routing.solve_tsp_ortools(points: ndarray, distance_method: str = 'euclidean', **distance_kwargs) → tuple[float, list[int]][source]

Solve TSP using Google OR-Tools.

Parameters:

  • points – Array of [lon, lat] coordinates

  • distance_method – Distance calculation method

  • **distance_kwargs – Additional args for distance calculation

Returns:

(total_distance, route) tuple

allocator.core.routing.solve_tsp_osrm(points: ndarray, osrm_base_url: str | None = None, **kwargs) → tuple[float, list[int]][source]

Solve TSP using OSRM trip service.

Parameters:

  • points – Array of [lon, lat] coordinates

  • osrm_base_url – Custom OSRM server URL

  • **kwargs – Additional arguments

Returns:

(total_distance, route) tuple

Usage Examples

Basic Route Optimization

import pandas as pd
import allocator

# Delivery locations
locations = pd.DataFrame({
    'longitude': [100.5, 100.6, 100.7, 100.8],
    'latitude': [13.7, 13.8, 13.9, 14.0],
    'stop_id': ['A', 'B', 'C', 'D']
})

# Find optimal route using OR-Tools
route = allocator.shortest_path(
    data=locations,
    method='ortools',
    distance='haversine'
)

print(f"Total distance: {route['total_distance']:.2f}km")
print("Route order:")
for i, stop in enumerate(route['data']['stop_id']):
    print(f"  {i+1}. {stop}")

Advanced Routing Options

# Route optimization with custom start/end points
route = allocator.shortest_path(
    data=locations,
    method='ortools',
    start_location=0,  # Start at first location
    end_location=0,    # Return to start (round trip)
    distance='haversine',
    time_limit=10      # 10 second optimization limit
)

Routing Methods

OR-Tools Solver

  • Method: ortools

  • Performance: Optimal solutions, fastest for medium datasets

  • Best for: Production applications, balanced performance/quality

Nearest Neighbor

  • Method: nearest

  • Performance: Fast heuristic, approximate solutions

  • Best for: Quick estimates, large datasets

Christofides Algorithm

  • Method: christofides

  • Performance: Optimal solutions, slower

  • Requires: pip install "allocator[algorithms]"

  • Best for: Small datasets requiring optimal solutions

Distance Methods

All routing methods support multiple distance calculations:

  • haversine: Geographic great-circle distance (recommended)

  • euclidean: Straight-line distance (fast approximation)

  • osrm: Driving distance via OSRM API

  • googlemaps: Driving distance via Google Maps API

Return Format

The shortest_path function returns a dictionary with:

  • data: DataFrame with route order and distances

  • total_distance: Total route distance in kilometers

  • method: Algorithm used

  • distance: Distance calculation method

  • metadata: Algorithm-specific information (iterations, solve time, etc.)

Performance Considerations

  • Small problems (≤15 points): All methods perform well

  • Medium problems (15-50 points): OR-Tools recommended

  • Large problems (50+ points): Consider nearest neighbor or sampling

  • API rate limits: Use haversine/euclidean for development