Genetic Algorithm-Based Optimization Approach for an Uncapacitated Single Allocation P-hub Center Problem with more realistic cost structure

Document Type : Research Paper

Authors

1 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran

3 School of Industrial Engineering, College of Engineering, University of Tehran

Abstract

A p-hub center network design problem is definition of some nodes as hubs and allocation of non-hub nodes to them wherein the maximum travel times between any pair of nodes is minimized. The distinctive feature of this study is proposing a new mathematical formulation for modeling costs in a p-hub center problem. Here, instead of considering costs as a linear function of distance, for the first time, we formulate costs as a summation of different parts: fixed cost, Health, Safety and Environment (HSE) cost, energy cost and personnel cost. Such integrated model results in a hard-to-solve nonlinear formulation. To validate the proposed model, a small scale problem instance of CAB dataset solved by LINGO software. Because of inability to solve bigger problems, we prepared a Genetic Algorithm (GA) by MATLAB software to solve complete problems of CAB and AP datasets.

Keywords

Main Subjects


ABYAZI-SANI, R. & GHANBARI, R. 2016. An efficient tabu search for solving the uncapacitated single allocation hub location problem. Computers & Industrial Engineering, 93, 99-109.
ALIZADEH, Y., TAVAKKOLI-MOGHADDAM, R. & EBRAHIMNEJAD, S. 2016. A new multi-objective model for a capacitated hub covering problem solving by two multi-objective evolutionary algorithms. International Journal of Mathematics in Operational Research, 9, 99-124.
AVERSA, R., BOTTER, R., HARALAMBIDES, H. & YOSHIZAKI, H. 2005. A mixed integer programming model on the location of a hub port in the east coast of South America. Maritime Economics & Logistics, 7, 1-18.
BASHIRI, M., MIRZAEI, M. & RANDALL, M. 2013. Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution. Applied Mathematical Modelling, 37, 3513-3525.
CAMPBELL, J. F. 1994. 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, 923-935.
CORREIA, I., NICKEL, S. & SALDANHA-DA-GAMA, F. 2014. Multi-product capacitated single-allocation hub location problems: formulations and inequalities. Networks and Spatial Economics, 14, 1-25.
DAMGACIOGLU, H., DINLER, D., OZDEMIREL, N. E. & IYIGUN, C. 2015. A genetic algorithm for the uncapacitated single allocation planar hub location problem. Computers & Operations Research, 62, 224-236.
EISELT, H. A. & MARIANOV, V. 2009. A conditional p-hub location problem with attraction functions. Computers & Operations Research, 36, 3128-3135.
ERNST, A., HAMACHER, H., JIANG, H., KRISHNAMOORTHY, M. & WOEGINGER, G. 2002. Heuristic algorithms for the uncapacitated hub center single allocation problem. Unpublished Report, CSIRO Mathematical and Information Sciences, Australia.
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, 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, 1096-1109.
GHADERI, A. & RAHMANIANI, R. 2016. Meta-heuristic solution approaches for robust single allocation p-hub median problem with stochastic demands and travel times. The International Journal of Advanced Manufacturing Technology, 82, 1627-1647.
HOLLAND, J. H. 1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, U Michigan Press.
ABYAZI-SANI, R. & GHANBARI, R. 2016. An efficient tabu search for solving the uncapacitated single allocation hub location problem. Computers & Industrial Engineering, 93, 99-109.
ALIZADEH, Y., TAVAKKOLI-MOGHADDAM, R. & EBRAHIMNEJAD, S. 2016. A new multi-objective model for a capacitated hub covering problem solving by two multi-objective evolutionary algorithms. International Journal of Mathematics in Operational Research, 9, 99-124.
AVERSA, R., BOTTER, R., HARALAMBIDES, H. & YOSHIZAKI, H. 2005. A mixed integer programming model on the location of a hub port in the east coast of South America. Maritime Economics & Logistics, 7, 1-18.
BASHIRI, M., MIRZAEI, M. & RANDALL, M. 2013. Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution. Applied Mathematical Modelling, 37, 3513-3525.
CAMPBELL, J. F. 1994. 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, 923-935.
CORREIA, I., NICKEL, S. & SALDANHA-DA-GAMA, F. 2014. Multi-product capacitated single-allocation hub location problems: formulations and inequalities. Networks and Spatial Economics, 14, 1-25.
DAMGACIOGLU, H., DINLER, D., OZDEMIREL, N. E. & IYIGUN, C. 2015. A genetic algorithm for the uncapacitated single allocation planar hub location problem. Computers & Operations Research, 62, 224-236.
EISELT, H. A. & MARIANOV, V. 2009. A conditional p-hub location problem with attraction functions. Computers & Operations Research, 36, 3128-3135.
ERNST, A., HAMACHER, H., JIANG, H., KRISHNAMOORTHY, M. & WOEGINGER, G. 2002. Heuristic algorithms for the uncapacitated hub center single allocation problem. Unpublished Report, CSIRO Mathematical and Information Sciences, Australia.
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, 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, 1096-1109.
GHADERI, A. & RAHMANIANI, R. 2016. Meta-heuristic solution approaches for robust single allocation p-hub median problem with stochastic demands and travel times. The International Journal of Advanced Manufacturing Technology, 82, 1627-1647.
HOLLAND, J. H. 1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, U Michigan Press.
HWANG, Y. H. & LEE, Y. H. 2012. Uncapacitated single allocation p-hub maximal covering problem. Computers & Industrial Engineering, 63, 382-389.
KARA, B. & TANSEL, B. 2003. The single-assignment hub covering problem: Models and linearizations. Journal of the Operational Research Society, 54, 59-64.
KARA, B. Y. & TANSEL, B. C. 2000. On the single-assignment p-hub center problem. European Journal of Operational Research, 125, 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, 425-437.
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, 3143-3151.
O’KELLY, M. E. 2012. Fuel burn and environmental implications of airline hub networks. Transportation Research Part D: Transport and Environment, 17, 555-567.
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, 405-418.
RABBANI, M., ZAMENI, S. & KAZEMI, S. M. Proposing a new mathematical formulation for modeling costs in a p-hub center problem.  Modeling, Simulation and Applied Optimization (ICMSAO), 2013 5th International Conference on, 2013. IEEE, 1-4.
RAHIMI, Y., TAVAKKOLI-MOGHADDAM, R., MOHAMMADI, M. & SADEGHI, M. 2016. Multi-objective hub network design under uncertainty considering congestion: An M/M/c/K queue system. Applied Mathematical Modelling, 40, 4179-4198.
ROSTAMI, B., MEIER, J., BUCHHEIM, C. & CLAUSEN, U. 2015. The uncapacitated single allocation p-hub median problem with stepwise cost function. Tech. rep., Optimization Online.
SEDEHZADEH, S., TAVAKKOLI-MOGHADDAM, R., BABOLI, A. & MOHAMMADI, M. 2015. Optimization of a multi-modal tree hub location network with transportation energy consumption: A fuzzy approach. Journal of Intelligent & Fuzzy Systems, 30, 43-60.
STANIMIROVIĆ, Z. 2012. A genetic algorithm approach for the capacitated single allocation p-hub median problem. Computing and Informatics, 29, 117-132.
TOPCUOGLU, H., CORUT, F., ERMIS, M. & YILMAZ, G. 2005. Solving the uncapacitated hub location problem using genetic algorithms. Computers & Operations Research, 32, 967-984.
YAMAN, H., KARA, B. Y. & TANSEL, B. Ç. 2007. The latest arrival hub location problem for cargo delivery systems with stopovers. Transportation Research Part B: Methodological, 41, 906-919.
ZADE, A. E., SADEGHEIH, A. & LOTFI, M. M. 2014. A modified NSGA-II solution for a new multi-objective hub maximal covering problem under uncertain shipments. Journal of Industrial Engineering International, 10, 185-197.