RCH Solver

RCH — a solver for the Heterogeneous Multi-Agent Travelling Salesman Problem (MTSP).

This package wraps the high-performance C++ solver core via pybind11 and makes it available as a regular Python library.

Installation

Prerequisites

• Python >= 3.8
• A C++17 compiler (g++ >= 7, clang++ >= 5)
• CMake >= 3.15
• uv
• matplotlib (only needed for visualization helpers)

Install from PyPI with uv

uv venv
. .venv/bin/activate
uv pip install PyRCH

If you also want plotting helpers:

uv venv
. .venv/bin/activate
uv pip install "PyRCH[viz]"

Install from source

cd MTSP-Solver

# Core package only
uv sync

# Core package + visualization helpers
uv sync --extra viz

# Development environment + visualization helpers
uv sync --group dev --extra viz

This project documents uv as the supported environment workflow for source and development installs.

Quick Start

1. Solve a JSON problem file

Assume your JSON has been saved as problem.json in the current directory.

import pyrch

result = pyrch.solve("problem.json", time_limit=10)

print(result["status"])        # "success" or "failed"
print(result["timeout"])       # True if time-limit was reached
print(result["statistics"])    # {"max_cost": ..., "sum_cost": ..., "solve_time": ..., ...}

for route in result["routes"]:
    print(f"Agent {route['agent_id']}: path={route['path']}, cost={route['cost']}")

# Anytime improvement history
for snapshot in result["anytime"]:
    print(f"  t={snapshot['time']:.3f}s  max_cost={snapshot['max_cost']:.2f}")

2. Solve from a Python dict

import pyrch

problem_data = {
    "nodes": [
        {"id": 0, "x": 0.0, "y": 0.0, "type": "depot"},
        {"id": 1, "x": 1.0, "y": 2.0, "type": "target"},
        {"id": 2, "x": 3.0, "y": 1.0, "type": "target"},
    ],
    "agents": [
        {"id": 0, "type": "UAV", "start_node": 0, "end_node": 0},
        {"id": 1, "type": "UAV", "start_node": 0, "end_node": 0},
    ],
    "costs": {
        "UAV": [
            [0.0, 2.24, 3.16],
            [2.24, 0.0, 2.24],
            [3.16, 2.24, 0.0],
        ]
    },
    "options": {
        "return_to_end": True,
        "objective": "min_max"
    }
}

result = pyrch.solve(problem_data, time_limit=5)
print(result)

3. Planner API (recommended)

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import pyrch

planner = pyrch.Planner()

# Add nodes
planner.add_depot(0, x=0.0, y=0.0)
planner.add_target(1, x=1.0, y=2.0)
planner.add_target(2, x=3.0, y=1.0)

# Add agents
planner.add_agent(agent_id=0, agent_type="UAV", start_node=0, end_node=0, time_limit=6.0)
planner.add_agent(agent_id=1, agent_type="UGV", start_node=0, end_node=0, time_limit=9.0)

# Set cost matrices (one per agent type)
planner.set_cost_matrix("UAV", [
    [0.0, 2.24, 3.16],
    [2.24, 0.0, 2.24],
    [3.16, 2.24, 0.0],
])
planner.set_cost_matrix("UGV", [
    [0.0, 1.80, 4.20],
    [1.80, 0.0, 2.90],
    [4.20, 2.90, 0.0],
])

# Add constraints (optional)
planner.add_assignment(1, ["UAV"])
planner.add_assignment(2, ["UGV"])
planner.add_time_window(1, start=0.0, end=3.0)
planner.add_time_window(2, start=0.0, end=6.0)

# Set solver options
planner.set_options(return_to_end=True, objective="min_max", time_limit=5)

# Visualize the problem map
planner.show_map(show=False)
plt.close("all")

# Solve
result = planner.solve()
print(result["status"])
for route in result["routes"]:
    print(f"  Agent {route['agent_id']}: path={route['path']}, cost={route['cost']:.3f}")

# Visualize the result
planner.show_result(result, show=False)
plt.close("all")

4. Visualization

show_map — view the problem before solving

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import pyrch

