Large-scale local search heuristics for the capacitated vertex \(p\)-center problem.

*(English)*Zbl 1053.90085Summary: This article investigates the application of very large neighborhood search techniques for solving the capacitated vertex \(p\)-center problem. We characterize a local search neighborhood in terms of path and cyclic exchanges of customers among facilities, and exploit principles borrowed from network optimization theory to efficiently detect cost-decreasing solutions in such a neighborhood. We complement the multiexchange methodology with a relocation mechanism specifically designed to perform facility location adjustments. The validity of the proposed approach is supported by empirical investigation and performance comparisons with the commercial code CPLEX.

##### MSC:

90B80 | Discrete location and assignment |

90C06 | Large-scale problems in mathematical programming |

90C59 | Approximation methods and heuristics in mathematical programming |

PDF
BibTeX
XML
Cite

\textit{M. P. Scaparra} et al., Networks 43, No. 4, 241--255 (2004; Zbl 1053.90085)

Full Text:
DOI

##### References:

[1] | Ahuja, Network flows: Theory, algorithms and applications (1993) · Zbl 1201.90001 |

[2] | Ahuja, A multiexchange heuristic for the single source capacitated facility location problem, Manage Sci (2002) |

[3] | Ahuja, New neighborhood search structures for the capacitated minimum spanning tree problem, Math Program 91 pp 71– (2001) · Zbl 1051.90019 |

[4] | Bar-Ilan, How to allocate network centers, J Algorithms 15 pp 385– (1993) · Zbl 0784.68012 |

[5] | Beasley, OR-Library: Distributing test problems by electronic mail, J Operat Res Soc 41 pp 1069– (1990) |

[6] | Frangioni, A multi-exchange neighborhood for minimum makespan machine scheduling problems, J Combinat Optimizat (2000) |

[7] | Galvão, A Lagrangean heuristic for the maximum covering location problem, Eur J Operat Res 88 pp 114– (1996) · Zbl 0913.90200 |

[8] | Hochbaum, A unified approach to approximation algorithms for bottleneck problems, J ACM 33 pp 533– (1986) |

[9] | Jaeger, A polynomial algorithm for the equal capacity p-center problem on trees, Transport Sci 28 pp 167– (1994) · Zbl 0807.90076 |

[10] | Kariv, An algorithmic approach to network location problems. Part 1: The p-centers, SIAM J Appl Math 37 pp 513– (1979) · Zbl 0432.90074 |

[11] | Khuller, The capacitated k-center problem, SIAM J Discrete Math 13 pp 403– (2000) · Zbl 0947.05073 |

[12] | Lorena, A column generation approach to capacitated p-median problems, Comput Operat Res 31 pp 863– (2004) · Zbl 1048.90132 |

[13] | Romeijn, A class of greedy algorithms for the generalized assignment problem, Discrete Appl Math 103 pp 209– (2000) · Zbl 1064.90019 |

[14] | Thompson, Cyclic transfer algorithms for multi-vehicle routing and scheduling problems, Operat Res 41 pp 935– (1993) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.