Model for Optimal Sectioning of Liquid Hydrocarbon Transportation Pipelines.
Crude oil and other liquid materials are transported in large quantities through pipelines. Pipelines are an efficient and safe transport way. Nevertheless, loss of containment (LOC) accidents may be caused by external actions of both operational and nonoperational nature. Consequences of LOC accidents in pipelines can be efficiently reduced through appropriate design of the general system by defining the installation of sectioning (or blocking) valves at adequate distances. Defining the location and number of valves in a specific pipeline section is a challenging decision due to the countless combinations of these two design components (i.e., where and how many valves). We address the valve location problem using a model for optimal sectioning which assesses the possible location of valves to minimize economic consequences. We present a case study for sectioning in a LatinAmerican pipeline, characterized by several changes in altimetry and the presence of urban and suburban populations. The results show reductions on the order of 10%18% of the total expected cost of economic consequences compared with the sectioning carried out under the current guidelines of pipeline design included in the CSA Z662 norm. The resulting valve configurations cover zones with different combinations of area and high consequence area types, reducing economical losses for both expected.
Contact: Sergio Cabrales
Public transportation systems: from demand estimation to route design
Bus rapid transit (BRT) systems such as TransMilenio (in Bogota) have become a real alternative to more expensive railbased public transportation systems. However, once the BRT system infrastructure is operational, its success often depends on the routes offered to the population. One of the challenges that planners face is the estimation of the origindestination (OD) matrix that is the key driver to the set of routes and frequencies that need to be offered to the population. This matrix captures how people move in the city from each origin to each destination throughout the day. The estimation of the OD matrix is challenged by the lack of complete information. In many BRT systems it is known where passengers board buses, but not where they leave the system. Based on a vast amount of (partial) data and the use of modern analytics techniques this research line is focused on estimating the OD matrix of public transportation systems. Once the OD matrix is estimated, the problem of finding a set of routes (services) and frequencies that minimizes the operational and passenger costs (travel time) while simultaneously satisfying the system’s technical constraints (e.g., demands for trips, bus frequencies, and lane capacities). Our approach to the problem is based on a mathematical formulation that exploits the underlying network structure. However, because of the vast number of routes, solving the problem directly is out of reach for most practical instances. Thus, our approach is based on decomposition strategies (e.g., simultaneous columnandrow generation and matheuristics) that break the problem into manageable parts.

Photo by mariordo59/ CC BYSA 2.0


Contact: Andrés L. Medaglia
Related work::
 Walteros, J. L., Medaglia, A. L., and Riaño, G. (2015). Hybrid algorithm for route design on bus rapid transit systems. Transportation Science. 49(1):6684.
 Feillet, D., Gendreau, M., Medaglia, A. L., Walteros, J. L. (2010). A note on branchandcutandprice. Operations Research Letters. 38(5):346353.
The pulse algorithm: a building block for network optimization
There are a vast amount of tactical and operational problems in transportation and logistics systems that rely on solving shortest paths (and variants) as a building block. The pulse algorithm can be seen as a general framework that can be extended to solve a wide range of routing problems. The idea behind the pulse algorithm is very simple, almost naive. The algorithm is based on the idea of recursively propagating pulses through a network from a start node to an end node. As a pulse traverses the network from node to node, it builds a partial path including the nodes already visited and some attributes associated with that path, such as the cumulative cost or resource consumption. Each pulse that reaches the final node contains all the information for a feasible path from the start to the end node. If nothing prevents the pulses from propagating, the algorithm completely enumerates all possible paths, ensuring that the optimal path is always found. At the core of the algorithm lies the ability to (effectively and aggressively) prune pulses as soon as there is enough evidence that the partial path will not lead to a feasible or improved solution. We have developed variants of the pulse algorithm to solve the Constrained Shortest Path Problem (CSP), the Elementary Shortest Path Problem with Resource Constraints (ESPPRC), the Biobjective Shortest Path Problem (BSP), the Orienteering Problem with Time Windows (OPTW), the Weight Constrained Shortest Path Problem with Replenishment (WCSPPR), and a variant of the Robust Shortest Path Problem. Also, the pulse algorithm has been used as a module to solve more complex transportation and logistics problems such as the Multiactivity Shift Scheduling Problem and the Bus Rapid Transit Route Design Problem. Other authors have applied it to variants of routing problems for electric vehicles and interdiction problems.

