ailsii 0.1.0

Python wrapper for the AILS-II metaheuristic (INFORMS JoC 2023) for the Capacitated Vehicle Routing Problem

PyAILSII

A Python wrapper for the AILS-II Capacitated Vehicle Routing Problem solver.

PyAILSII provides a thin Python interface to the AILS-II metaheuristic (Máximo, Cordeau, Nascimento, INFORMS JoC 2023; upstream source at INFORMSJoC/2023.0106).

The public API deliberately mirrors PyHygese (a sibling wrapper around HGS-CVRP), so you can compare or swap solvers by changing only the import.

Install

pip install ailsii

• Build-time requirements: a JDK with javac and jar on PATH. The install step downloads the upstream Java sources, compiles them, and bundles the resulting AILSII.jar into the package. On macOS, brew install openjdk is enough; on Debian/Ubuntu, sudo apt install default-jdk.
• Runtime requirement: a JRE on PATH. Once installed, PyAILSII shells out to java -jar for each solve.

Quick start

import ailsii

data = {
    "x_coordinates": [0.0, 1.0,  1.0, -1.0, -1.0, 0.5, -0.5],
    "y_coordinates": [0.0, 1.0, -1.0,  1.0, -1.0, 0.0,  0.0],
    "demands":       [0,   3,    3,    3,    3,    3,    3],
    "vehicle_capacity": 9,
}

params = ailsii.AlgorithmParameters(timeLimit=2.0, rounded=False)
solver = ailsii.Solver(parameters=params, verbose=True)
result = solver.solve_cvrp(data)

print("cost:", result.cost)
print("routes:", result.routes)  # customer ids in the input dict's index space; depot (0) excluded

Solving a CVRPLIB instance

Standard benchmark instances from CVRPLIB ship in TSPLIB CVRP format (.vrp files). The vrplib package reads them into NumPy-friendly dicts whose layout maps directly onto PyAILSII's input shape.

pip install vrplib

import urllib.request
import vrplib
import ailsii

# Grab a benchmark instance. The AILS-II authors' INFORMSJoC companion repo
# mirrors all CMT and Uchoa X instances at predictable raw URLs; CVRPLIB itself
# is also fine if you already have the file locally.
url = "https://raw.githubusercontent.com/INFORMSJoC/2023.0106/main/data/CMT1.vrp"
urllib.request.urlretrieve(url, "CMT1.vrp")

# vrplib returns coordinates as an (n, 2) ndarray with the depot at index 0,
# which is exactly the layout PyAILSII expects.
instance = vrplib.read_instance("CMT1.vrp")

data = {
    "x_coordinates": instance["node_coord"][:, 0],
    "y_coordinates": instance["node_coord"][:, 1],
    "demands":       instance["demand"],
    "vehicle_capacity": instance["capacity"],
}

params = ailsii.AlgorithmParameters(timeLimit=10.0, rounded=False)
result = ailsii.Solver(parameters=params, verbose=True).solve_cvrp(data)

print(f"cost: {result.cost:.4f}  (CMT1 best-known: 524.61)")
print(f"routes: {result.routes}")
print(f"time: {result.time} sec")

Use rounded=True for the X benchmark suite (Uchoa et al.), which is defined on rounded integer Euclidean distances; use rounded=False for the CMT and classic instances, which use real-valued distances.

Input data shape

PyAILSII v1 supports coordinate input only (TSPLIB EUC_2D). The expected dict keys match PyHygese's:

key	required	meaning
x_coordinates, y_coordinates	yes	length-n sequences; index 0 is the depot
demands	yes	length-n; demands[0] must be 0
vehicle_capacity	yes	homogeneous integer capacity
depot	optional	must be 0 (AILS-II requires the depot at index 0)

Passing distance_matrix raises NotImplementedError — explicit distance-matrix support (TSPLIB EDGE_WEIGHT_TYPE: EXPLICIT) is on the roadmap. For arbitrary cost matrices today, use PyHygese.

Algorithm parameters

ailsii.AlgorithmParameters(
    timeLimit=10.0,           # -limit  (seconds when stoppingCriterion="Time")
    stoppingCriterion="Time", # or "Iteration"
    rounded=True,             # -rounded  (Euclidean distances rounded to int)
    best=None,                # -best     (best-known value; for gap reporting only)
    varphi=40,                # -varphi   (k-NN granular set size)
    gamma=30,                 # -gamma    (iterations between ω adjustments)
    dMax=30,                  # -dMax     (initial reference perturbation degree)
    dMin=15,                  # -dMin     (final reference perturbation degree)
)

Field names track the upstream Java CLI flags so the original paper's parameter discussion applies unchanged. AILS-II's CLI is documented in the upstream README.

Result shape

@dataclass
class RoutingSolution:
    cost: float          # best objective value found
    time: float          # AILS-II's own clock (seconds)
    n_routes: int        # number of vehicle routes
    routes: list[list[int]]  # customer ids per vehicle (input dict index space); depot (0) excluded

This matches PyHygese's RoutingSolution so user code is portable between the two packages.

How it works

PyAILSII wraps a java -jar subprocess. The bundled JAR is built from upstream Java sources at install time with one tiny wrapper class added (AILSIIEntry.AILSIIMain) whose only purpose is to print the final routes between sentinel markers — upstream's own main prints progress metrics but not the resulting routes, so the Python wrapper has nothing to parse without this shim.

The PyPI distribution and Python import name is ailsii (lowercase). Whenever this README refers to "PyAILSII," it means the project / repo; code always uses import ailsii.

Citing

If you use PyAILSII in academic work, please cite the upstream paper:

@article{Maximo2024AILSII,
  author  = {V. R. M{\'a}ximo and J.-F. Cordeau and M. C. V. Nascimento},
  title   = {AILS-II: An Adaptive Iterated Local Search Heuristic for the Large-Scale Capacitated Vehicle Routing Problem},
  journal = {INFORMS Journal on Computing},
  year    = {2024},
  doi     = {10.1287/ijoc.2023.0106}
}

License

MIT, with upstream attribution preserved. See LICENSE.