A Temporal-Network Constraint Programming Model for the Pickup and Delivery Problem with Time Windows

Dynamic STN Interpretation and Conditional Difference Constraints

Abstract

We study the single-vehicle pickup and delivery problem with time windows (PDPTW), where each pickup must occur before its corresponding dropoff and service must begin within prescribed time windows. Classical mixed-integer linear programming (MILP) formulations typically link routing and timing through bigM constraints. We instead propose a constraint programming  (CP) formulation based on successor variables, a global Circuit constraint, position variables for route order, and conditional difference constraints that enforce travel-time separations only on selected arcs. Because the route is a closed tour, we introduce a separate return-time variable instead of propagating time back into the depot.

We also interpret the active timing constraints as an evolving temporal network during search, derive necessary infeasibility conditions including subsetbased time-window bounds, and present a baseline MILP formulation for comparison. Finally, we study a three-job instance built from publicly available locations, enumerate all precedence-respecting sequences, and report travel-time statistics, failure indices, and a sensitivity analysis under widened time windows.