2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.