Alibeyg, Armaghan
(2017)
*Hub Network Design Problems with Profits.*
PhD thesis, Concordia University.

Preview |
Text (application/pdf)
3MBAlibeyg_PhD_S2017.pdf - Accepted Version Available under License Spectrum Terms of Access. |

## Abstract

In this thesis we study a new class of hub location problems denoted as \textit{hub network design problems with profits} which share the same feature: a profit oriented objective. We start from a basic model in which only routing and location decisions are involved. We then investigate more realistic models by incorporating new elements such as different types of network design decisions, service commitments constraints, multiple demand levels, multiple capacity levels and pricing decisions. We present mixed-integer programming formulations for each variant and extension and provide insightful computational analyses regarding to their complexity, network topologies and their added value compared to related hub location problems in the literature. Furthermore, we present an exact algorithmic framework to solve two variants of this class of problems. We continue this study by introducing joint hub location and pricing problems in which pricing decisions are incorporated into the decision-making process. We formulate this problem as a mixed-integer bilevel problem and provide feasible solutions using two math-heuristics. The dissertation ends with some conclusions and comments on avenues of future research.

Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical and Industrial Engineering |
---|---|

Item Type: | Thesis (PhD) |

Authors: | Alibeyg, Armaghan |

Institution: | Concordia University |

Degree Name: | Ph. D. |

Program: | Industrial Engineering |

Date: | March 2017 |

Thesis Supervisor(s): | Contreras, Ivan and Fernandez, Elena |

Keywords: | Hub location, network design, location analysis, network optimization |

ID Code: | 982210 |

Deposited By: | ARMAGHAN ALIBEYG |

Deposited On: | 31 May 2017 19:46 |

Last Modified: | 18 Jan 2018 17:54 |

## References:

[1] Aboolian, R., O. Berman, and D. Krass (2007). Competitive facility location and design problem. European Journal of Operational Research 182 (1), 40–62.[2] Adler, N. and K. Smilowitz (2007). Hub-and-spoke network alliances and mergers: Price-location competition in the airline industry. Transportation Research Part B 41(4), 394–409.

[3] Ahuja, R. K., T. L. Magnanti, and J. B. Orlin (1994). Network flows: theory, algorithms, and applications. Transportation Science 28 (4), 354–356.

[4] Alibeyg, A., I. Contreras, and E. Fern´andez (2014). A lagrangean relaxation for uncapacitated hub location problems with profits. In Conference Proceedings of the CLAIO, pp. in press.

[5] Alibeyg, A., I. Contreras, and E. Fern´andez (2016). An exact algorithm for hub network design problems with profits. Submitted to European Journal of Operational Research.

[6] Alibeyg, A., I. Contreras, and E. Fern´andez (2016). Hub network design problems with profits. Transportation Research Part E: Logistics and Transportation Review 96, 40–59.

[7] Alumur, S. and B. Y. Kara (2008). Network hub location problems: The state of the art. European Journal of Operational Research 190 (1), 1–21.

[8] Alumur, S. A., S. Nickel, and F. Saldanha-da Gama (2012). Hub location under uncertainty. Transportation Research Part B 46 (4), 529–543.

[9] ´Alvarez-Miranda, E., I. Ljubi´c, and P. Toth (2013). Exact approaches for solving robust prize-collecting steiner tree problems. European Journal of Operational Research 229 (3), 599–612.

[10] Amaldi, E., M. Bruglieri, and B. Fortz (2011). On the hazmat transport network design problem. In Network Optimization, pp. 327–338. Springer.

[11] Ar´aoz, J., E. Fern´andez, and O. Meza (2009). An LP based algorithm for the privatized rural postman problem. European Journal of Operational Research 196 (5), 866–896.

[12] Aras, N., D. Aksen, and M. Tu˘grul Tekin (2011). Selective multi-depot vehicle routing problem with pricing. Transportation Research Part C 19 (5), 866–884.

[13] Asgari, N., R. Z. Farahani, and M. Goh (2013). Network design approach for hub ports-shipping companies competition and cooperation. Transportation Research Part A 48, 1–18.

[14] Aykin, T. (1995). Networking policies for hub-and-spoke systems with application to the air transportation system. Transportation Science 29 (3), 201–221.

