Generalized Network Design Problems (eBook)

Modeling and Optimization

(Autor)

eBook Download: PDF
2012
213 Seiten
De Gruyter (Verlag)
978-3-11-026768-6 (ISBN)
Systemvoraussetzungen
169,95 inkl. MwSt
  • Download sofort lieferbar
  • Zahlungsarten anzeigen

Generalized network design is a very hot topic of research. The monograph describes in a unified manner a series of mathematical models, methods, propositions, and algorithms developed in the last years on generalized network design problems. The book consists of seven chapters, where in addition to an introductory chapter, a number of six generalized network design problems are formulated and examined. The book will be useful for researchers and graduate students interested in operations research, optimization, applied mathematics, and computer science. Due to the substantial practical importance of some presented problems, researchers in other areas will also find it useful.



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

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

Erscheint lt. Verlag 30.10.2012
Reihe/Serie De Gruyter Series in Discrete Mathematics and Applications
De Gruyter Series in Discrete Mathematics and Applications
ISSN
ISSN
Zusatzinfo 40 b/w ill., 30 b/w tbl.
Verlagsort Berlin/Boston
Sprache englisch
Themenwelt Mathematik / Informatik Informatik Theorie / Studium
Mathematik / Informatik Mathematik Allgemeines / Lexika
Mathematik / Informatik Mathematik Algebra
Mathematik / Informatik Mathematik Angewandte Mathematik
Technik
Schlagworte Generalized Network Designed Problem • Heuristic Algorithm • Heuristic Algorithm, Metaheuristic Algorithm • Integer Programming • metaheuristic algorithm • Modeling • Network • network design • Network Design Problem • Optimization
ISBN-10 3-11-026768-3 / 3110267683
ISBN-13 978-3-11-026768-6 / 9783110267686
Haben Sie eine Frage zum Produkt?
PDFPDF (Wasserzeichen)
Größe: 1,9 MB

DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasser­zeichen und ist damit für Sie persona­lisiert. Bei einer missbräuch­lichen Weiter­gabe des eBooks an Dritte ist eine Rück­ver­folgung an die Quelle möglich.

Dateiformat: PDF (Portable Document Format)
Mit einem festen Seiten­layout eignet sich die PDF besonders für Fach­bücher mit Spalten, Tabellen und Abbild­ungen. Eine PDF kann auf fast allen Geräten ange­zeigt werden, ist aber für kleine Displays (Smart­phone, eReader) nur einge­schränkt geeignet.

Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.

Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.

Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.

Mehr entdecken
aus dem Bereich
Discover tactics to decrease churn and expand revenue

von Jeff Mar; Peter Armaly

eBook Download (2024)
Packt Publishing (Verlag)
25,19