On Computational Complexity of Pickup-and-Delivery Problems with Precedence Constraints or Time Windows

On Computational Complexity of Pickup-and-Delivery Problems with Precedence Constraints or Time Windows

Xing Tan, Jimmy Xiangji Huang

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 5635-5643. https://doi.org/10.24963/ijcai.2019/782

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). 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 NP-completeness. Many problems from a multitude of applications and industry domains are general versions of PDPC. Thus this new result of NP-hardness, 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.
Keywords:
Planning and Scheduling: Planning and Scheduling
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Planning and Scheduling: Scheduling
Agent-based and Multi-agent Systems: Resource Allocation
Robotics: Motion and Path Planning