[15] Bouhtou, M., A. Grigoriev, S. v. Hoesel, A. F. Van Der Kraaij, F. C. Spieksma, and M. Uetz (2007). Pricing bridges to cross a river. Naval Research Logistics 54 (4), 411–420.

[16] Bouhtou, M., S. van Hoesel, A. F. van der Kraaij, and J.-L. Lutton (2007). Tariff optimization in networks. INFORMS journal on computing 19 (3), 458–469.

[17] Bracken, J. and J. T. McGill (1973). Mathematical programs with optimization problems in the constraints. Operations Research 21 (1), 37–44.

[18] Brotcorne, L., M. Labb´e, P. Marcotte, and G. Savard (2000). A bilevel model and solution algorithm for a freight tariff-setting problem. Transportation Science 34 (3), 289–302.

[19] Brotcorne, L., M. Labb´e, P. Marcotte, and G. Savard (2008). Joint design and pricing on a network. Operations Research 56 (5), 1104–1115.

[20] Bryan, D. L. and M. E. O’Kelly (1999). Hub-and-spoke networks in air transportation: An analytical review. Journal of Regional Science 39 (2), 275–295.

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

[22] Campbell, J. F. (1994b). A survey of network hub location. Studies in Locational Analysis 6 (6), 31–49.

[23] Campbell, J. F. (2013). A continuous approximation model for time definite many-to-many transportation. Transportation Research Part B 54, 100–112.

[24] Campbell, J. F., A. Ernst, and M. Krishnamoorthy (2005). Hub arc location problems part I: Introduction and results. Management Science 51 (10), 1540–1555.

[25] Campbell, J. F., A. T. Ernst, and M. Krishnamoorthy (2002). Hub location problems. In Facility location: applications and theory, Volume 1, pp. 373–407. Springer-Verlag, New York, NY.

[26] Campbell, J. F. and M. E. O’Kelly (2012). Twenty-five years of hub location research. Transportation Science 46 (2), 153–169.

[27] Candler, W. and R. Norton (1977). Multilevel programming. Technical report 20. World Bank Development Research Center, Washington, DC.

[28] Church, R. and C. R. ReVelle (1974). The maximal covering location problem. Papers in Regional Science 32 (1), 101–118.

[29] Colson, B., P. Marcotte, and G. Savard (2005). Bilevel programming: A survey. 4OR 3 (2), 87–107.

[30] Colson, B., P. Marcotte, and G. Savard (2007). An overview of bilevel optimization. Annals of Operations Research 153 (1), 235–256.

[31] Contreras, I. (2015). Hub location problems. In G. Laporte, F. Saldanha da Gama, and S. Nickel (Eds.), Location Science, pp. 311–344. Springer.

[32] Contreras, I., J.-F. Cordeau, and G. Laporte (2011a). Benders decomposition for large-scale uncapacitated hub location. Operations Research 59 (6), 1477–1490.

[33] Contreras, I., J.-F. Cordeau, and G. Laporte (2011b). The dynamic uncapacitated hub location problem. Transportation Science 45 (1), 18–32.

[34] Contreras, I., J.-F. Cordeau, and G. Laporte (2011c). Stochastic uncapacitated hub location. European Journal of Operational Research 212 (3), 518–528.

[35] Contreras, I., J.-F. Cordeau, and G. Laporte (2011a). The dynamic uncapacitated hub location problem. Transportation Science 45 (1), 18–32.

[36] Contreras, I., J. A. D´ıaz, and E. Fern´andez (2011b). Branch and price for largescale capacitated hub location problems with single assignment. INFORMS Journal on Computing 23 (1), 41–55.

[37] Contreras, I. and E. Fern´andez (2012). General network design: A unified view of combined location and network design problems. European Journal of Operational Research 219 (3), 680–697.

[38] Contreras, I. and E. Fern´andez (2014). Hub location as the minimization of a supermodular set function. Operations Research 62 (3), 557–570.

[39] Contreras, I., E. Fern´andez, and A. Mar´ın (2009b). Tight bounds from a path based formulation for the tree of hub location problem. Computers and Operations Research 36 (12), 3117–3127.

[40] Contreras, I., E. Fern´andez, and A. Mar´ın (2010). The tree of hubs location problem. European Journal of Operational Research 202 (2), 390–400.