planner = pyrch.Planner()
planner.add_depot(0, x=0.0, y=0.0)
planner.add_target(1, x=1.0, y=2.0)
planner.add_agent(agent_id=0, agent_type="UAV", start_node=0, end_node=0)
planner.set_cost_matrix("UAV", [
    [0.0, 2.24],
    [2.24, 0.0],
])
planner.set_options(return_to_end=True, objective="min_max", time_limit=1.0)

# Via Planner method:
planner.show_map(show=False)
plt.close("all")

# Or via module-level function:
pyrch.show_map(planner, show=False)
plt.close("all")

# Draw on an existing axes (e.g. for subplots):
fig, ax = plt.subplots()
pyrch.show_map(planner, ax=ax, show=False)
plt.savefig("map.png")
plt.close(fig)

Depots are drawn as black stars (★), targets as grey dots, and each agent's start position as a coloured triangle.

show_result — view routes after solving

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import pyrch

planner = pyrch.Planner()
planner.add_depot(0, x=0.0, y=0.0)
planner.add_target(1, x=1.0, y=2.0)
planner.add_agent(agent_id=0, agent_type="UAV", start_node=0, end_node=0)
planner.set_cost_matrix("UAV", [
    [0.0, 2.24],
    [2.24, 0.0],
])
planner.set_options(return_to_end=True, objective="min_max", time_limit=1.0)
result = planner.solve()

# Via Planner method:
planner.show_result(result, show=False)
plt.close("all")

# Or via module-level function:
pyrch.show_result(planner, result, show=False)
plt.close("all")

Each agent's route is drawn with a distinct colour and directional arrows.

return_to_end=False handling: when the solver option return_to_end is False, the solver internally appends the depot as the last node in each route. show_result automatically detects this and removes the trailing depot from the visualization — the route will end at the last target visited, without drawing an edge back to the depot.

5. Low-level programmatic API

from pyrch import Problem, Solver, Options, ObjectiveType, NodeType
from pyrch import Node, Agent, AssignmentConstraint, TimeWindowConstraint

# Build a problem instance in code
problem = Problem()

# Add nodes
for nid, (x, y), ntype in [(0, (0, 0), NodeType.DEPOT),
                             (1, (1, 2), NodeType.TARGET),
                             (2, (3, 1), NodeType.TARGET)]:
    n = Node()
    n.id = nid
    n.position.x = x
    n.position.y = y
    n.position.z = 0.0
    n.type = ntype
    problem.add_node(n)

# Add agents
a = Agent()
a.id = 0
a.type = "UAV"
a.start_node = 0
a.end_node = 0
problem.add_agent(a, 0)

a2 = Agent()
a2.id = 1
a2.type = "UAV"
a2.start_node = 0
a2.end_node = 0
problem.add_agent(a2, 1)

