On Computational Complexity of Pickup-and-Delivery Problems with Precedence
Constraints or Time Windows
Abstract
Pickup-and-Delivery (PD) problems consider routing vehicles to achieve a set of tasks related to
“Pickup”, and to “Delivery”. Meanwhile these
tasks might subject to Precedence Constraints
(PDPC) or Time Windows (PDTW) constraints.
PD is a variant to Vehicle Routing Problems (VRP),
which have been extensively studied for decades.
In the recent years, PD demonstrates its closer relevance to AI. With an awareness that few work
has been dedicated so far in addressing where
the tractability boundary line can be drawn for
PD problems, we identify in this paper a set of
highly restricted PD problems and prove their NPcompleteness. Many problems from a multitude
of applications and industry domains are general
versions of PDPC. Thus this new result of NPhardness, of PDPC, not only clarifies the computational complexity of these problems, but also
sets up a firm base for the requirement on use of
approximation or heuristics, as opposed to looking for exact but intractable algorithms for solving
them. We move on to perform an empirical study
to locate sources of intractability in PD problems.
That is, we propose a local-search formalism and
algorithm for solving PDPC problems in particular. Experimental results support strongly effectiveness and efficiency of the local-search. Using
the local-search as a solver for randomly generated
PDPC problem instances, we obtained interesting
and potentially useful insights regarding computational hardness of PDPC and PD