Title

Efficient Heuristics For Facility Location Problem With Foresight

Translated Titles

Efficient Heuristics For Facility Location Problem With Foresight

DOI

10.6841/NTUT.2014.00357

Authors

倪琨珉

Key Words

market capture ; von Stackelberg ; p-center ; competitive location problem ; tabu search ; cplex ; market capture ; von Stackelberg ; p-center ; competitive location problem ; tabu search ; cplex

PublicationName

臺北科技大學管理國際學生碩士專班 (IMBA)學位論文

Volume or Term/Year and Month of Publication

2014年

Academic Degree Category

碩士

Advisor

吳建文

Content Language

英文

Chinese Abstract

Researchers have been solving location problems with the assumption that the competition in the market does not subject the new facilities that is located in the market. Meanwhile, competitive facility location model is the awareness that a firm’s location may affect its market share. The facilities capture as many customers as possible in order to maximize the market share. On the other hand, no existing facilities exist in the area where p-center problems apply. The objective in p-center is to minimize the cost for customer. The consideration in this research is customers patronize the nearest facility, whereas distance is the attractiveness. Therefore, we could propose an idea to implement the p-center into competitive location problem model in order to satisfy the assumption. Tabu search is one algorithm that has been applied to location problems successfully. In addition to the contributions mentioned earlier, we could also utilize efficient heuristics for facility location with foresight.

English Abstract

Researchers have been solving location problems with the assumption that the competition in the market does not subject the new facilities that is located in the market. Meanwhile, competitive facility location model is the awareness that a firm’s location may affect its market share. The facilities capture as many customers as possible in order to maximize the market share. On the other hand, no existing facilities exist in the area where p-center problems apply. The objective in p-center is to minimize the cost for customer. The consideration in this research is customers patronize the nearest facility, whereas distance is the attractiveness. Therefore, we could propose an idea to implement the p-center into competitive location problem model in order to satisfy the assumption. Tabu search is one algorithm that has been applied to location problems successfully. In addition to the contributions mentioned earlier, we could also utilize efficient heuristics for facility location with foresight.

