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.

Multiple-origin-multiple-destination path finding with minimal arc usage: Complexity and models

DOVIER, Agostino
2016

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
paper4.pdf

accesso aperto

Descrizione: PDF on line da CEUR
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 215.64 kB
Formato Adobe PDF
215.64 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/1099034
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact