Road Hub Location-Routing Issue in a Sparse and Distant Area

Document Type : Research Paper


1 Ph.D. Candidate in Production and Operations Management, University of Tehran, Tehran, Iran

2 Prof., School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

3 Prof., Dep. of Industrial Engineering, Sharif University of Technology, Tehran, Iran


In order to manage the expenditures in a road transportation network in which the transport demands between cities are less than a truckload capacity, one needs to determine the location of hubs at first, and then collect the cargo from the cities in some routes which are assigned to the appropriate hubs. In this paper, a special case of hub location-routing issue was considered that is suitable for the particular conditions of Iran as cities are located in the sparse and distant places. A mixed integer mathematical programming model was proposed. As the model is NP-hard in nature, a two-phase hybrid method including genetic algorithms and simulated annealing was designed to solve the model. The results of the comparison between the model and the outputs demonstrated the accuracy and speed of the proposed solution method. Finally, a real case including all 31 capital cities of Iran provinces was solved to illustrate the appropriate performance of the solution method.


Alumur, S., & Kara, B. Y. (2008). Network hub location problems: The state of the art. European journal of operational research, 190(1), 1-21.
Baker, B. M. & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.
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’Kelly, M. E. (2012). Twenty-five years of hub location research. Transportation Science, 46(2), 153-169.
Černý, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of optimization theory and applications, 45(1), 41-51.
Cunha, C. B. & Silva, M. R. (2007). A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil. European Journal of Operational Research, 179(3), 747-758.
Doulabi, S. H. H. & Seifi, A. (2013). Lower and upper bounds for location-arc routing problems with vehicle capacity constraints. European Journal of Operational Research, 224(1), 189-208.
Ernst, A.T. & Krishnamoorthy, M. (1996). Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location science, 4(3), 139-154.
Holland, J. H. (1992). Genetic algorithms. Scientific american, 267(1), 66-72.
Jarboui, B., Derbel, H., Hanafi, S. & Mladenović, N. (2013). Variable neighborhood search for location routing. Computers & Operations Research, 40(1), 47-57.
Karaoglan, I., Altiparmak, F., Kara, I. & Dengiz, B. (2012). The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach. Omega, 40(4), 465-477.
Krikpatrick, S., Gelatt Jr. C.D. & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220 (4598), 671-680.
Kuby, M. J. & Gray, R. G. (1993). The hub network design problem with stopovers and feeders: The case of Federal Express. Transportation Research Part A: Policy and Practice, 27(1), 1-12.
Laporte, G., (1988). Location-routing problems. In Golden, B.L., Assad, A.A. (eds) Vehicle Routing: Methods, Studies. North-Holland, Amsterdam.
Lee, J. H. & Moon, I. (2014). A hybrid hub-and-spoke postal logistics network with realistic restrictions: A case study of Korea Post. Expert systems with applications, 41(11), 5509-5519.
Lee, Y., Lim, B. H. & Park, J. S. (1996). A hub location problem in designing digital data service networks: Lagrangian relaxation approach. Location Science, 4(3), 185-194.
Lopes, R. B., Ferreira, C., Santos, B. S. & Barreto, S. (2013). A taxonomical analysis, current methods and objectives on location‐routing problems. International Transactions in Operational Research, 20(6), 795-822.
Martı́n, J. C. & Román, C. (2003). Hub location in the South-Atlantic airline market: A spatial competition game. Transportation Research Part A: Policy and Practice, 37(10), 865-888.
Nagy, G. & Salhi, S. (1998). The many-to-many location-routing problem. Top, 6(2), 261-275.
Nagy, G. & Salhi, S. (2007). Location-routing: Issues, models and methods. European Journal of Operational Research, 177(2), 649-672.
Norouzi, N., Sadegh-Amalnick, M. & Tavakkoli-Moghaddam, R. (2016). Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption. Optimization Letters, 11(1), 121-134.
O’kelly, M. E. (1986). The location of interacting hub facilities. Transportation science, 20(2), 92-106.
Razavi, M., Soukhakian, M. A. & Ziarati, K. (2011). A Meta Heuristic Algorithms Based on Ant Colony System For Solving Multi Depots Location-routing Problem with Multiple Using of Vehicle. Industrial Management, 3(6), 17-38. (in Persian)
Rieck, J., Ehrenberg, C. & Zimmermann, J. (2014). Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery. European Journal of Operational Research, 236(3), 863-878.
Salhi, S., & Rand, G. K. (1989). The effect of ignoring routes when locating depots. European journal of operational research, 39(2), 150-156.
Sasaki, M., Campbell, J.F., Krishnamoorthy, M. & Ernst, A.T. (2014). A Stackelberg hub arc location model for a competitive environment. Computers & Operations Research, 47, 27-41.
Sasaki, M., Suzuki, A. & Drezner, Z. (1999). On the selection of hub airports for an airline hub-and-spoke system. Computers & Operations Research, 26(14), 1411-1422.
Shahin, M., Jabalameli, M. S., Jabbarzadeh, A. (2017). Multi-modal and multi-product hierarchical hub location under uncertainty. Industrial Management, 8(4), 625-658. (in Persian)
Taylor, G. D., Harit, S., English, J. R. & Whicker, G. (1995). Hub and spoke networks in truckload trucking: Configuration, testing and operational concerns. Logistics and Transportation Review, 31(3), 209-237.
Toh, R. S. & Higgins, R. G. (1985). The impact of hub and spoke network centralization and route monopoly on domestic airline profitability. Transportation Journal, 24(4), 16-27.
Wasner, M. & Zäpfel, G. (2004). An integrated multi-depot hub-location vehicle routing model for network planning of parcel service. International Journal of Production Economics, 90(3), 403-419.
Wolsey, L. A. (1998). Integer programming. New York, John Wiley & Sons, Inc.
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(8), 906-919.