PyPDTSP

Python wrapper for the Pickup-and-Delivery Traveling Salesman Problem (PDTSP) solvers from vidalt/PDTSP — the hybrid genetic search (pdphgs) and ruin-and-recreate (pdprr) implementations accompanying Pacheco, Martinelli, Subramanian, Toffolo & Vidal, "Exponential-size neighborhoods for the pickup-and-delivery traveling salesman problem" (Transportation Science, 2022).

Status: alpha. The Python surface may change between minor releases.

Install

Prebuilt wheels for Linux (x86_64) and macOS (x86_64 + arm64):

pip install pdtsp

Windows is not yet supported by prebuilt wheels — Windows users (and anyone on a platform without a wheel) install from source. That needs CMake, a C++17 compiler, and Boost (program_options, filesystem, system, regex):

# Debian/Ubuntu
sudo apt install cmake g++ libboost-program-options-dev libboost-filesystem-dev libboost-system-dev libboost-regex-dev
# macOS
brew install cmake boost
# Windows (MSVC + vcpkg)
vcpkg install boost-program-options boost-filesystem boost-system boost-regex --triplet x64-windows-static-md
# then in a Developer PowerShell:
$env:CMAKE_TOOLCHAIN_FILE = "C:/vcpkg/scripts/buildsystems/vcpkg.cmake"

pip install pdtsp             # downloads sdist and builds from source

Quick start

from pdtsp import HGSSolver, HGSParameters

# Index 0 is the depot. Customers 1..4 form two pickup-delivery pairs:
#   pickup 1 -> delivery 3
#   pickup 2 -> delivery 4
data = {
    "x_coordinates": [0.0, 1.0, 2.0, 1.0, 2.0],
    "y_coordinates": [0.0, 1.0, 0.0, 0.0, 1.0],
    "pickup_delivery_pairs": [(1, 3), (2, 4)],
}

result = HGSSolver(HGSParameters(time_limit=10, seed=42)).solve(data)
print(result.cost)    # 4.65...
print(result.route)   # [0, 1, 3, 2, 4, 0]

The Ruin & Recreate variant is a drop-in replacement:

from pdtsp import RRSolver, RRParameters
result = RRSolver(RRParameters(time_limit=10, fast=True)).solve(data)

Explicit distance matrix (Grubhub format)

When you have arbitrary integer distances (not Euclidean coordinates), use the matrix mode. Pickup/delivery pairs are implicit: odd indices are pickups, the following even index is the paired delivery.

data = {
    "name": "demo",
    "distance_matrix": [
        [0, 10, 12, 15, 18],
        [10, 0,  5,  7, 11],
        [12, 5,  0,  6,  8],
        [15, 7,  6,  0,  4],
        [18, 11, 8,  4,  0],
    ],
}
result = HGSSolver(HGSParameters(time_limit=5)).solve(data)

Input shape reference

Coordinate mode

Matrix mode (Grubhub)

Parameter reference

HGSParameters mirrors pdphgs --help (defaults from upstream commit 451bc8a5):

RRParameters mirrors pdprr --help:

Result shape

solver.solve(data) returns a RoutingSolution:

How it works

HGSSolver and RRSolver bundle the upstream native binaries (pdphgs and pdprr) inside the package. Each solve() call:

1. Validates the input dict.
2. Writes a temporary .PDT file (coordinate mode) or matrix file (Grubhub mode).
3. Spawns the bundled binary via subprocess.run.
4. Parses the JSON document the binary prints to stdout.

Subprocess isolation sidesteps upstream's module-level globals — multiple solve() calls in the same Python process are safe.

Citing

@article{pacheco2022pdtsp,
  title   = {Exponential-Size Neighborhoods for the Pickup-and-Delivery
             Traveling Salesman Problem},
  author  = {Pacheco, Toni and Martinelli, Rafael and Subramanian, Anand
             and Toffolo, T{\'u}lio A. M. and Vidal, Thibaut},
  journal = {Transportation Science},
  year    = {2022},
  doi     = {10.1287/trsc.2022.1170}
}

License

PyPDTSP is released under the MIT License. The bundled binaries are compiled from the MIT-licensed vidalt/PDTSP codebase (Copyright © 2022 Toni Pacheco) — see LICENSE for the upstream attribution.