| Records |
| Author |
Alvarez-Miranda, E.; Pereira, J. |
| Title |
Designing and constructing networks under uncertainty in the construction stage: Definition and exact algorithmic approach |
Type |
|
| Year |
2017 |
Publication |
Computers & Operations Research |
Abbreviated Journal |
Comput. Oper. Res. |
| Volume |
81 |
Issue |
|
Pages |
178-191 |
| Keywords |
Network design; Network construction; Two-stage robust optimization; Exact algorithms |
| Abstract |
The present work proposes a novel Network Optimization problem whose core is to combine both network design and network construction scheduling under uncertainty into a single two-stage robust optimization model. The first-stage decisions correspond to those of a classical network design problem, while the second-stage decisions correspond to those of a network construction scheduling problem (NCS) under uncertainty. The resulting problem, which we will refer to as the Two-Stage Robust Network Design and Construction Problem (2SRNDC), aims at providing a modeling framework in which the design decision not only depends on the design costs (e.g., distances) but also on the corresponding construction plan (e.g., time to provide service to costumers). We provide motivations, mixed integer programming formulations, and an exact algorithm for the 2SRNDC. Experimental results on a large set of instances show the effectiveness of the model in providing robust solutions, and the capability of the proposed algorithm to provide good solutions in reasonable running times. (C) 2017 Elsevier Ltd. All rights reserved. |
| Address |
[Alvarez-Miranda, Eduardo] Univ Talca, Dept Ind Engn, Curico, Chile, Email: ealvarez@utalca.cl |
| Corporate Author |
|
Thesis |
|
| Publisher |
Pergamon-Elsevier Science Ltd |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0305-0548 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000394079400015 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
706 |
| Permanent link to this record |
| |
|
| |
| Author |
Averbakh, I.; Pereira, J |
| Title |
Tree optimization based heuristics and metaheuristics in network construction problems |
Type |
|
| Year |
2021 |
Publication |
Computers & Operations Research |
Abbreviated Journal |
Comput. Oper. Res. |
| Volume |
128 |
Issue |
|
Pages |
105190 |
| Keywords |
Network design; Scheduling; Network construction; Heuristics; Metaheuristics; Local search |
| Abstract |
We consider a recently introduced class of network construction problems where edges of a transportation network need to be constructed by a server (construction crew). The server has a constant construction speed which is much lower than its travel speed, so relocation times are negligible with respect to construction times. It is required to find a construction schedule that minimizes a non-decreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NP-hard on general networks, but are often tree-efficient, that is, polynomially solvable on trees. We develop a generic local search heuristic approach and two metaheuristics (Iterated Local Search and Tabu Search) for solving tree-efficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance. |
| Address |
|
| Corporate Author |
|
Thesis |
|
| Publisher |
|
Place of Publication |
|
Editor |
|
| Language |
|
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0305-0548 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000632975100009 |
Approved |
|
| Call Number |
UAI @ alexi.delcanto @ |
Serial |
1362 |
| Permanent link to this record |
| |
|
| |
| Author |
Averbakh, I.; Pereira, J. |
| Title |
Lateness Minimization in Pairwise Connectivity Restoration Problems |
Type |
|
| Year |
2018 |
Publication |
Informs Journal On Computing |
Abbreviated Journal |
INFORMS J. Comput. |
| Volume |
30 |
Issue |
3 |
Pages |
522-538 |
| Keywords |
combinatorial optimization; networks: scheduling; programming: branch and bound; network restoration; network construction; integrated network design and scheduling |
| Abstract |
A network is given whose edges need to be constructed (or restored after a disaster). The lengths of edges represent the required construction/restoration times given available resources, and one unit of length of the network can be constructed per unit of time. All points of the network are accessible for construction at any time. For each pair of vertices, a due date is given. It is required to find a construction schedule that minimizes the maximum lateness of all pairs of vertices, where the lateness of a pair is the difference between the time when the pair becomes connected by an already constructed path and the pair's due date. We introduce the problem and analyze its structural properties, present a mixed-integer linear programming formulation, develop a number of lower bounds that are integrated in a branch-and-bound algorithm, and discuss results of computational experiments both for instances based on randomly generated networks and for instances based on 2010 Chilean earthquake data. |
| Address |
[Averbakh, Igor] Univ Toronto Scarborough, Dept Management, Toronto, ON M1C 1A4, Canada, Email: averbakh@utsc.uturonto.ca; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Informs |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
1091-9856 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000449096000008 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
924 |
| Permanent link to this record |
| |
|
| |
| Author |
Barrera, J.; Cancela, H.; Moreno, E. |
| Title |
Topological optimization of reliable networks under dependent failures |
Type |
|
| Year |
2015 |
Publication |
Operations Research Letters |
Abbreviated Journal |
Oper. Res. Lett. |
| Volume |
43 |
Issue |
2 |
Pages |
132-136 |
| Keywords |
Common-cause failure; Dependent failure; Reliable network design; Sample average approximation |
| Abstract |
We address the design problem of a reliable network. Previous work assumes that link failures are independent. We discuss the impact of dropping this assumption. We show that under a common-cause failure model, dependencies between failures can affect the optimal design. We also provide an integer-programming formulation to solve this problem. Furthermore, we discuss how the dependence between the links that participate in the solution and those that do not can be handled. Other dependency models are discussed as well. (C) 2014 Elsevier B.V. All rights reserved. |
| Address |
[Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: javiera.barrera@uai.cl; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0167-6377 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000351968300003 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
480 |
| Permanent link to this record |
| |
|
| |
| Author |
Lagos, F.; Boland, N.; Savelsbergh, M. |
| Title |
Dynamic discretization discovery for solving the Continuous Time Inventory Routing Problem with Out-and-Back Routes |
Type |
|
| Year |
2022 |
Publication |
Computers & Operations Research |
Abbreviated Journal |
Comput. Oper. Res. |
| Volume |
141 |
Issue |
|
Pages |
105686 |
| Keywords |
NETWORK DESIGN; CUT ALGORITHM; DECOMPOSITION; POLICIES |
| Abstract |
In time dependent models, the objective is to find the optimal times (continuous) at which activities occur and resources are utilized. These models arise whenever a schedule of activities needs to be constructed. A common approach consists of discretizing the planning time and then restricting the decisions to those time points. However, this approach leads to very large formulations that are intractable in practice. In this work, we study the Continuous Time Inventory Routing Problem with Out-and-Back Routes (CIRP-OB). In this problem, a company manages the inventory of its customers, resupplying a single product from a single facility during a finite time horizon. The product is consumed at a constant rate (product per unit of time) by each customer. The customers have local storage capacity. The goal is to find the minimum cost delivery plan with out-and-back routes only that ensures that none of the customers run out of product during the planning period. We study the Dynamic Discovery Discretization algorithm (DDD) to solve the CIRP-OB by using partially constructed time-expanded networks. This method iteratively discovers time points needed in the network to find optimal continuous time solutions. We test this method by using randomly generated instances in which we find provable optimal solutions. |
| Address |
|
| Corporate Author |
|
Thesis |
|
| Publisher |
|
Place of Publication |
|
Editor |
|
| Language |
|
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0305-0548 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000762974200008 |
Approved |
|
| Call Number |
UAI @ alexi.delcanto @ |
Serial |
1541 |
| Permanent link to this record |
| |
|
| |
| Author |
Matus, O.; Barrera, J.; Moreno, E.; Rubino, G. |
| Title |
On the Marshall-Olkin Copula Model for Network Reliability Under Dependent Failures |
Type |
|
| Year |
2019 |
Publication |
IEEE Transactions On Reliability |
Abbreviated Journal |
IEEE Trans. Reliab. |
| Volume |
68 |
Issue |
2 |
Pages |
451-461 |
| Keywords |
Copula theory; failure analysis; network design; optimization methods; reliability |
| Abstract |
The Marshall-Olkin (MO) copulamodel has emerged as the standard tool for capturing dependence between components in failure analysis in reliability. In this model, shocks arise at exponential random times, that affect one or several components inducing a natural correlation in the failure process. However, because the number of parameter of the model grows exponentially with the number of components, MO suffers of the “curse of dimensionality.” MO models are usually intended to be applied to design a network before its construction; therefore, it is natural to assume that only partial information about failure behavior can be gathered, mostly from similar existing networks. To construct such an MO model, we propose an optimization approach to define the shock's parameters in the MO copula, in order to match marginal failures probabilities and correlations between these failures. To deal with the exponential number of parameters of this problem, we use a column-generation technique. We also discuss additional criteria that can be incorporated to obtain a suitable model. Our computational experiments show that the resulting MO model produces a close estimation of the network reliability, especially when the correlation between component failures is significant. |
| Address |
[Matus, Omar; Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Engn & Sci, Santiago 7941169, Chile, Email: omar.matus@edu.uai.cl; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Ieee-Inst Electrical Electronics Engineers Inc |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0018-9529 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000470826100005 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
1027 |
| Permanent link to this record |
