«A THESIS SUBMITTED TO THE DEPARTMENT OF INDUSTRIAL ENGINEERING AND THE INSTITUTE OF ENGINEERING AND SCIENCES OF BILKENT UNIVERSITY IN PARTIAL ...»
HUB LOCATION AND HUB NETWORK DESIGN
SUBMITTED TO THE DEPARTMENT OF INDUSTRIAL
AND THE INSTITUTE OF ENGINEERING AND SCIENCES
OF BILKENT UNIVERSITY
IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE DEGREE OF
DOCTOR OF PHILOSOPHYby Sibel Alev Alumur June 2009 I certify that I have read this thesis and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Assoc. Prof. Bahar Yetiş Kara (Principal Advisor) I certify that I have read this thesis and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Prof. Erhan Erkut I certify that I have read this thesis and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Prof. Barbaros Ç. Tansel ii I certify that I have read this thesis and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Assoc. Prof. Haldun Süral I certify that I have read this thesis and that in my opinion it is fully adequate, in scope and in quality, as a dissertation for the degree of Doctor of Philosophy.
Assoc. Prof. Oya Ekin Karaşan
Approved for the Institute of Engineering and Sciences:
Prof. Mehmet Baray Director of Institute of Engineering and Sciences iii
HUB LOCATION AND HUB NETWORK DESIGNSibel Alev Alumur Ph.D. in Industrial Engineering Supervisor: Assoc. Prof. Bahar Y. Kara June 2009 The hub location problem deals with finding the location of hub facilities and allocating the demand nodes to these hub facilities so as to effectively route the demand between origin–destination pairs. Hub location problems arise in various application settings in telecommunication and transportation. In the extensive literature on the hub location problem, it has widely been assumed that the subgraph induced by the hub nodes is complete. Throughout this thesis we relax the complete hub network assumption in hub location problems and focus on designing hub networks that are not necessarily complete. We approach to hub location problems from a network design perspective. In addition to the location and allocation decisions, we also study the decision on how the hub network must be designed. We focus on the single allocation version of the problems where each demand center is allocated to a single hub node. We start with introducing the 3-stop hub covering network design problem. In this problem, we aim to design hub networks so that all origin– destination pairs receive service by visiting at most three hubs on a route.
Then, we include hub network design decisions in the classical hub location problems introduced in the literature. We introduce the single allocation incomplete p-hub median, hub location with fixed costs, hub covering, and piv hub center network design problems to the literature. Lastly, we introduce the multimodal hub location and hub network design problem. We include the possibility of using different hub links, and allow for different transportation modes between hubs, and for different types of service time promises between origin–destination pairs, while designing the hub network in the multimodal problem. In this problem, we jointly consider transportation costs and travel times, which are studied separately in hub location problems presented in the literature. Computational analyses with all of the proposed models are presented on the various instances of the CAB data set and on the Turkish network.
Keywords: Hub location, incomplete hub network design, p-hub median, phub center, hub cover, multimodal hub location.
Ana Dağıtım Üssü (ADÜ) yer seçimi problemleri kaynak ve gidilecek yer arasında istenilen servisi sağlamak üzere ADÜ’lerin yerleştirilmesi ve talep noktalarının ADÜ’lere atanması problemlerini içermektedir. ADÜ yer seçimi problemlerinin çok çeşitli uygulamaları mevcuttur. Bu uygulamalar ulaşım ve telekomünikasyon alanlarında yoğunlaşmıştır. ADÜ yer seçimi literatüründeki birçok çalışmada tam serim bir ADÜ ağı varsayılmaktadır. Gerçek hayattaki çok çeşitli uygulamalarda tam serim bir ADÜ ağına gerek duyulmadığı gözlemlenmiştir. Bu çalışmada ADÜ yer seçimi problemlerindeki tam serim ADÜ ağı varsayımı gevşetilmiş ve ADÜ yer seçimi problemlerine ADÜ ağı tasarımı kararları da eklenmiştir. Bu bağlamda ilk olarak üç duraklı ADÜ kaplama problemi üzerinde çalışılmıştır. Bu problemde, kaynak ve gidilecek yer arasındaki servisin belirli bir zaman limiti içerisinde ve en fazla üç ADÜ’ye uğrayarak gerçekleşmesi sağlanmaktadır. Daha sonra, literatürde önerilen temel ADÜ yer seçimi problemlerine ADÜ ağı tasarımı kararları eklenmiştir. Yeni ADÜ yer seçimi ve ağ tasarımı problemleri tanımlanmış ve bu problemlere etkin matematiksel modeller önerilmiştir. Son olarak, çok yollu ADÜ yer seçimi ve ağ tasarımı problemi incelenmiştir. Bu problemde vi literatürde ayrı olarak ele alınan maliyet ve servis süreleri birlikte göz önüne alınmış ve daha gerçekçi bir matematiksel model önerilmiştir. Bu model ayrıca, ADÜ’ler arasında farklı taşıma yolları kullanılmasına ve farklı ikililerin farklı servis süreleri içinde servis almasına olanak sağlamaktadır. Önerilen tüm modeller literatürde yaygın olarak kullanılan CAB veri seti ve Türkiye verisi üzerinde denenmiş ve etkili sonuçlar alınmıştır.
Anahtar Kelimeler: ADÜ yer seçimi problemi, ADÜ ağı tasarımı, Modelleme.
First, I would like to express my sincere gratitude to Assoc. Prof. Bahar Yetiş Kara. I would not even considered a Ph.D. study if I was not working with such a great supervisor. She was there for me at all times, encouraged and trusted me, both in my professional and personal life, throughout my whole graduate study. ‘Bahar Hocam’, I feel lucky and privileged to have you as my academic mother.
I am also very grateful to Assoc. Prof. Oya Ekin Karaşan. She was always enthusiastic to share our problems and to find a better attitude. I certainly believe that her ideas upgraded my thesis. It was such a great pleasure to have worked with you ‘Oya Hocam’.
I am indebted to other members of my dissertation committee: Prof. Erhan Erkut, Prof. Barbaros Tansel, and Assoc. Prof. Haldun Süral for willingly accepting to be a member of my committee and to read and review this thesis.
Their remarks and recommendations have been very helpful.
I would like to thank our department chair Prof. İhsan Sabuncuoğlu, who has helped me in every way that he can, and also from our department to Figen Eren, Prof. Ülkü Gürler, Yeşim Karadeniz and Assoc. Prof. Hande Yaman for their intimacy. I am very proud to be a graduate of Bilkent University Industrial Engineering Department.
I am also grateful to TÜBİTAK, who supported my research during my Ph.D.study.
ix I am mostly indebted to my family. My dearest husband Bahadır Alev always motivated me, tried to understand and find a solution to all of my problems, and let me believe that I can handle. My mother Nural Alumur and brother Volkan Alumur always supported and believed in me. It is magnificent to feel that they are always proud of me. I am sure my father Demir Alumur would also be very proud and very eager to read and understand every word of this thesis. I also like to thank all the members of my rather new ‘Alev’ family.
Finally, I would like to express my gratitude to my whole friends who have always been there for me, and to all the current and previous members of the room EA327. Life and the graduate study would not have been bearable without them.
I’m dedicating this thesis to my mother Nural Alumur, for all her sacrifice and for raising me to become the person that I am today.
2 THE HUB LOCATION LITERATURE
2.1 The p-hub Median Problem
2.1.1 Single Allocation
2.1.2 Multiple Allocation
2.2 The Hub Location Problem with Fixed Costs
2.3 The p-hub Center Problem
2.4 Hub Covering Problems
2.5 Other Studies
3 THE 3-STOP HUB COVERING NETWORK DESIGN PROBLEM 24
3.1 Motivation and Problem Definition
3.2 Mathematical Model
3.4 Computational Results
4 MINIMIZATION OF TOTAL TRANSPORTATION COSTS INDESIGNING INCOMPLETE HUB NETWORKS
4.2 The Incomplete p-hub Median Network Design Problem
4.4 Computational Analysis
NETWORK DESIGN PROBLEMS
5.1 The Incomplete Hub Covering Network Design Problem..................65
network design problem
5.1.2 Incorporating Valid Inequalities
5.1.3 Computational Results
5.2 The Incomplete p-hub Center Network Design Problem
5.2.1 Mathematical Formulation
5.2.2 Computational Results
6 MULTIMODAL HUB LOCATION AND HUB NETWORK DESIGNPROBLEM
6.1 Motivation and Problem Definition
6.2 Mathematical Model
6.3 Enhancing the Model
6.3.2 Valid Inequalities
6.3.3 Lower Bound
6.3.4 Upper Bound
6.4 Computational Analysis
7 CONCLUSIONS AND FUTURE RESEARCH DIRECTIONS........134 BIBLIOGRAPHY
A LOCATIONS OF DEMAND CENTERS AND POTENTIAL HUBNODES IN CAB AND TURKISH NETWORK DATA SETS................151
1.1 (a) A completely interconnected network with 7 demand centers, (b) a hub network with 3 hubs and 7 demand centers
3.1 Decision variables of the mathematical model
3.2 Computational results on the Turkish network
3.3 Computational results on the CAB data set
4.1 CAB data set results with the transportation cost objective.................. 59
4.2 Trade-off curve with α=0.8 and p=5
5.1 Spanning tree idea
5.2 Incomplete hub covering results with the CAB data set
5.3 Incomplete hub covering results with the Turkish network.................. 82
6.1 Resulting hub networks
A.1 Names and geographical locations of the cities in the CAB data set.. 152 A.2 Geographical locations of the 81 demand centers and names of the 16 candidate hub locations on the Turkish network
3.1 Parameters for the Turkish network
3.2 CPU times on the Turkish network
3.3 Parameters for the CAB network
3.4 The CPU times for the CAB data set
4.1 The results on the CAB data set with the incomplete p-hub median problem
4.2 Incomplete p-hub median results on the Turkish network
5.1 Test bed for valid inequalities
5.2 Solution times (in seconds) with valid inequalities
5.3 Incomplete hub covering results on the CAB data set
5.4 Incomplete hub covering results on the Turkish network
5.5 Performance of the hub covering model with CPLEX on large networks
5.6 Incomplete p-hub center results on the CAB data set
5.7 Incomplete p-hub center results on the Turkish network
6.1 Test bed for |N|=25, |H|=8
6.2 The effect of valid inequalities
6.3 The effect of the lower bound and the performance of the solution with complete hub network