Browsing by Author "Marianov, Vladimir"
Now showing 1 - 16 of 16
Results Per Page
Sort Options
- ItemA branch and cut algorithm for the hierarchical network design problem(ELSEVIER SCIENCE BV, 2010) Obreque, Carlos; Donoso, Macarena; Gutierrez, Gabriel; Marianov, VladimirThe Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added. branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes. (C) 2008 Elsevier B.V. All rights reserved.
- ItemA branch-and-cluster coordination scheme for selecting prison facility sites under uncertainty(PERGAMON-ELSEVIER SCIENCE LTD, 2012) Hernandez, Patricio; Alonso Ayuso, Antonio; Bravo, Fernanda; Escudero, Laureano F.; Guignard, Monique; Marianov, Vladimir; Weintraub, AndresA multi-period stochastic model and an algorithmic approach to location of prison facilities under uncertainty are presented and applied to the Chilean prison system. The problem consists of finding locations and sizes of a preset number of new jails and determining where and when to increase the capacity of both new and existing facilities over a time horizon, while minimizing the expected costs of the prison system. Constraints include maximum inmate transfer distances, upper and lower bounds for facility capacities, and scheduling of facility openings and expansion, among others. The uncertainty lies in the future demand for capacity, because of the long time horizon under study and because of the changes in criminal laws, which could strongly modify the historical tendencies of penal population growth. Uncertainty comes from the effects of penal reform in the capacity demand. It is represented in the model through probabilistic scenarios, and the large-scale model is solved via a heuristic mixture of branch-and-fix coordination and branch-and-bound schemes to satisfy the constraints in all scenarios, the so-called branch-and-cluster coordination scheme. We discuss computational experience and compare the results obtained for the minimum expected cost and average scenario strategies. Our results demonstrate that the minimum expected cost solution leads to better solutions than does the average scenario approach. Additionally, the results show that the stochastic algorithmic approach that we propose outperforms the plain use of a state-of-the-art optimization engine, at least for the three versions of the real-life case that have been tested by us. (c) 2011 Published by Elsevier Ltd.
- ItemA branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows(ELSEVIER, 2010) Gutierrez Jarpa, Gabriel; Desaulniers, Guy; Laporte, Gilbert; Marianov, VladimirIn the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers. (C) 2010 Elsevier B.V. All rights reserved.
- ItemAn optimal procedure for solving the hierarchical network design problem(TAYLOR & FRANCIS INC, 2007) Obreque, Carlos; Marianov, VladimirThe hierarchical network design problem consists of finding a minimum cost bilevel network that connects all the nodes in a set, created by a loopless main path and a forest. The main path is formed by primary (higher cost) arcs, providing a path between an origin node and a destination node. The forest, built using secondary (lower cost) arcs, connects all the nodes not on the main path, to the path itself. We state and prove some properties of the problem, which allow finding good upper bounds to the solution in polynomial time when the primary costs are proportional to secondary costs. We also propose an O(n(4)) procedure to improve on these bounds. In turn, these bounds are used to significantly reduce the number of nodes and arcs of the problem. Once the problem is reduced, large instances can be solved to optimality. At this stage, we use one of two linear integer optimization formulations. The first and preferred one is based on multicommodity flows, which avoids the formation of subtours. The second formulation avoids subtours by iteratively adding ad hoc constraints. We show some examples and provide computational experiments performed on networks with sizes up to 600 nodes and 14 000 arcs.
- ItemEmployee positioning and workload allocation(PERGAMON-ELSEVIER SCIENCE LTD, 2008) Eiselt, H. A.; Marianov, VladimirAssigning tasks to employees is a difficult task. Errors committed in such assignments can have far-reaching consequences, such as reduced efficiency due to absenteeism, lack of job satisfaction, formal grievances, and generally deteriorating labor relations. This paper approaches the problem from a spatial point of view. First, the employees and the relevant tasks are mapped in a skill space. After feasible task assignments are determined, tasks are assigned to employees so as to minimize employee-task distances in order to avoid boredom, and minimize disequity between the individual employees' workloads, and minimize costs. Computational results are provided for an engineering department of the Pontificia Universidad Catolica de Chile in Santiago, Chile. (C) 2006 Elsevier Ltd. All rights reserved.
- ItemFacility location for market capture when users rank facilities by shorter travel and waiting times(ELSEVIER, 2008) Marianov, Vladimir; Rios, Miguel; Icaza, Manuel JoseA firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand. (c) 2007 Elsevier B.V. All rights reserved.
- ItemLagrangean relaxation heuristics for the p-cable-trench problem(PERGAMON-ELSEVIER SCIENCE LTD, 2012) Marianov, Vladimir; Gutierrez Jarpa, Gabriel; Obreque, Carlos; Cornejo, OscarWe address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer - or demand - in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes. (C) 2011 Elsevier Ltd. All rights reserved.
- ItemLocation Problems in the Public Sector(2002) Marianov, Vladimir; Serra, Daniel
- ItemMedian Problems in Networks(2011) Marianov Kluge, Vladimir; Serra, Daniel; Eiselt, H. A.; Marianov, Vladimir
- ItemMinimum cost path location for maximum traffic capture(PERGAMON-ELSEVIER SCIENCE LTD, 2010) Gutierrez Jarpa, Gabriel; Donoso, Macarena; Obreque, Carlos; Marianov, VladimirA free path (with no preset extreme nodes) is located on a network, in such a way as to minimize the cost and maximize the traffic captured by the path. Traffic between a pair of nodes is captured if both nodes are visited by the path. Applications are the design of the route and locations of mailboxes for a local package delivery company, or the design of bus or subway lines, in which the shape of the route and the number of stops is determined by the solution of the optimization problem. The problem also applies to the design of an optical fiber network interconnecting WiFi antennas in a university campus. We propose two models and an exact solution method. Computational experience is presented for up to 300 nodes and 1772 arcs, as well as a practical case for the city of Concepcion, Chile. (C) 2009 Elsevier Ltd. All rights reserved.
- ItemMobile phone tower location for survival after natural disasters(ELSEVIER, 2012) Eiselt, H. A.; Marianov, VladimirThis paper discusses the location or strengthening of cell phone towers so as to maximize service coverage and minimize the loss of communications if a natural disaster happens. This paper demonstrates that, under a high likelihood of destruction of antennas (towers), the customary method of maximizing coverage provides poor solutions as compared to the proposed method. In addition to the maximization of service coverage, the objectives of our model include the minimization of expected and worst-case losses. The model is applied to a region in the south of Chile that was stricken by one of the most destructive earthquakes registered in history. Computational results are provided for a variety of scenarios. (C) 2011 Elsevier B.V. All rights reserved.
- ItemOptimal Capacity Expansion in Electric Power Subtransmission Networks(ASCE-AMER SOC CIVIL ENGINEERS, 2009) Tapia, Felipe; Marianov, Vladimir; Vargas, LuisA procedure is proposed to determine where and when to increase the capacity of lines and transformers in a power subtransmission network. The expansion plan must minimize cost while supplying the demand for energy over a time horizon, keeping the quality and reliability standards of the network and minimizing the impact over the environment. The procedure is iterative and takes into account AC flows, reliability analysis, different scenarios, demand uncertainty, discrete investment costs, voltage constraints, capacity, and power factor. A significant contribution of this procedure is that, along with the expansion plan, it considers the optimization of the operation, specifically the movement of transformer taps and the location and sizing of reactive banks. This allows significantly reducing or delaying the investment, thus reducing its present value. The approach ensures convergence when computing the power flows and allows making an analysis of the effects of distributed generation and, if necessary, load curtailment. The model is tested on the power subtransmission network of the most important electric power distribution company in Chile, serving a city of 6 million people.
- ItemOptimal design of hierarchical networks with free main path extremes(ELSEVIER SCIENCE BV, 2008) Obreque, Carlos; Marianov, Vladimir; Rios, MiguelWe propose an optimal, two-stage procedure for the optimal design of minimum cost hierarchical spanning networks, consisting of a main path and secondary trees. The optimal location of the origin and destination nodes of the path is also found. We test our procedure and compare it with a known method. (C) 2007 Elsevier B.V. All rights reserved.
- ItemOptimizing location and size of rural schools in Chile(WILEY-BLACKWELL, 2012) Araya, Fernando; Dell, Robert; Donoso, Pedro; Marianov, Vladimir; Martinez, Francisco; Weintraub, AndresThe Chilean Ministry of Education oversees preschool, primary, and secondary education in both urban and rural areas. Many parts of Chile are sparsely populated and there are currently over 4,000 rural schools (almost 38% of all schools in Chile) educating 9.5% of the students in the country. Many of the rural schools are small with only one teacher responsible for instruction of all local students (multigrade schools). The geographical distribution of the rural schools has not been coordinated and this has resulted in unequal utilization of existing schools and some unreasonably long travel distances by students. Good management of the rural schools is fundamental to meeting Chile's goal of providing quality education to its citizens. Seeking to improve the situation, the Ministry of Education ordered a study of the optimal location and size of rural schools with the general goals of reducing the number of lesser quality multigrade schools and reducing student travel distances while maintaining reasonable costs. This paper presents results of this study obtained using an integer linear program that has been embedded in a geographical information system. We present computational results for the entire country. Recommendations include where to open new rural schools as well as where to expand, reduce, close, or leave unchanged existing schools. We show how recommendations are sensitive to key parameters such as the cost of transportation.
- ItemSelecting compact habitat reserves for species with differential habitat size needs(PERGAMON-ELSEVIER SCIENCE LTD, 2008) Marianov, Vladimir; ReVelle, Charles; Snyder, StephanieWe propose a model for the design of protected habitat reserves, which maximizes the number of species represented at least once in a limited set of reserved sites or parcels. Most models for reserve design do not differentiate eligible habitat sites by their size. Also, they assume that protection is guaranteed through the selection of one site for any species, not taking into consideration that habitat needs vary from species to species. Our model acknowledges the fact that different species require reserves of different sizes, and that these reserves should be compact areas, as opposed to a set of disconnected parcels. Computational experience is shown on a landscape modeled as a regular grid, in which individual species require 1-, 2- or 4-parcel compact reserves. The results are compared to output from a Maximum Species Covering Model. (C) 2006 Elsevier Ltd. All rights reserved.
- ItemTransmitter location for maximum coverage and constructive-destructive interference management(PERGAMON-ELSEVIER SCIENCE LTD, 2012) Marianov, Vladimir; Eiselt, H. A.Covering location models consider a demand "covered" if there is at least one facility sited within a preset threshold distance. If more than one facility satisfies this criterion, it is implicitly assumed that one of these facilities - usually the closest - will serve the customer, while the remaining ones will have no relation to the demand. However, there are cases in which this multiple coverage has either synergetic or undesired effects. In digital television broadcast networks using Single Frequency Network transmissions, if a customer receives transmissions from more than one transmitter, the strongest transmitter is the main signal source, while the second and following transmitters can either contribute to a good reception or act as sources of interference, depending on the technology and their relative locations. In this case, facilities should be located so as to avoid overlapping coverage if there is interference, or enhancing overlapping coverage if signals are combined constructively. We propose models that are solved using a commercial software, that address this problem. One of these models is used to compare different alternatives of network design for a region in Chile, and to find the best coverage situations. (C) 2011 Elsevier Ltd. All rights reserved.