This project implements a Python Composable API for Vehicle Routing Problems (VRP), serving as a bridge between the C++ Routing Library concepts and the XCSP3 Constraint Programming ecosystem.
The core idea is to provide a high-level, attribute-based modeling interface (similar to the upcoming C++ bindings detailed in ROADMAP.md) that transparently generates native PyCSP3 constraints. This allows users to define complex routing problems by simply "composing" attributes like Capacities, Time Windows, or Resources, without writing low-level CP variable/constraint logic manually.
- Composable Modeling: Define problems by adding attributes (
Capacity,TimeWindow) to entities (Client,Vehicle). - Native PyCSP3 Generation: Automatically translates high-level attributes into efficient PyCSP3 constraints (
Cumulative,Circuit,NoOverlap, etc.). - Solver Agnostic: Generated models (in XCSP3 format) can be solved by any compliant solver, such as ACE (Abstract Constraint Engine) or CoSoCo.
The library uses a plugin/generator architecture to handle specific problem aspects:
| Generator | Description | PyCSP3 Constraints |
|---|---|---|
| Flow | Handles basic routing logic (sequences, visits). | Circuit |
| Capacity | Manages demand and vehicle capacity. | Cumulative (or resource flow logic) |
| TimeWindow | Handles scheduling and time bounds. | NoOverlap, valid interval propagation |
- Python 3.10+
- PyCSP3 (
pip install pycsp3) - ACE Solver (Java-based) or compliant XCSP3 solver.
from routing import Problem, Solver
from routing.attributes import Capacity, TimeWindow
# 1. Define a VRP Problem
problem = Problem("cvrp_example")
problem.add_attribute("capacity")
problem.add_attribute("time_window")
# 2. Add Entities
depot = problem.add_depot(id=0, x=0, y=0)
client = problem.add_client(id=1, x=10, y=10)
vehicle = problem.add_vehicle(id=1)
# 3. Configure Attributes
depot.add_attribute("vehicle_capacity", Capacity(100))
client.add_attribute("demand", Capacity(10))
client.add_attribute("time_window", TimeWindow(0, 50, service_time=5))
# 4. Solve using ACE (via PyCSP3)
solver = Solver()
status = solver.solve(problem)- XCSP3: An XML-based format for representing Constraint Satisfaction and Optimization Problems.
- PyCSP3: A Python library for modeling combinatorial constrained problems.
- PyCSP3-Scheduling: Scheduling extension for pycsp3 with interval variables, sequence variables, and scheduling constraints.
- ACE (Abstract Constraint Engine): A generic Constraint Programming solver focused on XCSP3.
- CoSoCo: A C++ CP solver for XCSP3.