The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any p/N ratio.

Two exact algorithms for the capacitated p-median problem / Alberto Ceselli. - In: 4OR. - ISSN 1619-4500. - 1:4(2003), pp. 319-340.

Two exact algorithms for the capacitated p-median problem

Alberto Ceselli
2003

Abstract

The p-median problem has been widely studied in combinatorial optimisation, but its generalisation to the capacitated case has not. We propose a branch and price algorithm, comparing it with a standard MIP solver and a branch and bound algorithm based on Lagrangean relaxation. We present computational experience, using test instances drawn from the literature and new instances with higher ratio between the number of medians p and the number of nodes N. The branch and price algorithm shows very good performances and computational time robustness in solving problems for any p/N ratio.
Branch and bound; Column generation; Lagrangean relaxation; Location theory
2003
4OR
http://www.springerlink.com/content/58b5f7h60tlda6q2/
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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: https://hdl.handle.net/2434/27113
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 24
  • ???jsp.display-item.citation.isi??? 22
social impact