Photo by sjcockell/ CC BY

Contact: Andrés L. Medaglia
Related work::
 Lozano, L., Duque, D., and Medaglia, A. L. (2016). An exact algorithm for the elementary shortest path problem with resource constraints. Transportation Science. 50(1):348–357.
 Duque, D., Lozano, L. and Medaglia, A. L. (2015). An exact method for the biobjective shortest path problem for largescale road networks. European Journal of Operational Research. 242:788797.
 Duque, D., Lozano, L. and Medaglia, A. L. (2015). Solving the Orienteering Problem with Time Windows via the Pulse Framework. Computers & Operations Research. 54:168176.
 Bolívar, M. A., Lozano, L. and Medaglia, A. L. (2014). Acceleration Strategies for the Weight Constrained Shortest Path Problem with Replenishment. Optimization Letters. 8(8): 21552172.
 Lozano, L. and Medaglia, A. L. (2013). On an exact method for the constrained shortest path problem. Computers & Operations Research. 40 (1):378384.
 Restrepo, M. I., Lozano, L., and Medaglia, A. L. (2012). Constrained networkbased column generation for the multiactivity shift scheduling problem. International Journal of Production Economics. 140(1):466472
Modeling the evacuation dynamics under congestion

A key aspect related to network design, is estimating how a given system is going to perform under stress or an undesired event. We have worked on models that are able to evaluate the evacuation dynamics in a network of interconnected facilities (e.g., buildings). By using a macroscopic approach, a network optimization model determines the optimal evacuation paths under a rational behavior of the evacuees and without taking into account network congestion. Because this is overly optimistic, an (stochastic) microscopic approach incorporates congestion and the erratic behavior of the evacuees. By feeding back both models, a mesoscopic model is able to estimate evaluation times and identify bottlenecks that cause critical congestion during an evacuation. With this information, it is now possible to identify investment plans that make the network more robust and efficient in terms of disaster or shock.

Contact: Andrés L. Medaglia and Jorge A. Huertas
Locationallocation models for wildfire preparedness
A problem setting where strategic network design is of foremost importance, is the preparedness for wildfire events. Once a wildfire starts, prepositioned resources (e.g., tools) are delivered to operation centers where tactical decisions are made by firefighters. One of the key drivers for allocating the resources are the fire ignition points and the fire spread, which are stochastic in nature. By using simulated scenarios and a twostage stochastic program, we have been able to decide upon strategic decisions related to locating facilities and their inventory levels; along with the tactical transportation and distribution decisions within a timespace network that allows for realistic size problems such as those arising in Bogotá.

Photo by usfwshq / CC BY

Contact: Andrés L. Medaglia and Camilo Gómez
Building resilient and robust networks for efficient response
At a strategic level, optimizing the resilience of any given system requires optimizing decisions for diminishing vulnerability and increasing efficient response. We have worked on devising a comprehensive optimization framework that incorporates resilience and uncertainty of interconnected networks. The methodologies devised in this line of research help decision makers to plan where to invest in the networks (e.g., road network, supply chain, gas network, power network), so that after an uncertain and shocking (e.g., disaster or lowdemand) event, the system is able to recover and perform well as early as possible.


Contact: Andrés L. Medaglia
Related work:
González, A., DueñasOsorio, L., SánchezSilva, M., and Medaglia, A. L. (2016). The interdependent network design problem for optimal infrastructure system restoration. ComputerAided Civil and Infrastructure Engineering. 31(5):334–350.