Shobeiri, Ali (2015) GRASP Metaheuristic for Multiple Allocation p-Hub Location Problem. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
1MBShobeiri_MASc_W2016.pdf - Accepted Version |
Abstract
Hub Location Problems (HLPs), belonging to the field of location theory, have been area of much research over the past two decades. This is due, in large measure, to the applications of hub and spoke networks in practice. Among the most classical versions of HLPs are p-hub location problems (p-HLPs), p-hub location problems are one of the most well studied variants of hub location literature. The primary goal of these models is to allocate p hub facilities in a hub and spoke network so as to concentrate flows (demands) to benefit from economies of scale in cost of transportation. The application of p-hub networks extends beyond the field of telecommunication and includes air freight systems, postal delivery systems and airline industries and several transportation related systems. p-HLPs constitute a challenging class of HLPs and are known to be NP-hard. Several solution approaches have been developed from exact solutions using integer programming techniques to the development of metaheuristics. Even though metaheuristic algorithms cannot guarantee optimality, given complexity of large scale HLPs, they are being used for solving these problems. In this thesis, we focus on the multiple allocation uncapacitated p-hub location problem. Four solution algorithms will be proposed to this problem for solving the Australian Postal (AP) data instances. We start with a very simple algorithm and continue with more complicated one in order to present an efficient high quality feasible solution and to assess the impact of the quality of initial feasible solution on local improvement phase. Computational results from the different algorithms were compared to exact solutions to track the efficiency of the proposed algorithms.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical and Industrial Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Shobeiri, Ali |
| Institution: | Concordia University |
| Degree Name: | M.A. Sc. |
| Program: | Industrial Engineering |
| Date: | July 2015 |
| Thesis Supervisor(s): | Contreras, Ivan and Vidyarthi, Navneet |
| Keywords: | Multiple Allocation, GRASP, p-Hub Location , Uncapacitated, |
| ID Code: | 981261 |
| Deposited By: | SEYED ALI SHOBEIRI NEJAD |
| Deposited On: | 17 Jun 2016 15:05 |
| Last Modified: | 18 Jan 2018 17:52 |
References:
Alumur, S., Kara, B.Y. (2008). Network hub location problems: The state of the art. European Journal of Operational Research, 190(1): 1-21.Aykin,T. (1995).The hub location and routing problem. European Journal of Operational Research, 29(3):200-219.
Campbell, J.F. (1994b). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72:387-405.
Campbell, J.F. (1996). Hub location and the p-hub median problem. Operations Research, 44(6): 923-935.
Campbell, J.F., Ernst, A.T. and Krishnamoorthy, M., (2002). Hub location problems. In: Drezner, Z., Hamacher, H.W. (Eds.), Facility Location: Applications and Theory. Springer, Heidelberg, pp. 373-408.
Campbell, J. F., Ernst, A. T. and Krishnamoorthy, M. (2005).Hub arc location problems: Part I - introduction and results. Management Science, 51(10):1540-1555.
Campbell, A. M., Lowe, T. J., and Zhang, L. (2007). The p-hub center allocation problem. European Journal of Operational Research, 176(2):819-835.
Campbell, J.F., O’Kelly, M.E. (2012).Twenty-five years of hub location research. Transportation Science, 46(2):153-169.
Contreras, I. (2015). Hub location problems. In Location Science, pp. 311-344, Springer International Publishing.
Contreras, I., Cordeau, J.F. and Laporte, G. (2011a) stochastic uncapacitated hub location. European Journal of Operational Research, 212: 518-528.
Contreras, I., Cordeau, J.F. andLaporte, G. (2011c) Benders
decomposition for large-scale uncapacitated hub location. Operations Research, 59(6):1477-1490.
Ernst, A.T., Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated Single allocation p-hub median problem. Location Science, 4:139-154.
Ernst A.T., Krishnamoorthy M. (1998a). Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem. European Journal of Operational Research, 104: 100-112.
Ernst, A. T., Hamacher, H., Jiang, H., Krishnamoorthy, M., and Woeginger, G. (2009). Uncapacitated single and multiple allocation p-hub center problems.Computers & Operations Research, 36(7):2230-2241.
Feo T.A., Resende, M.G.C. (1995). A greedy randomized adaptive search procedure. Journal of global optimization. 6(2):109-133.
Garcia, S., Landete, M., and Marin, A. (2012). New formulation and a branch-and cut algorithm for the multiple allocation p-hub median problem. European Journal of Operational Research, 220(1):48-57.
Glover, F. (1996). Tabu search and adaptive memory programming-advances, applications and challenges. Interfaces in computer science and operations research. Kluwer, 1-75.
Golden, B., Skiscim, C. (1986). Using simulated annealing to solve routing and location problems. Naval Research Logistics Quarterly. 33:261-279.
Hakimi, SL. (1964). Optimal locations of switching centers and the absolute centers and medians of a graph. Operations Research 12(3): 450-459.
Hart, J.P., Shogan. A.W. (1987). Semi-greedy heuristics: An empirical study. Operations Research Letters.6:107-114.
Kara, B.Y., Tansel, B.C. (2000).On the single assignment p-hub center problem. European Journal of Operational Research, 125(3):648-55.
Kara, B. Y. and Tansel, B. C. (2001). The latest arrival hub location problem. Management Science, 47(10):1408-1420.
Kara, B.Y., Tansel, B.C. (2003). The single-assignment hub covering problem: Models and linearizations. Journal of the Operational Research Society, 54(1):59-64.
Kirkpatrick.S., Gclatt, C. D.,Vecchi, Jr. and Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598): 671-680.
Klincewicz, J.G. (1991). Heuristics for the p-hub location problem. European Journal of Operational Research. 53:25-37.
Klincewicz, J.G. (1992). Avoiding local optima in the p-hub location problem using tabu search and grasp. Annals of Operational Research, 40: 283-302.
Kratica, J. (2013). An electromagnetism-like metaheuristic for the uncapacitated multiple allocation p-hub median problem. Computers & Industrial Engineering, 66(4):1015-1024.
Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2:83-97.
Michalewicz, Z., Janikow, CZ (1992). A modified genetic algorithm for optimal control problems. Computers & Mathematics with Applications. 23(12):83-94.
Milanovic, M. (2010). A new evolutionary based approach for solving the uncapacitatedmultiple allocation p-hub median problem. In Soft Computing in IndustrialApplications, pages 81- 88. Springer.
O’Kelly, M.E. (1986a). Activity levels at hub facilities in interacting networks. Geographical Analysis, 18(4):343-356.
O’Kelly, M.E. (1986b). The location of interacting hub facilities. Transportation Science. 20:92-106.
O’Kelly, M.E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 32: 393-404.
O’Kelly, M.E. (1992). Hub facility location with fixed costs. Papers in Regional Science, 20(2): 293-306.
Pamuk, F. S. and Sepil, C. (2001). A solution to the hub center problem via a single-relocation algorithm with tabu search. IIE Transactions, 33(5):399-411.
Peiro, J., Corberan, A. and Marti, R. (2014). GRASP for the uncapacitated r-Allocation p-hub median problem. Computers & Operations Research 43: 50-60.
Pirkul, H. and Schilling, D. A. (1998). An efficient procedure for designing single allocation hub and spoke systems. Management Science, 44(12-Part-2):235-242.
Sasaki, M., Suzuki, A. and Drezner, Z. (1999). On the selection of hub airports for an airline hub-and spoke system. Computers and Operations Research. 26:1411-1422.
Skorin-Kapov, D., Skorin-Kapov, J. (1994). On tabu search for the location of interacting hub facilities. European Journal of Operations Research, 73:502-509.
Skorin-Kapov, D., Skorin-Kapov, J. and O’Kelly, M. (1996). Tight linear programming relaxations of uncapacitated p-hub median problems. European Journal of Operational Research, 73:501–508.
Sohn, J., Park, S. (1998). Efficient solution procedure and reduced size formulation for p-HLP. European Journal of Operational Research, 108:118-126.
Wagner, B. (2004). A note on “the latest arrival hub location problem”. Management science. 50(12):1751-1752.
Wagner, B. (2008). Model formulations for hub covering problems.
Journal of the Operational Research Society. 59(7):932-938.
Yaman, H., Kara, B. Y., and Tansel, B. C. (2007). The latest arrival hub location problem for cargo delivery systems with stopovers. Transportation Research Part B: Methodological, 41(8):906-919.
Yaman, H. (2011). Allocation strategies in hub networks. European Journal of Operational Research, 211(3):442-451.
Zanjirani-Farahani, R., Hekmatfar, M., Boloori-Arabani, A. and Nikbakhsh, E. (2013). Hub location problems: a review of models, classification, techniques and application. Computers & Industrial Engineering, 64(4):1096-1109.
Zanjirani-Farahani, R., Rezapour, S., Drezner, T., & Fallah, S. (2014). Competitive supply chain network design: An overview of classifications, models, solution techniques and applications. Omega, 45, 92-118.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics