Is the Traveling Salesman Problem with Precedence Constraints NP-hard? I am searching for a proof of NP-hardness or dynamic programming solution to the Traveling Salesman Problem with Precedence Constraints (TSP-PC). So far I could not even find any proof that proves the Dial-a-ride Problem (DARP) (also known as the Pick-up and Delivery Problem (PDP)) to lie in NP. 
The PDP is a problem of optimizing the pick-up and delivery of N customers - implying a set of 2N nodes (N pick-up and N delivery nodes). What makes the problem complicated is that on the one hand it consists of a classical routing problem (as the classic TSP) but on the other hand includes precedence constraints which make certain optimal routes infeasible (As there is no need to visit the delivery node -i of customer i before picking him/her up at node +i). Optimization can be considered as minimizing the total traveled distance (assuming euclidean distances), the total completion time or some customer dissatisfaction formulas based on their waiting and riding times.
Psaraftis (1980) and Ruland and Rodin (1997) provide some good attempts of the above described problems but still lack in giving any proofs whether the problem is P or NP.
Psaraftis: http://www.jstor.org/stable/25767975?seq=1#page_scan_tab_contents
Ruland & Rodin: http://www.sciencedirect.com/science/article/pii/S0898122197000904
 A: The TSP with precedence constraints (TSP-PC) as well as the Pickup and Delivery Problem, are both NP-hard problems. The TSP with precedence constraints is a generalization of the TSP problem, which is a known NP-hard problem (Note that NP-hard refers to the optimization problems, not the decision problems which are NP-complete).
A proof of NP-hardness is always by reduction to a problem that is known to be NP-hard: if I had an algorithm to solve TSP-PC, could I then also solve some other problem class which is known to be NP-Hard? In this case, the answer is affirmative: an algorithm for TSP-PC would also be able to solve the TSP problem simply by setting the set of precedence constraints equal to the empty set. Alternatively, in case of a complete, weighted graph $G$, you could pick two arbitrary vertices, say $u$ and $v$, and have the precedence constraint $u\prec v$ ($u$ must precede $v$). Claim: the optimal solution to the TSP problem in $G$ is equivalent to the optimal solution of the TSP-PC problem in $G$ where the set of precedence constraints equals $\{(u\prec v)\}$. Since the optimal solution to a TSP is a cycle which visits all the vertices exactly once, the precedence relation always holds due to the cyclic nature of any feasible TSP solution.
It might be tempting to (falsely) reason that TSP-PC is somehow easier to solve than TSP because some TSP-PC problem instances are easier to solve than the TSP problem instances without the precedence constraints. This is often caused by a very large number of precedence constraints which restrict the solution space so much that only a few feasible solutions exist. This however does not hold in general.
