Hub location models in public transport planning [Elektronische Ressource] / von Shahin Gelareh

Sujets

• Handel

Informations

• Publié par: technische_universitat_kaiserslautern
• Publié le: 01 janvier 2008
• Nombre de lectures: 29
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

Hub Location Models in Public
Transport Planning
Vom Fachbereich Mathematik
der Technischen Universit at Kaiserslautern
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
(Doctor rerum naturalium, Dr. rer. nat.)
genehmigte
Dissertation
von
Shahin Gelareh
Erstgutachter: Prof. Dr. Stefan Nickel
Zweitgutachterin: Prof. Dr. Elena Fern andez
Datum der Disputation: 21. April 2008
D 386Dedicated to
Agha, Baba, Rahimeh, Azin
and the memory of Azizeh.Preface
In the name of God
First of all, I must be thankful of who owns the creation and supports me throughout
my life. There is no doubt that all what I gained so far owes to his auspice and attention.
The outcome of this research, whatever it is, has strongly been in uenced by many
people who accompanied me during the whole or part of the work in my private and
academic life. I take this opportunity to express my sincere thanks to them and ap-
preciate their support.
The most, I am grateful and owing my family, parents and especially my father,
Shaban Ali Gelareh and my grandfather, Abd Al-Rahim Chaloshtar Mokari who always
supported me throughout my education. They initiated the rst steps and continu-
ously supported me during this work to reach this milestone. They have been and will
always be paragons in my mind. Forever, I will be indebted to Ms. Sedigheh Makaremi
and her family for their endless support.
I am very much indebted to my wife, Rahimeh Nematian Monemi for her endless
patience in recent years which shared with me. Her support strongly in uenced my
work.
I would like to thank Prof. Dr. Stefan Nickel as my supervisor for o ering me
the opportunity, necessary scienti c freedom and support to carry out this disserta-
tion. Without his support and patience, this dissertation would not reach to this point.
Special thanks to Prof. Dr. Elena Fern andez from Universitat Politecnica de Catalunya
as the second referee of my thesis. Many thanks to Prof. Dr. Horst. W. Hamacher
for o ering me the opportunity in Hub Location workshop. I would like to thank Dr.
Alfredo Mar n-Perez from Universidad de Murcia (Spain) and Prof. Dr. Bernard Fortz
from Universite Libre de Bruxelles for our inspiring and fruitful discussion and their
useful hints.ii
Armin, Azin, Bahram, Maziar, Bobak, Shahriar Makaremi, Sassan Khajehali and
Nazira Heinrich deserve my gratitude for their support.
Finally, I acknowledge the Department of Optimization of Fraunhofer Institute for
Industrial Mathematics (ITWM) for o ering me a motivating scienti c environment to
carry out this work.
Kaiserslautern, May 2008 Shahin GelarehContents
1 Introduction 1
1.1 Hub Location Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Multi-Period Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Solution Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Hub Location Problems 7
2.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Examples of Real-Life Applications . . . . . . . . . . . . . . . . 9
2.2 Traits of Hub-and-Spoke Networks . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 Single vs. Multiple Allocation . . . . . . . . . . . . . . . . . . . 14
2.3.2 Capacities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5.1 Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.2 Polyhedral Studies . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.3 Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.5 Solution Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Mathematical Formulations 31
3.1 Classical Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Mathematical Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1 Primary Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.2 Available HLP Models for Public Transport . . . . . . . . . . . 34
3.2.3 New Model for Public Transport Application . . . . . . . . . . . 37
3.2.4 HLPPT vs. PT . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.5 Computational Comparison . . . . . . . . . . . . . . . . . . . . 42
3.3 Extensions to the Base Model of HLPPT . . . . . . . . . . . . . . . . 44
3.3.1 HLPPT Under Non-Restrictive Network Policy . . . . . . . . . 44
3.3.2 with Delay Considerations (DHLPPT) . . . . . . . . . 45
3.4 Additional HLP Models Derived from HLPPT . . . . . . . . . . . . . 46
3.4.1 Tree-Shaped HLPPT (TSHLPPT) . . . . . . . . . . . . . . . . 46
3.4.2 Polygonal HLPPT (PHLPPT) . . . . . . . . . . . . . . . . . . . 48iv CONTENTS
3.5 Multi Period Hub Location Model . . . . . . . . . . . . . . . . . . . . . 48
4 Lagrangian Relaxation and Integrality 53
4.1 Approach for HLPPT . . . . . . . . . . . . . . . . . . . . . 53
4.2 Integrality Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3 Sub-Problem Integrality . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Strengthened Formulation 59
5.1 Improving Valid Inequalities . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.1 E ect of Preprocessing on Computational Time . . . . . . . . . 65
5.2.2 Size Reduction by Exploiting Symmetry . . . . . . . . . . . . . 66
6 Benders Decomposition for HLPPT 69
6.1 Motivation of Applying on HLPs . . . . . . . . . . . . . . . . . . . . . 69
6.2 Benders Approach for Single Period HLPPT . . . . . . . . . . . . . . . 72
6.2.1 Master Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.2.2 Sub-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.3 Speeding Up the Convergence . . . . . . . . . . . . . . . . . . . . . . . 77
6.4 Splitting the Sub-Problem: Strength of the Cuts . . . . . . . . . . . . . 77
6.5 Strengthening the Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.5.1 Computational Results: Comparison Between SCs . . . . . . . . 82
6.6 Multiple Cuts vs. Single Cut . . . . . . . . . . . . . . . . . . . . . . . . 83
6.6.1 Results: Comparison Between MCs . . . . . . . 84
6.7 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.8 Accelerating Benders Approaches by Fractional Cuts . . . . . . . . . . 85
6.9 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.9.1 Classical Single Cut Benders Algorithm (SC1) . . . . . . . . . . 88
6.9.2 Modi ed Classical Single Cut Benders Algorithm (SC2) . . . . . 89
6.9.3 Multi-Cut Benders Algorithm (MC1) . . . . . . . . . . . . . . . 90
6.9.4 Modi ed Multi-Cut Benders Algorithm (MC2) . . . . . . . . . . 90
d6.9.5 Accelerated Multi-Cut Benders Algorithm (AMC2 ) . . . . . . . 90
7 Heuristic Method for HLPPT 95
7.1 Heuristic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.1.1 Metaheuristic Algorithm . . . . . . . . . . . . . . . . . . . . . . 95
7.2 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.2.1 Strategy and Elements . . . . . . . . . . . . . . . . . . . . . . . 96
7.2.2 Greedy Choice Priority . . . . . . . . . . . . . . . . . . . . . . . 96
7.2.3 Well-Known Greedy Algorithms . . . . . . . . . . . . . . . . . . 97
7.3 Greedy Algorithm for HLPPT . . . . . . . . . . . . . . . . . . . . . . 97
7.3.1 Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98CONTENTS v
7.3.2 Initial Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.3.3 Complexity and Neighborhood Size . . . . . . . . . . . . . . . . 101
7.3.4 Computational Results . . . . . . . . . . . . . . . . . . . . . . . 102
7.4 Improvement by Local Neighborhood Search . . . . . . . . . . . . . . . 103
7.4.1 Neighborhood Search I . . . . . . . . . . . . . . . . . . . . . . . 104
7.4.2 Neighborhood Search II . . . . . . . . . . . . . . . . . . . . . . 106
7.4.3 Neighborhood Size and Complexity . . . . . . . . . . . . . . . . 106
7.4.4 Quality of Solutions . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.4.5 Computational Results . . . . . . . . . . . . . . . . . . . . . . . 108
7.4.6 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.5 Heuristic for the DHLPPT . . . . . . . . . . . . . . . . . . . . . . . . 108
8 A Generalized Multi-Period HLPPT 113
8.1 Multi-Period Model for HLPPT (MPHLPPT) . . . . . . . . . . . . . 113
8.2 Mathematical Model of MPHLPPT . . . . . . . . . . . . . . . . . . . 114
8.2.1 Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
8.2.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.2.3 Mathematical Formulation . . . . . . . . . . . . . . . . . . . . . 116
8.3 Graphical Demonstration . .