Topic Category 管理學院 > 管理國際學生碩士專班 (IMBA)
社會科學 > 管理學
Reference
  1. Al-Sultan, K. S., & Al-Fawzan, M. A. (1999). A tabu search approach to the uncapacitated facility location problem. Annuals of Operations Research, 86, 91-103.
    連結:
  2. Berman, O., & Huang, R. (2008). The minimum weighted covering location problem with distance constraints. Computer & Operations Research, 35, 356-372.
    連結:
  3. Berman, O., & Simchi-Levi, D. (1990). Conditional location problems on networks. Transportation Science, 24, 77-78.
    連結:
  4. Bilgin, S., & Azizoğlu, M. (2009). Operation assignment and capacity allocation problem in automated manufacturing systems. Computers & Industrial Engineering, 56, 662-676.
    連結:
  5. Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3), 268-308.
    連結:
  6. Chen, R. (1988). Conditional minimum and minimax location-allocation problems in Euclidean space. Transportation Science, 22, 157-160.
    連結:
  7. Chen, R., & Handler , G. Y. (1993). The conditional p-center problem in the plane. Naval Research Logistics, 40, 117-127.
    連結:
  8. Chen, R., & Handler, G. Y. (1987). A relaxation method for the solution of the minimax location-allocation problem in Euclidean space. Naval Research Logistics Quarterly, 34, pp. 775-788.
    連結:
  9. Church, R., & ReVelle, C. (1974). The maximal covering location problem. Papers of the Regional Science Association, 32, 101-118.
    連結:
  10. Coxeter, H. S., Few, L., & Rogers, C. A. (1959). Covering space with equal spheres. Mathematica, 6, 247.
    連結:
  11. deWerra, D., & Hertz, A. (1989). Tabu search techniques: A tutorial and an application to neural networks. OR Spectrum, 11, 131-141.
    連結:
  12. Dobson, G., & Karmarkar, U. S. (1987). Competitive location on network. Operations Research, 35, 565-574.
    連結:
  13. Drezner, T. (1994). Optimal continuous location of a retail facility, facility attractiveness, and market share: An interactive model. Journal of Retailing, 70, 49-64.
    連結:
  14. Drezner, T. (1998). Location of multiple retail facilities with a limited budget. Journal of Retailing and Consumer Services, 5, 173-184.
    連結:
  15. Drezner, T., Drezner, Z., & Salhi, S. (2002). Solving the multiple competitive facilities location problem. European Journal of Operational Research, 142, 138-151.
    連結:
  16. Drezner, Z. (1984). The p-center problem—heuristic and optimal algorithms. Journal of the Operational Research Society, 35, 741-748.
    連結:
  17. Drezner, Z. (1987). On the rectangular p-center problem. Naval Research Logistics Quarterly, 34, pp. 229-234.
    連結:
  18. Drezner, Z. (1989). Conditional p-center problems. Transportation Science, 23, 51-53.
    連結:
  19. Drezner, Z., & Zemel, E. (1991). Competitive location in the plane. Annals of Operations Research, 40, 173-193.
    連結:
  20. Eiselt, H. A., & Laporte , G. (1989). The maximum capture problem in a weighted network. Working paper CRT-580, Universite de Montreal.
    連結:
  21. Eiselt, H. A., Laporte, G., & Thisse, J. F. (1993). Competitive location models: A framework and bibliography. Transportation Science, 27(1), 44-54.
    連結:
  22. Friden, C., Hertz, A., & deWerra , D. (1989). Stabulus: A technique for finding stable sets in large graphs with tabu search. ORSA Journal of Computing, 42, 35-44.
    連結:
  23. Friez, T., Miller, T., & Tobin, R. (1988). Competitive network facility location models: A survey. Papers of the Regional Science Association, 65, 47-57.
    連結:
  24. Ghosh, A., & Craig, C. S. (1984). A location allocation model for facility planning in a competitive environment. Geographical Analysis, 16, 39-51.
    連結:
  25. Glover, F. (1977). Heuristics for integer programming using surrogate constraints. Decision Sciences, 8, 156-166.
    連結:
  26. Glover, F. (1986). Future paths for integer programming and linkage to artificial intelligence. Computers and Operations Research, 13, 533-549.
    連結:
  27. Glover, F. (1990). Tabu search Part II. ORSA Journal of Computing, 2, 4-32.
    連結:
  28. Hakimi, S. L. (1983). On locating new facilities in a competitive environment. European Journal of Operational Research, 12, 29-35.
    連結:
  29. Hakimi, S. L. (1986). p-Median theorems for competitive locations. Annals of Operations Research, 5, 79-88.
    連結:
  30. Hertz, A., & DeWerra, D. (1987). Using tabu search techniques for graph coloring. ORSA Journal of Computing, 29, 345-351.
    連結:
  31. Hotelling, H. (1929). Stability in competition. Economic Journal, 39, 41-57.
    連結:
  32. Huff, D. L. (1964). Defining and estimating a trade area. Journaal of Marketing, 28, 34-38.
    連結:
  33. Huff, D. L. (1966). A programmed solution for approximating and optimum retail location. Land Economics, 42, 293-303.
    連結:
  34. Karkazis, J. (1989). Facilities location in a competitive environment: A promethee based multiple criteria analysis. European Journal of Operational Research, 42, 294-304.
    連結:
  35. Klincewicz, J. G. (1992). Avoiding local optima in the p-hub location problem using tabu search and grasp. Annals of Operations Research, 40, 121-132.
    連結:
  36. Laguna, M., Barnes, J. W., & Glover, F. (1991). Tabu search for a single machine scheduling problem. Journal of Intelligent Manufacturing, 2, 253-260.
    連結:
  37. Michel, L., & Van Hentenryck, P. A. (2004). A simple tabu search for warehouse location. European Journal of Operational Research, 157, 576-591.
    連結:
  38. Minieka, E. (1980). Conditional centers and medians of a graph. Networks, 10, 265-272.
    連結:
  39. Nakanishi, M., & Cooper, L. G. (1974). Parameter estimate for multiplicative interactive choice model: Least squares approach. Journal of Marketing Research, 11, 303-311.
    連結:
  40. Okabe, A., & Suzuki, A. (1987). Stability in spatial competition for a large number of firms on a bounded two-dimensional space. Environment and Planning A, 19(18), 1067-1082.
    連結:
  41. Papadimitriou, C. H. (1981). Worst case and probabilistic analysis of a geometric location problem. SIAM Journal on Computing, 10, 542.
    連結:
  42. Plastria, F. (2001). Static competitive facility location: An overview of optimisation approaches. European Journal of Operational Research, 129, 461-470.
    連結:
  43. Plastria, F. (2002). Formulating logical implications in combinatorial optimisation. European Journal of Operational Research, 140, 338-353.
    連結:
  44. Plastria, F., & Vanhaverbeke, L. (2008). Discrete models for competitive location with foresight. Computers & Operations Research, 35, 683-700.
    連結:
  45. Prescott, E. C., & Visscher, M. (1977). Sequential location among firms with foresight. Bell Journal of Economics, 8, 378-393.
    連結:
  46. ReVelle, C. (1986). The maximum capture or sphere of influence location problem: Hotelling revisited on a network. Journal of Regional Science, 26, 343-358.
    連結:
  47. ReVelle, C., & Serra, D. (1991). The maximum capture problem including relocation. Information and Operations Research, 29(2), 130-138.
    連結:
  48. Rolland, E., Schilling, D. A., & Current, J. R. (1996). An efficient tabu search procedure for the p-median problem. European Journal of Operational Research, 96, 329-42.
    連結:
  49. Serra, D., & ReVelle, C. (1994). Market capture by two competitors: The pre-emptive location problem. Journal of Regional Science, 34(4), 549-561.
    連結:
  50. Serra, D., Ratick, S., & ReVelle, C. (1996). The maximum capture problem with uncertainty. Environment and Planning B, 23, 49-59.
    連結:
  51. Skorin-Kapov, J. (1990). Tabu search applied to the quadratic assignment problem. ORSA Journal of Computing, 2.
    連結:
  52. Skorin-Kapov, J. (1994). Extensions of a tabu search adaptation to the quadratic assignment problem. Computer and Operations Research, 21(8), 855-865.
    連結:
  53. Stackelberg, H. v. (1943). Grundlagen der theoretischen Volkswirtschaftslehre (translated as The Theory of the Market Economy). London: W. Hodge & Co. Ltd.
    連結:
  54. Suzuki, A., & Drezner, Z. (1996). The p-center location problem in an area. Location Science, 4, 69-82.
    連結:
  55. Taillard, E. (1991). Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing, 17, 443-455.
    連結:
  56. Teitz, M. B. (1968). Locational strategies for competitive systems. Journal of Regional Science, 8, 135-148.
    連結:
  57. Vijay, J. (1985). An algorithm for the p-center problem in the plane. Transportation Science, 19, 235-245.
    連結:
  58. Zemel , E. (1984). Probabilistic analysis of geometric location problems. Annals of Operations Research, 1, 215-238.
    連結:
  59. Battiti, R., & Tecchiolli, G. (1994). The reactive tabu search. ORSA Journal of Computing, 6, 126-140.
  60. Daskin, M. S. (1995). Network and discrete location: Models, Algorithms, and Applications. New York, NY: John Wiley & Sons.
  61. Daskin, M. S. (2013). Network and Discrete Location: Algorithms, and Applications. John Wiley & Sons.
  62. Eiselt, H. A., & Laporte, G. (1996). Sequential location problems. European Journal of Operational Research, 96(2), 217-231.
  63. Farahani, R. Z., & Iekmatfar, M. (2009). Facility Location: Concepts, Models, Algorithms and Case Studies. Springer.
  64. Glover, F., & Laguna, M. (1993). Tabu search. (C. Reeves, Ed.) Blackwell Publishing.
  65. Glover, F., & Laguna, M. (1997). Tabu Search. Norwell, Massachusetts: Kluwer Academic Publishers.
  66. Hakimi, S. L. (1990). Locations with spatial interactions: Competitive locations and games. Discrete Location Theory, 439-478.
  67. Handler, G. Y. (1990). p-Center Problems. (B. M. P, & L. F. R, Eds.) Discrete Location Theory.
  68. Niemi, R. G. (1976). Controversies in American Voting Behavior. (H. F. Weisberg, Ed.) San Francisco, CA: W. H. Freeman & Son.
  69. Rolland, E., Pirkul, H., & Glover, F. (1995). Tabu search for graph partitioning. Annals of Operations Research.
  70. Serra, D., & ReVelle, C. (1994). Competitive Location in Discrete Space. Economics Working paper 96, Universitat Pompeu Fabra, Department of Economics and Business.
  71. Serra, D., Marianov , V., & ReVelle, C. (1992). The hierarchical maximum capture problem. European Journal of Operational Research, 62(3), 58-69.
  72. Stutzle, T. (1999). Local Search Algorithms for Combinatorial Problems — Analysis, Algorithms and New Applications. Sankt Augustin, Germany: DISKI — Dissertationen zur Kunstliken Intelligenz.
  73. Suzuki, A., & Okabe, A. (1995). Using Voronoi diagrams: A survey of Applications and Methods. (D. Z, Ed.) New York, NY: Springer-Verlag.
  74. Tansel, B. C., Francis, R. L., & Lowe, T. J. (1990). Duality: covering and constraining p center problems on trees. (B. M. P, & L. F. R, Eds.) Discrete Location Theory.