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 precede its corresponding dropoff and service must begin within prescribed time windows. We present a constraint programming (CP) formulation based on successor variables, a global Circuit constraint, position variables for route order, and conditional difference constraints that activate travel-time separations only on selected arcs. Because the route is closed, we introduce a separate return-time variable instead of propagating timing constraints back into the depot.

The central perspective of the paper is that routing decisions induce a temporal constraint graph. As successor variables are fixed, the active timing constraints form an evolving simple temporal network whose edges correspond to selected travel and service separations. This view clarifies how propagation tightens service-time bounds and why some partial assignments become infeasible before a complete tour is specified. Within this framework, we derive necessary infeasibility conditions, including subset-based time-window bounds, and present a baseline mixed-integer linear programming formulation for comparison.

We complement the formulation with a controlled empirical study over synthetic PDPTW instances. For instances with three to five pickup--dropoff pairs, we enumerate all precedence-respecting routes and analyze feasible-route percentages, normalized failure depths, prefix-failure profiles, slack sensitivity, and travel-time structure. The results illustrate how active timing constraints expose temporal structure during search and how feasibility depends on route size, travel-time structure, and time-window slack.