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 SAT-based models for solving the problem optimally. It also gives experimental results that compare these two SAT models and ASP and CP models.