[41] Contreras, I., E. Fern´andez, and G. Reinelt (2012). Minimizing the maximum travel time in a combined model of facility location and network design. Omega 40 (6), 847–860.

[42] Contreras, I., M. Tanash, and N. Vidyarthi (2016). Exact and heuristic approaches for the cycle hub location problem. Annals of Operations Research. DOI 10.1007/s10479-015-2091-2.

[43] Croxton, K. L., B. Gendron, and T. L. Magnanti (2007). Variable disaggregation in network flow problems with piecewise linear costs. Operations research 55 (1), 146–157.

[44] de Camargo, R. S., G. Miranda, and H. Luna (2008a). Benders decomposition for the uncapacitated multiple allocation hub location problem. Computers & Operations Research 35 (4), 1047–1064.

[45] de Camargo, R. S., G. Miranda, and H. P. Luna (2008b). Benders decomposition for the uncapacitated multiple allocation hub location problem. Computers and Operations Research 35 (4), 1047–1064.

[46] Dempe, S. (2002). Foundations of bilevel programming. Springer Science & Business Media.

[47] Dewez, S. and M. Labb´e (2004). On the toll setting problem, PhD thesis. Universit´e libre de Bruxelles, Bruxelles.

[48] Dewez, S., M. Labb´e, P. Marcotte, and G. Savard (2008). New formulations and valid inequalities for a bilevel pricing problem. Operations research letters 36 (2), 141–149.

[49] Drexl, M. and M. Schneider (2015). A survey of variants and extensions of the location-routing problem. European Journal of Operational Research 241 (2), 283–308.

[50] Ebery, J., M. Krishnamoorthy, A. Ernst, and N. Boland (2000). The capacitated multiple allocation hub location problem: Formulations and algorithms. European Journal of Operational Research 120 (3), 614–631.

[51] Eiselt, H. A. and V. Marianov (2009). A conditional p-hub location problem with attraction functions. Computers and Operations Research 36 (12), 3128–3135.

[52] Elhedhli, S. and H. Wu (2010). A lagrangean heuristic for hub-and-spoke system design with capacity selection and congestion. INFORMS Journal on Computing 22 (2), 282–296.

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

[54] Feillet, D., P. Dejax, and M. Gendreau (2005). Traveling salesman problems with profits. Transportation Science 39 (2), 188–205.

[55] Fisher, M. L. (1981). The lagrangian relaxation method for solving integer programming problems. Management science 27 (1), 1–18.

[56] Frangioni, A. and B. Gendron (2009). 0–1 reformulations of the multicommodity capacitated network design problem. Discrete Applied Mathematics 157 (6), 1229–1241.

[57] Garey, M. R. and D. S. Johnson (2002). Computers and intractability, Volume 29. wh freeman New York.

[58] Gelareh, S., R. N. Monemi, and S. Nickel (2015). Multi-period hub location problems in transportation. Transportation Research Part E: Logistics and Transportation Review 75, 67–94.

[59] Gelareh, S., S. Nickel, and D. Pisinger (2010). Liner shipping hub network design in a competitive environment. Transportation Research Part E 46 (6), 991–1004.

[60] Gendron, B., T. G. Crainic, and A. Frangioni (1999). Multicommodity capacitated network design. Springer.

[61] Goldman, A. (1969). Optimal locations for centers in a network. Transportation Science 3 (4), 352–360.

[62] Gouveia, L. and F. Saldanha-da Gama (2006). On the capacitated concentrator location problem: a reformulation by discretization. Computers & operations research 33 (5), 1242–1258.

[63] Grove, P. G. and M. E. O’Kelly (1986). Hub networks and simulated schedule delay. Papers in Regional Science 59 (1), 103–119.

[64] Hakimi, S. L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research 12 (3), 450–459.

[65] Hamacher, H. W., M. Labb´e, S. Nickel, and T. Sonneborn (2004). Adapting polyhedral properties from facility to hub location problems. Discrete Applied Mathematics 145 (1), 104–116.

[66] Hansen, P., B. Jaumard, and G. Savard (1992). New branch-and-bound rules for linear bilevel programming. SIAM Journal on scientific and Statistical Computing 13 (5), 1194–1217.

[67] Heilporn, G., M. Labb´e, P. Marcotte, and G. Savard (2010a). A parallel between two classes of pricing problems in transportation and marketing. Journal of Revenue & Pricing Management 9 (1), 110–125.

