Limit search to available items
Book Cover
E-book
Author Pop, Petrică C.

Title Generalized Network Design Problems : Modeling and Optimization
Published Berlin : De Gruyter, 2012

Copies

Description 1 online resource (ix, 203 pages)
Series De Gruyter Series in Discrete Mathematics and Applications ; 1
De Gruyter series in discrete mathematics and applications ; 1.
Contents Preface; 1 Introduction; 1.1 Combinatorial optimization and integer programming; 1.2 Complexity theory; 1.3 Heuristic and relaxation methods; 1.4 Generalized network design problems; 2 The Generalized Minimum Spanning Tree Problem (GMSTP); 2.1 Definition and complexity of the GMSTP; 2.2 An exact algorithm for the GMSTP; 2.3 Mathematical models of the GMSTP; 2.3.1 Formulations based on tree properties; 2.3.2 Formulations based on arborescence properties; 2.3.3 Flow based formulations; 2.3.4 A model based on Steiner tree properties; 2.3.5 Local-global formulation of the GMSTP
2.4 Approximation results for the GMSTP2.4.1 Introduction; 2.4.2 Positive results: the design of the approximation algorithms; 2.4.3 A negative result for the GMSTP; 2.4.4 An approximation algorithm for the GMSTP with bounded cluster size; 2.5 Solving the GMSTP; 2.5.1 A branch-and-cut algorithm for solving the GMSTP; 2.5.2 A heuristic algorithm for solving the GMSTP; 2.5.3 Rooting procedure for solving the GMSTP; 2.5.4 Solving the GMSTP with Simulated Annealing; 2.6 Notes; 3 The Generalized Traveling Salesman Problem (GTSP); 3.1 Definition and complexity of the GTSP
3.2 An efficient transformation of the GTSP into the TSP3.3 An exact algorithm for the Generalized Traveling Salesman Problem; 3.4 Integer programming formulations of the GTSP; 3.4.1 Formulations based on the properties of Hamiltonian tours; 3.4.2 Flow based formulations; 3.4.3 A local-global formulation; 3.5 Solving the Generalized Traveling Salesman Problem; 3.5.1 Reinforcing ant colony system for solving the GTSP; 3.5.2 Computational results; 3.5.3 A hybrid heuristic approach for solving the GTSP; 3.5.4 Computational results; 3.6 The drilling problem; 3.6.1 Stigmergy and autonomous robots
3.6.2 Sensitive robots3.6.3 Sensitive robot metaheuristic for solving the drilling problem; 3.6.4 Numerical experiments; 3.7 Notes; 4 The Railway Traveling Salesman Problem (RTSP); 4.1 Definition of the RTSP; 4.2 Preliminaries; 4.3 Methods for solving the RTSP; 4.3.1 The size reduction method through shortest paths; 4.3.2 A cutting plane approach for the RTSP; 4.3.3 Solving the RTSP via a transformation into the classical TSP; 4.3.4 An ant-based heuristic for solving the RTSP; 4.4 Dynamic Railway Traveling Salesman Problem; 4.4.1 Ant colony approach to the Dynamic RTSP
4.4.2 Implementation details and computational results4.5 Notes; 5 The Generalized Vehicle Routing Problem (GVRP); 5.1 Definition and complexity of the GVRP; 5.2 An efficient transformation of the GVRP into a capacitated arc routing problem; 5.3 Integer linear programming formulations of the GVRP; 5.3.1 A general formulation; 5.3.2 A node based formulation; 5.3.3 Flow based formulations; 5.4 A numerical example; 5.5 Special cases of the proposed formulations; 5.5.1 The Generalized multiple Traveling Salesman Problem; 5.5.2 The Generalized Traveling Salesman Problem
5.5.3 The Clustered Generalized Vehicle Routing Problem
Summary 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
Bibliography Includes bibliographical references and index
Subject Combinatorial optimization.
Computer networks -- Design and construction -- Mathematical models
Linear programming
MATHEMATICS -- Applied.
MATHEMATICS -- Probability & Statistics -- General.
Combinatorial optimization
Linear programming
Civil & Environmental Engineering.
Engineering & Applied Sciences.
Operations Research.
Form Electronic book
LC no. 2012028924
ISBN 9783110267686
3110267683
9783110267693
3110267691