# Set cost matrix (one per agent type)
import math
nodes_xy = [(0,0), (1,2), (3,1)]
n = len(nodes_xy)
cost = [[0.0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        dx = nodes_xy[i][0] - nodes_xy[j][0]
        dy = nodes_xy[i][1] - nodes_xy[j][1]
        cost[i][j] = math.sqrt(dx*dx + dy*dy)
problem.set_cost_matrix("UAV", cost)

# Configure options
problem.options().objective = ObjectiveType.MinMax
problem.options().return_to_end = True
problem.options().time_limit = 5.0

# Solve
opts = problem.options()
solver = Solver(problem, opts)
ret = solver.solve()
result = solver.get_result()

# Note: this low-level API follows the original C++ convention:
# ret == 1 means success, ret == 0 means failure.
print(f"Return code: {ret}")
print(f"Paths: {result.paths}")
print(f"Costs: {result.times}")

JSON Input Format

{
  "nodes": [
    {"id": 0, "x": 0.0, "y": 0.0, "z": 0.0, "type": "depot"},
    {"id": 1, "x": 1.5, "y": 2.3, "z": 0.0, "type": "target"}
  ],
  "agents": [
    {
      "id": 0,
      "type": "TypeA",
      "start_node": 0,
      "end_node": 0,
      "max_length": 100.0,
      "capacity": 10.0
    }
  ],
  "costs": {
    "TypeA": [[0.0, 1.5], [1.5, 0.0]]
  },
  "constraints": [
    {
      "kind": "assignment",
      "items": [
        {"node": 1, "types": ["TypeA"]}
      ]
    },
    {
      "kind": "timewindow",
      "items": [
        {"node": 1, "start": 0.0, "end": 50.0}
      ]
    }
  ],
  "options": {
    "return_to_end": true,
    "objective": "min_max",
    "time_limit": 60
  }
}

Fields:

Result Format

{
    "status": "success",       # "success" or "failed"
    "timeout": False,          # True if solver hit time limit
    "routes": [
        {
            "agent_id": 0,
            "path": [0, 2, 0],    # ordered node IDs
            "cost": 6.32          # route cost
        },
        ...
    ],
    "statistics": {
        "solve_time": 0.123,      # wall-clock time (s)
        "max_cost": 6.32,         # maximum route cost
        "sum_cost": 10.56,        # total cost of all routes
        "n_generated": 1500,      # labels generated
        "n_expanded": 800,        # labels expanded
        "last_update_time": 0.08  # time of last solution improvement
    },
    "anytime": [
        {"time": 0.01, "max_cost": 9.5, "sum_cost": 15.2},
        {"time": 0.05, "max_cost": 7.1, "sum_cost": 12.0},
        ...
    ]
}

API Reference

pyrch.solve(source, *, time_limit=-1) → dict

Solve an MTSP instance.

• source — file path (str / Path), raw JSON string, or Python dict.
• time_limit — override the time limit in seconds (default: use the value in JSON).
• If source looks like a file path but the file does not exist, solve() raises FileNotFoundError.

pyrch.Planner (recommended)

High-level builder API. All mutating methods return self for chaining.

• add_depot(node_id, *, x, y, z=0) — add a depot node.
• add_target(node_id, *, x, y, z=0, demand=0) — add a target node.
• add_agent(*, agent_id, agent_type, start_node, end_node, order=None, capacity_limit=-1, time_limit=-1) — add an agent. time_limit is the max travel distance/time (≤0 means no limit).
• set_cost_matrix(agent_type, matrix) — set cost matrix for an agent type.
• add_assignment(node_id, types) — assign a node to a list of allowed agent types.
• add_time_window(node_id, start, end) — add a time window constraint for a node.
• set_options(*, return_to_end=None, objective=None, time_limit=None) — set solver options. objective accepts "min_max" or "min_sum".
• solve() → dict — run the solver and return a result dict.
• show_map(**kwargs) → Axes — visualize the problem map (depots, targets, agent starts).
• show_result(result, **kwargs) → Axes — visualize solved routes on the map.

pyrch.show_map(planner, *, ax=None, figsize=(8,6), show=True) → Axes

Plot the problem map: depots (★), targets (●), and agent start positions (▲).

pyrch.show_result(planner, result, *, ax=None, figsize=(8,6), show=True) → Axes

Plot solved routes on the map. Each agent's path is drawn with a distinct colour and directional arrows. When return_to_end=False, the trailing depot is automatically stripped from the visualization.

pyrch.Problem

Low-level programmatic problem builder. Methods:

• add_node(node: Node) — add a node.
• add_agent(agent: Agent, id: int) — add an agent.
• set_cost_matrix(agent_type: str, matrix: List[List[float]]) — set cost matrix.
• set_assignment_constraint(c: AssignmentConstraint) — set assignment constraint.
• set_timewindow_constraint(c: TimeWindowConstraint) — set time window constraint.
• options() → Options — access/modify solver options.

pyrch.Solver

Low-level solver. Construct with Solver(problem, options).

• solve() → int — run the solver (1 = success, 0 = failure).
• get_result() → Result — get the final result.
• get_result_process() → List[Tuple[float, Result]] — get full anytime history.

pyrch.ObjectiveType

Enum: ObjectiveType.MinMax, ObjectiveType.MinSum.

pyrch.NodeType

Enum: NodeType.DEPOT, NodeType.TARGET.

License

MIT