Feasibility of the Pickup and Delivery Problem with Fixed Partial Routes: A Complexity Analysis

In the pickup and delivery problem (PDP) a fleet of vehicles must serve customers' requests, which consist of transporting objects from their origins to their destinations. We introduce the PDP with fixed partial routes (PDP‐FPR), in which some partial routes are given, and the problem consists in obtaining a solution (a set of routes) that includes those partial routes. We have analyzed the complexity of determining whether or not a feasible solution exists for this problem as well as for some relaxations of it. Checking the feasibility of the PDP‐FPR and some of its relaxations is shown to be NP‐complete, whereas for other relaxations, the problem was proved to be polynomial‐time solvable.