[68] Heilporn, G., M. Labb´e, P. Marcotte, and G. Savard (2010b). A polyhedral study of the network pricing problem with connected toll arcs. Networks 55 (3), 234–246.

[69] Heilporn, G., M. Labb´e, P. Marcotte, and G. Savard (2011). Valid inequalities and branch-and-cut for the clique pricing problem. Discrete Optimization 8 (3), 393–410.

[70] Hwang, Y. H. and Y. H. Lee (2012). Uncapacitated single allocation p-hub maximal covering problem. Computers and Industrial Engineering 63 (2), 382–389.

[71] Jaillet, P., G. Song, and G. Yu (1996). Airline network design and hub location problems. Location science 4 (3), 195–212.

[72] Jeroslow, R. G. (1985). The polynomial hierarchy and a simple model for competitive analysis. Mathematical programming 32 (2), 146–164.

[73] Joret, G. (2011). Stackelberg network pricing is hard to approximate. Networks 57 (2), 117–120.

[74] Kantorovich, L. V. (1942). On the transfer of masses. In Dokl. Akad. Nauk. SSSR, Volume 37, pp. 227–229.

[75] Kara, B. Y. and M. R. Taner (2011). Hub location problems: The location of interacting facilities. In Foundations of Location Analysis, pp. 273–288. Springer.

[76] Klincewicz, J. G. (1996). A dual algorithm for the uncapacitated hub location problem. Location Science 4 (3), 173–184.

[77] Kuehn, A. A. and M. J. Hamburger (1963). A heuristic program for locating warehouses. Management science 9 (4), 643–666.

[78] Labbe, M., G. Laporte, I. R. Mart´ın, and J. J. S. Gonzalez (2004). The ring star problem: Polyhedral analysis and exact algorithm. Networks 43 (3), 177–189.

[79] Labb´e, M., P. Marcotte, and G. Savard (1998). A bilevel model of taxation and its application to optimal highway pricing. Management Science 44 (12-part-1), 1608–1622.

[80] Labb´e, M. and A. Violin (2013). Bilevel programming and price setting problems. 4OR 11 (1), 1–30.

[81] Labb´e, M. and H. Yaman (2006). Polyhedral analysis for concentrator location problems. Computational optimization and applications 34 (3), 377–407.

[82] Labb´e, M. and H. Yaman (2008). Solving the hub location problem in a star–star network. Networks 51 (1), 19–33.

[83] Laporte, G., S. Nickel, and F. S. da Gama (2015). Location science. Springer.

[84] Lin, C.-C. and S.-C. Lee (2010). The competition game on hub network design. Transportation Research Part B 44 (4), 618–629.

[85] Lowe, T. and T. Sim (2012). The hub covering flow problem. Journal of the Operational Research Society 64 (7), 973–981.

[86] L¨uer-Villagra, A. and V. Marianov (2013). A competitive hub location and pricing problem. European Journal of Operational Research 231 (3), 734–744.

[87] Magnanti, T. L., P. Mirchandani, and R. Vachani (1995). Modeling and solving the two-facility capacitated network loading problem. Operations Research 43 (1), 142–157.

[88] Magnanti, T. L. and R. T. Wong (1984). Network design and transportation planning: Models and algorithms. Transportation science 18 (1), 1–55.

[89] Marianov, V., D. Serra, and C. ReVelle (1999). Location of hubs in a competitive environment. European Journal of Operational Research 114 (2), 363–371.

[90] Mar´ın, A. (2005a). Formulating and solving splittable capacitated multiple allocation hub location problems. Computers & operations research 32 (12), 3093–3109.

[91] Mar´ın, A. (2005b). Uncapacitated euclidean hub location: Strengthened formulation, new facets and a relax-and-cut algorithm. Journal of Global Optimization 33 (3), 393–422.

[92] Mar´ın, A., L. C´anovas, and M. Landete (2006). New formulations for the uncapacitated multiple allocation hub location problem. European Journal of Operational Research 172 (1), 274–292.

[93] Martins de S´a, E., I. Contreras, and J.-F. Cordeau (2015a). Exact and heuristic algorithms for the design of hub networks with multiple lines. European Journal of Operational Research 246 (1), 186–198.

