Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers

The Pickup and Delivery Problem with Transfers (PDPT) consists of defining a set of minimum cost routes in order to satisfy a set of transportation requests, allowing them to change vehicles at specific locations. In this problem, routes are strongly interdependent due to request transfers. Then it is critical to efficiently check if inserting a request into a partial solution is feasible or not. In this article, we present a method to perform this check in constant time.