A Bender’s Decomposition Algorithm for Multi-objective Hub Location Problem Considering Stochastic Characteristics

Abbasiparizi, Saeid; Aminnayeri, Majid; Bashiri, Mahdi

doi:10.22059/jieng.2014.52917

A Bender’s Decomposition Algorithm for Multi-objective Hub Location Problem Considering Stochastic Characteristics

Document Type : Research Paper

Authors

¹ School of Industrial Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, I.R. Iran

² Dept. of Industrial Engineering, Shahed University, Tehran, I.R. Iran

10.22059/jieng.2014.52917

Abstract

In this paper, a multi-objective hub location problem considering stochastic links and candidate nodes characteristics is modeled. The first objective is to minimize total costs, including setup and transportation costs. The second one is to minimize network risks. Characteristics such as weather conditions, safety, exchange rate, crisis, are defined as uncertainty parameters and considered as different scenarios. Due to the size of the numbers of scenarios, it is assumed that the distribution of their risks is considered to be normal. Also reliability levels associated to candidate hub nodes and links are considered as chance constraints. Moreover a Bender’s decomposition algorithm is utilized to solve the proposed model. In order to evaluate the performance of the proposed model, the results of this algorithm are compared to those of Cplex solver. The comparison shows that Cplex solver can solves small size problems but the Bender’s decomposition algorithm is capable of solving problems of large scale as well as small ones.

Keywords

References

1. Costa, M. G., Captivob, M. E., Clmacoc, J. (2008). “Capacitated single allocation hub location problem-A bi-criteria approach.” Computers & Operations Research, 35, 3671–3695.

2. Contreras, I., Cordeau, J. –F., and Laporte, G. (2011). “Stochastic uncapacitated hub location.” European Journal of Operational Research, 212 (3), 518–528.

3. Vasconcelos, A. D., Nassi, C. D., and Lopes, L. A. (2011). “The uncapacitated hublocation problem in networks underdecentralized management.” Computers & Operations Research, 38, 1656–1666.

4. Marianov, V. and Serra, D. (2003). “Location models for airline hubs behaving as M_/D_/cqueues.” Computers and Operations Research, 30, 983–1003.

5. Mirchandani, P. B. and Odoni, A. R. (1979). “Location of medians on stochastic networks.” Transportation Science, 13, 85-97.

6. Louveaux, F. V. and Thisse, J. -F. (1985). “Production and location on a network under uncertainty.” Operations Research Letters, 4, 145–149.

7. Barbarosoglu, G. and Arda, Y. (2004). “A two-stage stochastic programming framework for transportation planning in disaster response.” J. Oper. Res. Soc., 55 (1), 43–53.

8. Sheppard, E. S. (1974). “A conceptual framework for dynamic location-allocation analysis” Environment and Planning a 6, 547–564.

9. Mirchandani, P. B., Oudjit, A., and Wong, R. T. (1985). “Multidimensional extensions and a nested dual approach for the m-median problem.” European Journal of Operational Research, 21 (1), 121–137.

10. Weaver, J. R. and Church, R. L. (1983). “Computational procedures for location problems on stochastic networks.” Transportation Science, 17 (2), 168–180.

11. Laporte, G., Louveaux, F., V. and Hamme, L. (1994). “Exact solution to a location problem with stochastic demands.” Transportation Science, 28, 95–103.

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

13. Yang, T. -H. (2009). “Stochastic air freight hub location and flight routes planning.” Applied Mathematical Modeling, 33 (12), 4424–4430.

14. Tadei, R., Ricciardi, N., and Perboli, G. (2009). “The stochastic p-median problem with unknown cost probability distribution.” Operations Research Letters, 37, 135-141.

15. Snyder, V., Daskin, M., and Teo, C. (2007). “The stochastic location model with risk pooling.” European Journal of Operational Research, 179, 1221–1238.

16. Zhai, H., Liu, Y. i., and Chen, W. (2012). “Applying Minimum-Risk Criterion to Stochastic Hub Location Problem.” Procedia Engineering, 29, 2313–2321.

17. De Camargo, R. S., De Miranda, G., and Ferreira, R. P. (2011). “A hybrid Outer-Approximation_/Benders Decomposition algorithm for the single allocation hub location problem under congestion.” Operations Research Letters, 39, 329-337.

18. Correia, I., Stefan, N., and Francisco, S. G. (2010). "Single-assignment hub location problems with multiple capacity levels." Transportation Research Part B: Methodological, 44(8–9): 1047-1066.

19. Camargo, R. S., Miranda, Jr. G., and Luna, HP. (2008) “Benders decomposition for the uncapacitated multiple allocation hub location problem.” Computers & Operations Research, 2008; 35(4):1047–64.

20. Alumur, S., Nickel, S., and da Gama, F. S. (2012). "Hub location under uncertainty." Transportation Research Part B: Methodological, 46(4): 529-543.

21. Tarokh, M. J., EsmaeiliGookeh, M., and Torabi, Sh. (2012). “A Model to Optimize the Design of a Reverse Logistic Network under Uncertainty.” Journal of Industrial Engineering, University of Tehran, Volume 46, Issue 2, autumn 2012, Page 159-173.

22. Narenji, M., Forghani, A., and Pourebrahim, A. (2011). “A Prioritization Model for Investing Plans by Hierarchical Decision Making under Uncertainty (Interval Comparison Matrices); a Case Study.” Journal of Industrial Engineering, University of Tehran, Volume 45, Issue 2, autumn 2011, Page 229-237.

23. Omidbakhsh, M., Bagherinejad, J., and Seifbarghy, M. (2011). “Modeling Gravity Based Equitable Location Problem on Network and Solving by an Efficient Heuristic Method.” Journal of Industrial Engineering, University of Tehran, Volume 45, Issue 2, autumn 2011, Page 117-130.

24. Contreras, I., Fernandez, E., and Marin, A. (2010) “The tree of hubs location problem.” European Journal of Operational Research, 202:390–400.