본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

Multi-Exchange Neighborhood Search Heuristics for the Multi-Source Capacitated Facility Location Problem

Chyu, Chiuh-Cheng    (Department of Industrial Engineering and Management Yuan-Ze University   ); Chang, Wei-Shung    (Department of Industrial Engineering and Management Yuan-Ze University  );
  • 초록

    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.


  • 주제어

    Capacitated Facility Location Problems .   Transportation Simplex Method .   Sensitivity Analysis .   Simulated Annealing .   Variable Neighborhood Structures.  

  • 참고문헌 (15)

    1. Klose, A. and Drexl, A., (2005), Lower bounds for the capacitated facility location problem based on column generation, Management Science, 51(11), 1689-1705 
    2. Sridharan R. (1995), The capacitated plant location problem, European Journal of Operational Research, 87 (2), 203-213 
    3. Beasley, J. E. (1993), Lagrangian heuristics for location problems, European Journal of Operational Research, 65(3), 383-399 
    4. 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 
    5. 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 
    6. 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 
    7. Barahona, F., Anbil, R. (2000), The volume algorithm: Producing primal solutions with a subgradient method, Mathematical Programming, Series B 87(3), 385-399 
    8. Pirkul, H. (1987), Efficient algorithms for capacitated concentrator location problem, computers and operations Research, 14(3), 197-208 
    9. Barahona, F. and Chudak, F. A. (2005), Near-optimal solutions to large-scale facility location problems, Discrete Optimization, 2(1), 35-50 
    10. 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 
    11. 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 
    12. Sridharan, R. (1993), A Lagrangian heuristic for the capacitatedplant location problem with single source constraints, European Journal of Operational Research, 66(3), 305-312 
    13. 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 
    14. Lenstra, J. K., Rinnooy Kan, A. H. G. (1978), Complexity of scheduling under precedence constraints, Operations Research, 26(1), 22-35 
    15. 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 

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기