Alvarez-Miranda, Eduardo ORCID: 0000-0002-7788-0451, Cacchiani, Valentina, Lodi, Andrea, Parriani, Tiziano and Schmidt, Daniel R. ORCID: 0000-0001-7381-912X (2014). Single-commodity robust network design problem: Complexity, instances and heuristic solutions. Eur. J. Oper. Res., 238 (3). S. 711 - 724. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1872-6860

Full text not available from this repository.

Abstract

We study a single-commodity Robust Network Design problem (RND) in which an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. Previously conducted computational investigations on the problem motivated the study of the complexity of some special cases and we present complexity results on them, including hypercubes. In turn, these results lead to the definition of new instances (random graphs with {-1,0,1} balances) that are computationally hard for the natural flow formulation. These instances are then solved by means of a new heuristic algorithm for RND, which consists of three phases. In the first phase the graph representing the network is reduced by heuristically deleting a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model. Finally, the third phase applies a proximity search approach to further improve the solution, taking into account the original graph. The heuristic is tested on the new instances, and the comparison with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the proposed method. (C) 2014 Elsevier B.V. All rights reserved.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Alvarez-Miranda, EduardoUNSPECIFIEDorcid.org/0000-0002-7788-0451UNSPECIFIED
Cacchiani, ValentinaUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Lodi, AndreaUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Parriani, TizianoUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Schmidt, Daniel R.UNSPECIFIEDorcid.org/0000-0001-7381-912XUNSPECIFIED
URN: urn:nbn:de:hbz:38-425423
DOI: 10.1016/j.ejor.2014.04.023
Journal or Publication Title: Eur. J. Oper. Res.
Volume: 238
Number: 3
Page Range: S. 711 - 724
Date: 2014
Publisher: ELSEVIER SCIENCE BV
Place of Publication: AMSTERDAM
ISSN: 1872-6860
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: no entry
Uncontrolled Keywords:
KeywordsLanguage
ALGORITHMMultiple languages
Management; Operations Research & Management ScienceMultiple languages
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/42542

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item