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

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.