[94] Martins de S´a, E., I. Contreras, J.-F. Cordeau, R. Saraiva de Camargo, and G. de Miranda (2015b). The hub line location problem. Transportation Science 49 (3), 500–518.

[95] Melkote, S. and M. S. Daskin (2001). An integrated model of facility location and transportation network design. Transportation Research Part A: Policy and Practice 35 (6), 515–538.

[96] Minoux, M. (1989). Networks synthesis and optimum network design problems: Models, solution methods and applications. Networks 19 (3), 313–360.

[97] Monge, G. (1781). M´emoire sur la th´eorie des d´eblais et des remblais. De l’Imprimerie Royale.

[98] Nagy, G. and S. Salhi (2007). Location-routing: Issues, models and methods. European Journal of Operational Research 177 (2), 649–672.

[99] O’Kelly, M. E. (1986). Activity levels at hub facilities in interacting networks. Geographical Analysis 18 (4), 343–356.

[100] O’Kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research 32 (3), 393–404.

[101] O’Kelly, M. E. (1992). Hub facility location with fixed costs. Papers in Regional Science 71 (3), 293–306.

[102] O’Kelly, M. E. (1998). A geographer’s analysis of hub-and-spoke networks. Journal of transport Geography 6 (3), 171–186.

[103] O’Kelly, M. E. (2012). Fuel burn and environmental implications of airline hub networks. Transportation Research Part D: Transport and Environment 17 (7), 555–567.

[104] O’Kelly, M. E., H. P. L. Luna, R. S. De Camargo, and G. de Miranda Jr (2015). Hub location problems with price sensitive demands. Networks and Spatial Economics 15 (4), 917–945.

[105] O’Kelly, M. E. and H. J. Miller (1994). The hub network design problem: a review and synthesis. Journal of Transport Geography 2 (1), 31–40.

[106] Orlin, J. B. (2012). Max flows in O(nm) time or better. In Proceedings of the 2013 Symposium on the Theory of Computing, pp. 765–774.

[107] Picard, J.-C. and H. D. Ratliff (1975). Minimum cuts and related problems. Networks 5 (4), 357–370.

[108] Pirkul, H. and D. A. Schilling (1998). An efficient procedure for designing single allocation hub and spoke systems. Management Science 44 (12), 235–242.

[109] Roch, S., P. Marcotte, and G. Savard (2003). Design and analysis of an approximation algorithm for Stackelberg network pricing. Citeseer.

[110] Saberi, M. and H. S. Mahmassani (2013). Modeling the airline hub location and optimal market problems with continuous approximation techniques. Journal of Transport Geography 30, 68–76.

[111] Sasaki, M., J. F. Campbell, A. Ernst, and M. Krishnamoorthy (2014). A Stackelberg hub arc location model for a competitive environment. Computers and Operations Research 47, 27–41.

[112] Sasaki, M., J. F. Campbell, M. Krishnamoorthy, and A. T. Ernst (2014). A stackelberg hub arc location model for a competitive environment. Computers & Operations Research 47, 27–41.

[113] Sasaki, M., A. Suzuki, and Z. Drezner (1999). On the selection of hub airports for an airline hub-and-spoke system. Computers and Operations Research 26 (14), 1411–1422.

[114] Shioda, R., L. Tun¸cel, and T. Myklebust (2011). Maximum utility product pricing models and algorithms based on reservation price. Computational Optimization and Applications 48 (2), 157–198.

[115] Smith, H. K., G. Laporte, and P. R. Harper (2009). Locational analysis: highlights of growth to maturity. Journal of the Operational Research Society 60, S140–S148.

[116] Toregas, C., R. Swain, C. ReVelle, and L. Bergman (1971). The location of emergency service facilities. Operations Research 19 (6), 1363–1373.

[117] Vicente, L., G. Savard, and J. J´udice (1994). Descent approaches for quadratic bilevel programming. Journal of Optimization Theory and Applications 81 (2), 379–399.

[118] Winter, P. (1987). Steiner problem in networks: a survey. Networks 17 (2), 129–167.

[119] Yaman, H. (2004). Concentrator location in telecommunications. Quarterly Journal of the Belgian, French and Italian Operations Research Societies 2 (2), 175–177.

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

Repository Staff Only: item control page