Competitive hub location problem (CD)

By: Tiwari, RichaMaterial type: Computer fileComputer filePublication details: Ahmedabad Indian Institute of Management Ahmedabad 2021Description: 131 p. col. ill. Includes bibliographical referencesSubject(s): Hub location | Mixed integer second order conic program | Cutting Plane AlgorithmDDC classification: TH 2021-9 Online resources: eThesis Summary: Competition is an important, yet relatively unstudied, subject in the hub location literature. Through this thesis, we attempt to bridge this gap by studying the hub location problem under competition in the airline industry. The first essay discusses the hub location problem of a new airline, hereafter called the entrant, that wants to set up its hub & spoke network in order to maximize its share in a competitive market. Customers choose among competing airlines on the basis of utility provided by them, which depends on like price, travel time, and attractiveness of the airlines. The problem is modelled as a non-linear integer program, which is intractable for off-the-shelf commercial solvers. Hence, we propose four alternate solution approaches based on: i. Kelley’s cutting plane method; ii. mixed integer second order conic program based reformation; iii. Kelley’s cutting plane method within Lagrangian relaxation; and iv. second order conic program within Lagrangian relaxation. Our computational experiments based on benchmark datasets show the Kelley’s cutting plane within Lagrangian relaxation to perform the best, which is able to solve all the problem instances of upto 50 nodes within 10 minutes of CPU time. The second essay discusses the design of a more realistic hub & spoke network. We propose the hub location problem for the entrant in two alternate network settings: multiple allocation and single allocation. This further increases the computational challenge in solving an already difficult problem. We address this computational challenge by proposing three alternate solution approaches based on: I. mixed integer second order conic program based reformulation; ii. Kelley’s cutting plane method; and iii. Kelley’s cutting plane method within Lagrangian relaxation. Our computational experiments based on benchmark datasets show the Kelley’s cutting plane within Lagrangian relaxation to perform the best, which is able to solve all the problem instances of upto 50 nodes within 120 and 10 minutes of CPU time for single and multiple allocation setting, respectively. The third essay extends the entrant’s model to incorporate uncertainty in demand, for which we are interested in finding a solution that is robust to any changes in the demand. We model the uncertainty in demand using an ellipsoidal uncertainty set. This introduces additional non-linearities in the problem, and makes the problem computationally even more challenging to solve. We address this challenge by first proposing mixed integer second order conic program based reformulation of the problem. To solve the resulting formulation, we propose two alternate solution approaches. The first one is a cutting-plane method based on three types of lifted polymatroid cuts, while the second one is based on Lagrangian relaxation. Our computational experiments based on benchmark datasets demonstrate the superiority of the first method, which is on average 33% and 41% faster than the second approach for single and multiple allocation, respectively. Papers arising from this thesis are at various stages of publication. The first paper, based on essay 1, is accepted for publication in European Journal of Operational Research (Click here). The second paper, based on essay 2, is under the first round of review in Transportation Research Part B: Methodological. The third paper, based on essay 3, has been submitted to Transportation Science.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Collection Call number Status Date due Barcode
Thesis (FPM) Vikram Sarabhai Library
Reference
Non-fiction TH 2021-9 (Browse shelf(Opens below)) Not for Issue (Restricted Access) CD002653

Thesis Advisory Committee
Prof Sachin Jayaswal (Chairperson)
Prof Ankur Sinha (Co-Chairperson)
Prof Navneet Vidyarthi (Member)

Competition is an important, yet relatively unstudied, subject in the hub location literature. Through this thesis, we attempt to bridge this gap by studying the hub location problem under competition in the airline industry.
The first essay discusses the hub location problem of a new airline, hereafter called the entrant, that wants to set up its hub & spoke network in order to maximize its share in a competitive market. Customers choose among competing airlines on the basis of utility provided by them, which depends on like price, travel time, and attractiveness of the airlines. The problem is modelled as a non-linear integer program, which is intractable for off-the-shelf commercial solvers. Hence, we propose four alternate solution approaches based on: i. Kelley’s cutting plane method; ii. mixed integer second order conic program based reformation; iii. Kelley’s cutting plane method within Lagrangian relaxation; and iv. second order conic program within Lagrangian relaxation. Our computational experiments based on benchmark datasets show the Kelley’s cutting plane within Lagrangian relaxation to perform the best, which is able to solve all the problem instances of upto 50 nodes within 10 minutes of CPU time.
The second essay discusses the design of a more realistic hub & spoke network. We propose the hub location problem for the entrant in two alternate network settings: multiple allocation and single allocation. This further increases the computational challenge in solving an already difficult problem. We address this computational challenge by proposing three alternate solution approaches based on: I. mixed integer second order conic program based reformulation; ii. Kelley’s cutting plane method; and iii. Kelley’s cutting plane method within Lagrangian relaxation. Our computational experiments based on benchmark datasets show the Kelley’s cutting plane within Lagrangian relaxation to perform the best, which is able to solve all the problem instances of upto 50 nodes within 120 and 10 minutes of CPU time for single and multiple allocation setting, respectively.
The third essay extends the entrant’s model to incorporate uncertainty in demand, for which we are interested in finding a solution that is robust to any changes in the demand. We model the uncertainty in demand using an ellipsoidal uncertainty set. This introduces additional non-linearities in the problem, and makes the problem computationally even more challenging to solve. We address this challenge by first proposing mixed integer second order conic program based reformulation of the problem. To solve the resulting formulation, we propose two alternate solution approaches. The first one is a cutting-plane method based on three types of lifted polymatroid cuts, while the second one is based on Lagrangian relaxation. Our computational experiments based on benchmark datasets demonstrate the superiority of the first method, which is on average 33% and 41% faster than the second approach for single and multiple allocation, respectively.
Papers arising from this thesis are at various stages of publication. The first paper, based on essay 1, is accepted for publication in European Journal of Operational Research (Click here). The second paper, based on essay 2, is under the first round of review in Transportation Research Part B: Methodological. The third paper, based on essay 3, has been submitted to Transportation Science.

There are no comments on this title.

to post a comment.

Powered by Koha