Solving uncapacitated multiple allocation p-hub center problem by Dijkstra’s algorithm-based genetic algorithm and simulated annealing

Rabbani, M.; Kazemi, S.

Growing Science » International Journal of Industrial Engineering Computations » Solving uncapacitated multiple allocation p-hub center problem by Dijkstra’s algorithm-based genetic algorithm and simulated annealing

Journals

IJIEC Volumes

Volume 1 (17)
- Issue 1 (9)
- Issue 2 (8)

Volume 2 (68)
- Issue 1 (12)
- Issue 2 (20)
- Issue 3 (20)
- Issue 4 (16)

Volume 3 (76)
- Issue 1 (9)
- Issue 2 (15)
- Issue 3 (20)
- Issue 4 (12)
- Issue 5 (20)

Volume 4 (50)
- Issue 1 (14)
- Issue 2 (10)
- Issue 3 (12)
- Issue 4 (14)

Volume 5 (47)
- Issue 1 (13)
- Issue 2 (12)
- Issue 3 (12)
- Issue 4 (10)

Volume 6 (39)
- Issue 1 (7)
- Issue 2 (12)
- Issue 3 (10)
- Issue 4 (10)

Volume 7 (47)
- Issue 1 (10)
- Issue 2 (14)
- Issue 3 (10)
- Issue 4 (13)

Volume 8 (30)
- Issue 1 (9)
- Issue 2 (7)
- Issue 3 (8)
- Issue 4 (6)

Volume 9 (32)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (7)
- Issue 4 (10)

Volume 10 (34)
- Issue 1 (8)
- Issue 2 (10)
- Issue 3 (8)
- Issue 4 (8)

Volume 11 (36)
- Issue 1 (9)
- Issue 2 (8)
- Issue 3 (9)
- Issue 4 (10)

Volume 12 (29)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (8)
- Issue 4 (6)

Volume 13 (41)
- Issue 1 (10)
- Issue 2 (8)
- Issue 3 (10)
- Issue 4 (13)

Volume 14 (50)
- Issue 1 (11)
- Issue 2 (15)
- Issue 3 (9)
- Issue 4 (15)

Volume 15 (55)
- Issue 1 (19)
- Issue 2 (15)
- Issue 3 (12)
- Issue 4 (9)

Keywords

Authors

Countries

International Journal of Industrial Engineering Computations

ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print) Quarterly Publication Volume 6 Issue 3 pp. 405-418 , 2015

Solving uncapacitated multiple allocation p-hub center problem by Dijkstra’s algorithm-based genetic algorithm and simulated annealing Pages 405-418 Download PDF

Authors: Masoud Rabbani, Seyed Mahmood Kazemi

DOI: 10.5267/j.ijiec.2015.2.002

Keywords: Dijkstra’s algorithm, Genetic Algorithm, P-hub center problem, Simulated Annealing

Abstract: In the existing literature, there are a huge number of studies focused on p-hub median problems and inventing heuristic or metaheuristic algorithms for solving them. But such analogous body of literature does not exist for its counterpart problem; p-hub center problem. In fact, since p-hub center has been lately introduced and has a particular objective function, minimizing the maximum cost between origin-destination nodes, there are few studies investigating the problem and the challenges for solving it. In this study, after presenting a complete definition of the uncapacitated multiple allocation p-hub center problem (UMApHCP) two well-known metaheuristic algorithms are proposed to solve the problem for small scale and large scale standard data sets. These two algorithms are one single solution-based algorithm, Simulated Annealing (SA), and one population-based metaheuristic, Genetic Algorithm (GA). Because of the particular nature of the problem, Dijkstra’s algorithm has been incorporated in the fitness function calculation part of the proposed methods. The numerical results of running the GA and SA for standard test problems show that for smaller scale test problems, single solution-based SA shows greater performance versus GA but for larger scales of data sets the GA generally yield more desirable solutions.

How to cite this paper

 Rabbani, M & Kazemi, S. (2015). Solving uncapacitated multiple allocation p-hub center problem by Dijkstra’s algorithm-based genetic algorithm and simulated annealing.International Journal of Industrial Engineering Computations , 6(3), 405-418.

Refrences

Alumur, S., & Kara, B. Y. (2008). Network hub location problems: The state of the art. European Journal of Operational Research, 190(1), 1-21.

