Route feasibility testing and forward time slack for the Synchronized Pickup and Delivery Problem

The Synchronized Pickup and Delivery Problem (SPDP) consists of finding a set of minimum-cost routes servicing user-specified transportation requests from pickup to delivery locations subject to pairing and precedence, capacity, time-window, and minimum and maximum time-lag constraints. The temporal constraints of the SPDP impose a complex scheduling problem for the service times at the customer locations which makes the efficient feasibility checking of routes intricate. We present different route feasibility tests for the SPDP and compare their practical runtime on a huge number of randomly generated routes. Furthermore, we generalize to the SPDP the concept of forward time slack, which has proven a versatile tool for feasibility testing of customer or request insertions into a given (feasible) route for many VRP variants.