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 constraint models for solving the problem optimally.

These models are then solved by SAT and MIP solvers (after some translation) and the results are experimentally compared with ASP and CP problem encodings.

Klíčová slova

• Multiple-Origin-Multiple-Destination Path
• Minimal Arc Usage
• Complexity Models