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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.