Multiple-Origin-Multiple-Destination Path Finding with Minimal Arc Usage: Complexity and Models

Abstrakt

The multiple-origin-multiple-destination (MOMD) problem is a simplified version of the logistics planning problem in which packages are required to be transported from their origins to their destinations by multiple trucks with a minimum total cost. This paper proves the NP-hardness of the problem, and gives two SAT-based models for solving the problem optimally.

It also gives experimental results that compare these two SAT models and ASP and CP models

Klíčová slova

• Multiple-Origin-Multiple-Destination Path Finding
• Minimal Arc Usage