Multi-Exchange Neighborhood Search Heuristics for the Multi-Source Capacitated Facility Location Problem
We present two local-search based metaheuristics for the multi-source capacitated facility location problem. In such a problem, each customer's demand can be supplied by one or more facilities. The problem is NP-hard and the number of locations in the optimal solution is unknown. To keep the search process effective, the proposed methods adopt the following features: (1) a multi-exchange neighborhood structure, (2) a tabu list that keeps track of recently visited solutions, and (3) a multi-start to enhance the diversified search paths. The transportation simplex method is applied in an efficient manner to obtain the optimal solutions to neighbors of the current solution under the algorithm framework. Two in-and-out selection rules are also proposed in the algorithms with the purpose of finding promising solutions in a short computational time. Our computational results for some of the benchmark instances, as well as some instances generated using a method in the literature, have demonstrated the effectiveness of this approach.
- Klose, A. and Drexl, A., (2005), Lower bounds for the capacitated facility location problem based on column generation, Management Science, 51(11), 1689-1705
- Sridharan R. (1995), The capacitated plant location problem, European Journal of Operational Research, 87 (2), 203-213
- Beasley, J. E. (1993), Lagrangian heuristics for location problems, European Journal of Operational Research, 65(3), 383-399
- Arostegui, Jr., M. A., Kadipasaoglu, S. N., and Khumawala, B. M. (2006), An empirical comparison of tabu search, simulated annealing, and genetic algorithms for facilities location problems, International Journal of Production Economics, 103(2), 742-754
- Ahuja, R. K., Liu, J., Orlin, J. B., Goodstein, J., and Mukherjee, A. (2004). A neighborhood search algorithm for the combined through and fleet assignment model with time windows, Networks, 44(2), 160-171
- Cortinhal, M. J., Captivo, M. E. (2003), Upper and lower bounds for the single source capacitated location problem, European Journal of Operational Research, 151(2), 333-351
- Barahona, F., Anbil, R. (2000), The volume algorithm: Producing primal solutions with a subgradient method, Mathematical Programming, Series B 87(3), 385-399
- Pirkul, H. (1987), Efficient algorithms for capacitated concentrator location problem, computers and operations Research, 14(3), 197-208
- Barahona, F. and Chudak, F. A. (2005), Near-optimal solutions to large-scale facility location problems, Discrete Optimization, 2(1), 35-50
- Aart, E. H. L. and Korst, J. H. M. (1991), Simulated annealing Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing. John Wiley, Chichester
- Holmberg, K., Ronnqvist, M., and Yuan, D. (1999), An exact algorithm for the capacitated facility location problems with single sourcing, European Journal of Operational Research, 113(3), 544-559
- Sridharan, R. (1993), A Lagrangian heuristic for the capacitatedplant location problem with single source constraints, European Journal of Operational Research, 66(3), 305-312
- Korupolu, M. R., Plaxton, C. G., Rajaraman, R. (2000), Analysis of a local search heuristic for facility location problems, Journal of Algorithms, 37(1), 146-188
- Lenstra, J. K., Rinnooy Kan, A. H. G. (1978), Complexity of scheduling under precedence constraints, Operations Research, 26(1), 22-35
- Teitz, M. B. and Bart, P. (1968), Heuristic methods for estimating the generalized vertex median of a weighted graph, Operations Research, 16(5), 955-961
유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.
원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.
NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.
- 이 논문과 함께 출판된 논문 + 더보기