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

Xing Tan, Jimmy Xiangji HuangIJCAI 2019 · DOI

TL;DR

This paper tackles the computational complexity of Pickup-and-Delivery (PD) problems, specifically those with added precedence constraints (PDPC) or time windows (PDTW). The authors prove that these restricted PD variants are NP-complete, establishing a theoretical boundary for their solvability and justifying the use of heuristics. They also conduct an empirical study to pinpoint the sources of this intractability.

What Problem Does This Paper Address?

The Pickup-and-Delivery (PD) problem, a variant of the Vehicle Routing Problem (VRP), involves routing vehicles to pick up and deliver goods or passengers. While VRPs have been extensively studied, PD problems are gaining increasing relevance in AI, particularly with the rise of ride-sharing and intelligent transportation systems. However, a crucial aspect often overlooked is understanding the computational complexity of these problems, especially when they are constrained by real-world factors like precedence (task A must be completed before task B) or time windows (task C must be done within a specific time frame). Without knowing if a problem is fundamentally hard (NP-complete), it's difficult to justify the development and use of approximation algorithms or heuristics over exact, but potentially intractable, methods. This paper aims to fill this gap by formally analyzing the complexity of PD problems with these common constraints.

Methods

The core of this paper's contribution lies in its theoretical proofs and empirical analysis.

Theoretical Contributions: * NP-Completeness Proofs: The authors formally define PDPC (Pickup-and-Delivery with Precedence Constraints) and PDTW (Pickup-and-Delivery with Time Windows) and prove that both are NP-complete. They achieve this by reducing known NP-complete problems, specifically the Directed Hamiltonian Circuit Problem (DHC), to PDPC. They also extend this to variants like PDPC-ST (single-trip) and PDPC-M-ST (multi-vehicle), and their PDTW counterparts, showing they too are NP-complete. * Tractability Boundary: The paper highlights that relaxing either the graph structure (G) or the constraints (P or W) can lead to tractable problems. For instance, PDPC without precedence constraints reduces to finding an Euler Tour (polynomial time), and PDTW without time windows but with precedence constraints can be solved via topological sorting.

Empirical Analysis: * Local Search Algorithm: To investigate the sources of intractability, the authors propose a local search algorithm for solving PDPC. This algorithm iteratively improves a random task permutation by moving tasks to positions that reduce a cost function, which penalizes unmet neighborhood requirements and violated precedence constraints. * Source of Intractability Study: Using the local search solver, they conduct experiments to analyze how factors like the number of cities, the number of tasks, and the density of precedence constraints affect problem solvability.

Datasets

Not discussed in the paper. The authors generate their own problem instances for empirical evaluation.

Key Insights and Ideas

  • PDPC and PDTW are Fundamentally Hard: The NP-completeness proofs are a significant theoretical contribution, establishing that even restricted versions of PD problems are computationally challenging. This provides a strong theoretical basis for using heuristics.
  • The "Sweet Spot" of Intractability: The empirical results suggest that PDPC problems are not necessarily hardest when they have the fewest or the most precedence constraints. Instead, the most difficult instances (where solvability transitions from high to low) often occur in intermediate regions, particularly around 10% of the maximum possible precedence constraints.
  • City Count Matters: For a given number of tasks, problems with more cities tend to be harder to solve. This indicates that the topology of the underlying graph (G) plays a crucial role in computational difficulty.
  • Local Search as a Practical Tool: The proposed local search algorithm, despite its simplicity, proves effective in finding solutions for PDPC instances, demonstrating the practical utility of heuristic approaches.

Key Results

  • NP-Completeness: PDPC and PDTW, along with their single-trip and multi-vehicle variants, are proven to be NP-complete.
  • Empirical Findings:
    • The local search algorithm generally solves problem instances within 300 rounds, with many solvable in under 100 rounds.
  • Problems with no precedence constraints are easily solvable (related to Euler Tours).
  • Problems with a high density of precedence constraints (e.g., 80%) are also relatively easy to solve, as the constraints largely dictate the solution.
  • The most challenging instances are found in intermediate ranges of precedence constraints (e.g., 10-40%), where the problem is neither too constrained nor too unconstrained.
  • The number of cities significantly impacts hardness; more cities lead to harder problems for the same number of tasks and constraints.

Limitations and Future Work

  • Local Minima: The current local search algorithm does not explicitly employ strategies for escaping local minima, which could be a limitation for very complex instances.
  • Generalization of PDTW: While PDPC is shown to be NP-complete, the paper notes that PDTW with time windows alone (without graph structure constraints) is already NP-hard, referencing the complexity of Allen's Interval Algebra. Further research could explore tractable subalgebras of Allen's IA for PDTW.
  • Future Directions:
    • Investigating more advanced local search techniques, including methods for escaping local minima (e.g., Discrete Lagrangian Method).
  • Encoding PDPC problems as propositional satisfiability (CSP) problems.
  • Testing the proposed methods and insights on real-world benchmarks (e.g., from ride-sharing or robotics).
  • Exploring further restrictions on graph structures or precedence constraints that might lead to polynomial-time solvable PDPC variants.

Summary updated

BibTeX
@inproceedings{tan2019computational,
  author = {Xing Tan and Jimmy Xiangji Huang},
  title = {{On Computational Complexity of Pickup-and-Delivery Problems with Precedence Constraints or Time Windows}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/782},
}
Figure