A Complexity-theoretic Analysis of Green Pickup-and-Delivery Problems

Xing Tan, Jimmy Xiangji HuangAAAI 2021 · DOI

Introduction

As the global logistics industry transitions toward electric and alternative-fuel vehicles, planners face a new set of constraints. The Green Pickup-and-Delivery Problem (GPD) extends traditional routing challenges by incorporating limited vehicle ranges and sparse refueling infrastructure. While the classic Pickup-and-Delivery Problem (PDP) is already known to be NP-hard, researchers have often viewed fuel constraints as merely an additional layer of practical complexity.

This research provides a fundamental complexity-theoretic analysis to answer a critical question: Are these "green" constraints themselves a primary source of computational intractability? By stripping away common variables like vehicle capacity and time windows, the authors isolate the impact of fuel limitations on problem-solving efficiency.

Methodology: Mapping Hardness

The authors employ polynomial-time reductions to test the limits of GPD tractability. They define several highly restricted variants of the problem to see if they remain difficult even under ideal conditions:

  • $GPD_{stn}$: A single vehicle and a single depot, where the depot serves as the sole refueling station.
  • $GPD_{dgr}$: A variant that limits the "degree" of the network, ensuring no more than two tasks enter or leave any city.
  • $GPD^{ring}_{stn\_dgr}$: A specific "ring" topology where tasks form a continuous loop between distinct cities.

To prove these variants are hard, the authors map classic NP-hard problems—such as the Directed Hamiltonian Circuit (DHC) and the PARTITION problem—onto these GPD structures.

A reduction gadget used to prove the NP-completeness of restricted GPD variants.

As shown in the reduction gadgets (e.g., Figure 6), complex logical dependencies are translated into specific task sequences. If a GPD solver could efficiently find a valid route through these gadgets while respecting fuel limits, it would imply that these classic hard problems could also be solved in polynomial time—a feat widely considered impossible in computer science.

Key Insights: The "Green" Villain

The most striking finding is that the simple requirement to refuel before a tank hits empty makes the problem strongly NP-complete, even when the underlying routing is simplified to a point where it would otherwise be solvable in polynomial time (e.g., reducible to an Euler Tour).

A sample task graph and its corresponding solution partitioned into fuel-constrained trails.

Figure 3 illustrates this challenge. In a task graph where cities ($C_a$ to $C_d$) are connected by tasks ($t_1$ to $t_8$), a solution must partition the tasks into "trails." Each trail must start and end at the fuel station ($C_a$) and the total fuel consumption of the tasks in that trail cannot exceed the vehicle's capacity (in this case, 8). This partitioning requirement is the core driver of the problem's complexity.

Finding the Boundary of Tractability

The research identifies a crucial "boundary" for tractability. While most GPD variants are strongly NP-complete (meaning they remain hard even if the numerical values for fuel and distance are small), the ring topology variant is only weakly NP-complete.

This distinction is vital for algorithm design. Weakly NP-complete problems can often be solved using Dynamic Programming. The authors propose a pseudo-polynomial time algorithm for the ring topology that runs in $O(n \times f_{vhl})$ time, where $n$ is the number of tasks and $f_{vhl}$ is the fuel capacity. For most practical applications where fuel capacity is not an astronomically large number, this approach is highly efficient.

Conclusion and Future Work

This analysis proves that fuel constraints are not just "messy" additions to logistics problems; they are fundamental sources of hardness. While real-world delivery networks are rarely perfect rings, these insights allow developers to create better heuristics by approximating complex task graphs as tractable structures.

Future research will focus on identifying other graph structures that allow for efficient solutions and investigating "phase transitions"—the exact points where tightening a fuel constraint shifts a problem from being easily solvable to computationally impossible.

Summary updated

BibTeX
@inproceedings{tan2021complexity,
  author = {Xing Tan and Jimmy Xiangji Huang},
  title = {{A Complexity-theoretic Analysis of Green Pickup-and-Delivery Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17424},
}
Figure