Bashiri, M., Mirzaei, M., & Randall, M. (2013). Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution. Applied Mathematical Modelling, 37(5), 3513-3525.

Baumgartner, S. (2003). Polyhedral analysis of hub center problems (Doctoral dissertation, Technische Universit?t Kaiserslautern).

Campbell, A. M., Lowe, T. J., & Zhang, L. (2007). The p-hub center allocation problem. European Journal of Operational Research, 176(2), 819-835.

Campbell, J. F. (1994). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72(2), 387-405.

Campbell, J. F., & O & apos; Kelly, M. E. (2012). Twenty-five years of hub location research. Transportation Science, 46(2), 153-169.

Contreras, I., Cordeau, J. F., & Laporte, G. (2011). Stochastic uncapacitated hub location. European Journal of Operational Research, 212(3), 518-528.

Contributors, W. (2014). Dijkstra & apos; s algorithm. Wikipedia, The Free Encyclopedia.

Ernst, A. T., Hamacher, H., Jiang, H., Krishnamoorthy, M., & Woeginger, G. (2009). Uncapacitated single and multiple allocation p-hub center problems.Computers & Operations Research, 36(7), 2230-2241.

Farahani, R. Z., Hekmatfar, M., Arabani, A. B., & Nikbakhsh, E. (2013). Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering, 64(4), 1096-1109.

Gavriliouk, E. O. (2009). Aggregation in hub location problems. Computers & Operations Research, 36(12), 3136-3142.

Hult, E., Jiang, H., & Ralph, D. (2014). Exact computational approaches to a stochastic uncapacitated single allocation p-hub center problem. Computational Optimization and Applications, 59(1-2), 185-200.

Kara, B. Y., & Tansel, B. C. (2000). On the single-assignment p-hub center problem. European Journal of Operational Research, 125(3), 648-655.

Kratica, J., & Stanimirovi?, Z. (2006). Solving the uncapacitated multiple allocation p-hub center problem by genetic algorithm. Asia-Pacific Journal of Operational Research, 23(04), 425-437.

Liang, H. (2013). The hardness and approximation of the star -hub center problem. Operations Research Letters, 41, 138-141.

Meyer, T., Ernst, A. T., & Krishnamoorthy, M. (2009). A 2-phase algorithm for solving the single allocation p-hub center problem. Computers & Operations Research, 36(12), 3143-3151.

Mohammadi, M., Tavakkoli-Moghaddam, R., Ghodratnama, A., & Rostami, H. (2011). Genetic and Improved Shuffled Frog Leaping Algorithms for a 2-Stage Model of a Hub Covering Location Network.

Mohammadi, M., Tavakkoli-Moghaddam, R., & Rostami, H. (2011b). A multi-objective imperialist competitive algorithm for a capacitated hub covering location problem. International Journal of Industrial Engineering Computations, 2, 671-688.

Pamuk, F. S., & Sepil, C. (2001). A solution to the hub center problem via a single-relocation algorithm with tabu search. IIE Transactions, 33(5), 399-411.

Sim, T., Lowe, T.J., & Thomas, B.W. (2009). The stochastic -hub center problem with service-level constraints. Computers & Operations Research 36(12), 3166-3177.

Yaman, H., & Elloumi, S. (2012). Star p-hub center problem and star p-hub median problem with bounded path lengths. Computers & Operations Research, 39, 2725-2732.

Yaman, H., Kara, B.Y., & Tansel, B.C. (2007). The latest arrival hub location problem for cargo delivery systems with stopovers. Transportation Research Part B: Methodological, 41, 906-919.

Yang, K., Liu, Y.-K., & Yang, G.-Q. (2013a). Solving fuzzy p-hub center problem by genetic algorithm incorporating local search. Applied Soft Computing, 13, 2624-2632.

Yang, K., Liu, Y., & Yang, G. (2013b). An improved hybrid particle swarm optimization algorithm for fuzzy p-hub center problem. Computers & Industrial Engineering, 64, 133-142.

Yang, K., Liu, Y., & Yang, G. (2014). Optimizing fuzzy p-hub center problem with generalized value-at-risk criterion. Applied Mathematical Modelling, 38, 3987-4005.