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.
|Titolo:||Two exact algorithms for the capacitated p-median problem|
|Parole Chiave:||Branch and bound; Column generation; Lagrangean relaxation; Location theory|
|Data di pubblicazione:||2003|
|Digital Object Identifier (DOI):||10.1007/s10288-003-0023-5|
|Appare nelle tipologie:||01 - Articolo su periodico|