Generalized Network Design Problems (eBook)

lt;!doctype html public "-//w3c//dtd html 4.0 transitional//en">

Petrica C. Pop, North University of Baia Mare, Romania.

Preface 5
1 Introduction 11
1.1 Combinatorial optimization and integer programming 11
1.2 Complexity theory 13
1.3 Heuristic and relaxation methods 15
1.4 Generalized network design problems 17
2 The Generalized Minimum Spanning Tree Problem (GMSTP) 19
2.1 Definition and complexity of the GMSTP 20
2.2 An exact algorithm for the GMSTP 22
2.3 Mathematical models of the GMSTP 24
2.3.1 Formulations based on tree properties 24
2.3.2 Formulations based on arborescence properties 27
2.3.3 Flow based formulations 29
2.3.4 A model based on Steiner tree properties 33
2.3.5 Local-global formulation of the GMSTP 34
2.4 Approximation results for the GMSTP 38
2.4.1 Introduction 39
2.4.2 Positive results: the design of the approximation algorithms 40
2.4.3 A negative result for the GMSTP 42
2.4.4 An approximation algorithm for the GMSTP with bounded cluster size 44
2.5 Solving the GMSTP 51
2.5.1 A branch-and-cut algorithm for solving the GMSTP 52
2.5.2 A heuristic algorithm for solving the GMSTP 54
2.5.3 Rooting procedure for solving the GMSTP 56
2.5.4 Solving the GMSTP with Simulated Annealing 58
2.6 Notes 69
3 The Generalized Traveling Salesman Problem (GTSP) 70
3.1 Definition and complexity of the GTSP 71
3.2 An efficient transformation of the GTSP into the TSP 71
3.3 An exact algorithm for the Generalized Traveling Salesman Problem 73
3.4 Integer programming formulations of the GTSP 75
3.4.1 Formulations based on the properties of Hamiltonian tours 75
3.4.2 Flow based formulations 76
3.4.3 A local-global formulation 79
3.5 Solving the Generalized Traveling Salesman Problem 81
3.5.1 Reinforcing ant colony system for solving the GTSP 82
3.5.2 Computational results 85
3.5.3 A hybrid heuristic approach for solving the GTSP 88
3.5.4 Computational results 98
3.6 The drilling problem 102
3.6.1 Stigmergy and autonomous robots 103
3.6.2 Sensitive robots 104
3.6.3 Sensitive robot metaheuristic for solving the drilling problem 104
3.6.4 Numerical experiments 107
3.7 Notes 109
4 The Railway Traveling Salesman Problem (RTSP) 110
4.1 Definition of the RTSP 110
4.2 Preliminaries 111
4.3 Methods for solving the RTSP 113
4.3.1 The size reduction method through shortest paths 113
4.3.2 A cutting plane approach for the RTSP 121
4.3.3 Solving the RTSP via a transformation into the classical TSP 124
4.3.4 An ant-based heuristic for solving the RTSP 129
4.4 Dynamic Railway Traveling Salesman Problem 131
4.4.1 Ant colony approach to the Dynamic RTSP 132
4.4.2 Implementation details and computational results 134
4.5 Notes 136
5 The Generalized Vehicle Routing Problem (GVRP) 138
5.1 Definition and complexity of the GVRP 139
5.2 An efficient transformation of the GVRP into a capacitated arc routing problem 140
5.3 Integer linear programming formulations of the GVRP 142
5.3.1 A general formulation 142
5.3.2 A node based formulation 145
5.3.3 Flow based formulations 147
5.4 A numerical example 149
5.5 Special cases of the proposed formulations 151
5.5.1 The Generalized multiple Traveling Salesman Problem 151
5.5.2 The Generalized Traveling Salesman Problem 153
5.5.3 The Clustered Generalized Vehicle Routing Problem 154
5.6 Solving the Generalized Vehicle Routing Problem 157
5.6.1 An improved hybrid algorithm for Solving the GVRP 157
5.6.2 An efficient memetic algorithm for solving the GVRP 164
5.6.3 Computational experiments 169
5.7 Notes 175
6 The Generalized Fixed-Charge Network Design Problem (GFCNDP) 177
6.1 Definition of the GFCNDP 178
6.2 Integer programming formulations of the GFCNDP 179
6.3 Solving the GFCNDP 183
6.4 Computational results 185
6.5 Notes 187
7 The Generalized Minimum Edge-Biconnected Network Problem (GMEBCNP) 188
7.1 Definition and complexity of the GMEBCNP 188
7.2 A mixed integer programming model of the GMEBCNP 189
7.3 Solving the GMEBCNP 191
7.3.1 Simple Node Optimization Neighborhood (SNON) 191
7.3.2 Node Re-Arrangement Neighborhood (NRAN) 192
7.3.3 Edge Augmentation Neighborhood 192
7.3.4 Node Exchange Neighborhood 193
7.3.5 Variable Neighborhood Descent 193
7.4 Computational results 195
7.5 Notes 195
Bibliography 198
Index 212