Generalized network design problems. Modeling and optimization.
type: Item
instance of: scholarly article
title: Generalized network design problems. Modeling and optimization.
zbMATH Open document ID: 1260.90143
DOI: 10.1515/9783110267686
author: Petrica Pop
published in: De Gruyter Series in Discrete Mathematics and Applications
publication date: 2012-10-04T00:00:00Z
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90-02
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6090161
zbMATH Keywords: network design
zbMATH Keywords: spanning tree problem
zbMATH Keywords: traveling salesman
zbMATH Keywords: vehicle routing
zbMATH Keywords: railway traveling salesman
zbMATH Keywords: heuristics
zbMATH Keywords: approximation algorithm
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1515/9783110267686
OpenAlex ID: W583659471
review text: In this monograph, several basic network design problems (such as the minimum spanning tree problem or the traveling salesman problem) are generalized in the following way. Let \(G=(V,E)\) be an undirected graph with vertex set \(V\) and edge set \(E\), where the vertices are partitioned into pairwise disjoint clusters \(V_1, V_2, \dots ,V_k\) and each edge \(e\in E\) has associated a nonnegative cost \(c_e\). The aim is to find a subgraph \(G'=(V',E')\) of \(G\) which contains exactly one vertex from each cluster such that \(G'\) has a prescribed property depending on the actual problem (e.g. \(G'\) is required to be a tree or a cycle) and the total edge cost of \(G'\) is minimized. The generalized problems are NP-hard. In the special case when each cluster is a singleton one gets the basic problem.NEWLINENEWLINE From the contents:NEWLINENEWLINE 1. Introduction (combinatorial optimization and integer programming, complexity theory, heuristic and relaxation methods, generalized network design problems);NEWLINENEWLINE 2. Generalized minimum spanning tree problem (GMSTP) (mathematical models, approximation results, solving the GMSTP);NEWLINENEWLINE 3. Generalized traveling salesman problem (GTSP) (an efficient transformation, an exact algorithm, solving the GTSP, the drilling problem);NEWLINENEWLINE 4. Railway traveling salesman problem (RTSP) (methods for solving the RTSP, dynamic RTSP);NEWLINENEWLINE 5. Generalized vehicle routing problem (GVRP) (complexity, an efficient transformation to a capacitated arc routing problem, integer linear programming formulations, solving the GVRP);NEWLINENEWLINE 6. Generalized fixed-charge network design problem (GFCNDP) (integer programming formulations, solving the GFCNDP);NEWLINENEWLINE 7. Generalized minimum edge-biconnected network problem (GMEBCNP) (complexity, a mixed integer programming model of the GMEBCNP, solving the GMEBCNP).NEWLINENEWLINEMethods for solving the problems are accompanied by computational results. Each cha…
description: scientific article; zbMATH DE number 6090161