Mathematical Modeling of a Hierarchical Hub Routing Problem and Using the Benders Decomposition and Artificial Bee Colony Algorithms to Solve it

Document Type : Research Paper

Authors

Department of Industrial Engineering, Shahed University, Tehran, Iran

Abstract

The hierarchical hub routing network consists of 3 levels (customer, the non-central and
The hierarchical hub routing network consists of 3 levels (customer, the non-central and
central hubs), which aims to find the optimum location of the central and non-central hubs, allocation of customers to established hubs to find the optimal path between customers and non-central hubs. Among the functions of this model are for post, banks, and sending and receiving services. In this study, a MIP mathematical model is proposed. The hierarchical hub routing is based on the traveling salesman problem. So it is an NP-hard problem too, and to solve this model in the medium and large sizes, Benders’ decomposition and artificial bee colony algorithms are proposed respectively. The proposed artificial bee colony algorithms has some changes while it has been developed for continuous type problems. Results showed good performance of Benders decomposition and artificial bee colony in order to solve the model in medium and large sizes. Also the numerical examples and sensitivity analysis confirms validity of the proposed mathematical model.

Keywords

Main Subjects

References

  1. Alumur, S., and Kara, B. Y. (2008). “Network hub location problems: The state of the art”, European Journal of Operational Research, Vol. 190, No. 1, PP. 1–21.
  2. Farahani, R. Z., Hekmatfar, M., Arabani, A. B., and Nikbakhsh, E. (2013). “Hub location problems: A review of models, classification, solution techniques, and applications”, Computers & Industrial Engineering, Vol. 64, No. 4, PP. 1096–1109.
  3. Şahin, G., and Süral, H. (2007). “A review of hierarchical facility location models”, Computers & Operations Research, Vol. 34, No. 8, PP. 2310–2331.
  4. Farahani, R. Z., Hekmatfar, M., Fahimnia, B., and Kazemzadeh, N. (2014). “Hierarchical facility location problem: Models, classifications, techniques, and applications”, Computers & Industrial Engineering, Vol. 68, No. 0, PP. 104–117.
  5. Chou, Y. H. (1990). “The hierarchical-hub model for airline networks”, Transportation Planning and Technology, No. 14, PP. 243–258.
  6. Lin, C. C. and Chen, S. H. (2004). “The hierarchical network design problem for time-definite express common carriers”, Transportation Research Part B: Methodological, Vol. 38, No. 3, PP. 271–283.
  7. Yaman, H. (2009). “The hierarchical hub median problem with single assignment”, Transportation Research Part B: Methodological, Vol. 43, No. 6, PP. 643–658.
  8. Sahraeian, R., and Korani, E. (2010). The hierarchical hub maximal covering problem with determinate cover radiuses, Industrial Engineering and Engineering Management (IEEM), 2010 IEEE International Conference.
  9. Alumur, S. A., Yaman, H., and Kara, B. Y. (2012). “Hierarchical multimodal hub location problem with time-definite deliveries”, Transportation Research Part E: Logistics and Transportation Review, Vol. 48, No. 6, PP. 1107–1120.
  10. Rodríguez-Martína, I., Salazar-Gonzáleza, J., and Yaman, H., (2016). “A branch-and-cut algorithm for two-level survivable network design problems”, Computers & Operations Research, Vol. 67, No. 0, PP. 102–112.
  11. Pan S, Nigrelli, M., Ballot, E., Sarraj, B., and Yang, Y., (2015). “Perspectives of inventory control models in the physical internet: A simulation study”, Computers & Industrial Engineering, Vol. 84, No. 0, PP. 122–132.
  12. Chen, S. (2010). “A heuristic algorithm for hierarchical hub-and-spoke network of time-definite common carrier operation planning problem”, Networks and Spatial Economics, Vol. 10, No. 4, PP. 509–523.
  13. Prodhon, C., and Prins C. (2014). “A survey of recent research on location-routing problems”, European Journal of Operational Research, Vol. 238, No. 1, PP. 1–17.
  14. Jian, Z., Yaohua, W., and Pei, L. (2007). Routing problem for hybrid hub-and-spoke transportation network: A case study of a LTL carrier. Automation and Logistics, 2007 IEEE International Conference on.
  15. Çetiner, S., Sepil, C., and Süral, H. (2010). “Hubbing and routing in postal delivery systems”, Annals of Operations Research, Vol. 181, No. 1, PP. 109–124.
  16. De Camargo, R. S., de Miranda, G., and Løkketangen, A. (2013). “A new formulation and an exact approach for the many-to-many hub location-routing problem”, Applied Mathematical Modelling, Vol. 37, No. 12–13, PP. 7465–7480.
  17. Rodríguez-Martín, I., Salazar-González, J. J., and Yaman, H. (2014). “A branch-and-cut algorithm for the hub location and routing problem”, Computers & Operations Research, Vol. 50, No. 0, PP. 161–174.
  18. Karimi, H., and Setak, M. (2014). “Proprietor and customer costs in the incomplete hub location-routing network topology”, Applied Mathematical Modelling, Vol. 38, No. 3, PP. 1011–1023.
  19. Rieck, J., Ehrenberg, C., and Zimmermann, J. (2014). “Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery”, European Journal of Operational Research, Vol. 236, No. 3, PP. 863–878.
  20. Nagy, G. and Salhi, S. (1998). “The many-to-many location-routing problem”, Vol. 6, No. 2, PP. 261–275.
  21. Wasner, M., and Zäpfel, G. (2004). “An integrated multi-depot hub-location vehicle routing model for network planning of parcel service”, International Journal of Production Economics, Vol. 90, No. 3, PP. 403–419.
  22. Hsu, C. I. and Hsieh, Y. P. (2007). “Routing, ship size, and sailing frequency decision-making for a maritime hub-and-spoke container network”, Mathematical and Computer Modelling, Vol. 45, No. 7–8, PP. 899–916.
  23. Mingjun, J., Lixin, S., Baishun, S., Yanyan, X., and Fei, W. (2015). “Routing optimization for multi-type containerships in a hub-and-spoke network”, Journal of Traffic and Transportation Engineering, Vol. 2, No. 5, PP. 362–372.
  24. Benders, J. F. (1962). “Partitioning procedures for solving mixed-variables programming problems”, Numerische Mathematik, Vol. 4, No. 1, PP. 238–252.
  25. Karaboga, D. (2005). “An idea based on honey bee swarm for numerical optimization”, Technical report Computer Engineering Department, Engineering Faculty, Erciyes University
  26. Szeto, W. Y., Wu, Y., and Ho, S. C. (2011). “An artificial bee colony algorithm for the capacitated vehicle routing problem”, European Journal of Operational Research, Vol. 215, No. 1, PP. 126–135.
Advances in Industrial Engineering
Volume 51, Issue 3
October 2017
Pages 265-279

Files

Share

How to cite

Statistics