ABSTRACT. In this presentation I will present a network design model which is employed to obtain the minimum set-up and operational cost hydrogen refuelling infrastructure. The network design model takes into consideration both facility location and hydrogen supply decisions. More specifically, the model must determine where to locate hydrogen refuelling stations and how the hydrogen must be supplied to each refuelling station. For the supply of hydrogen we consider local hydrogen supply and off-site hydrogen supply. In the latter case the hydrogen must be distributed to the refuelling stations by means of tube trailers or a hydrogen pipeline. The three supply modes (localised production, tube trailer, and pipelines), result in model solutions that take on a forest-stars-points topology. More specifically, the hydrogen refuelling stations connected to the hydrogen pipeline will resemble a forest of directed trees rooted at hydrogen pipeline supply points, while the hydrogen refuelling stations supplied by tube trailers will resemble a set of stars centered around the centralised production facilities and, finally, the hydrogen refuelling stations which have localised hydrogen production will resemble a set of isolated points. The difficulty of solving the network design problem arises from the hydrogen pipeline routing decisions which will be the focus of the presentation. More specifically, I will present three different formulations and two different cutting plane algorithms to solve this problem. We then compare each of the formulations and solution algorithms in a preliminary computational study where we found that the classical flow formulation with a set of valid inequalities is the most efficient. Finally, I will present a real-life case study in the north of England where we found that allowing hydrogen to be delivered by pipelines made a significant improvement in the objective function.

ABSTRACT. With millions of pounds involved in the construction of offshore wind turbines, there is need to optimize the whole process as to reduce the cost and duration of the final process involved in wind energy generation. Specifically, this project focuses on the derivation of mixed integer linear programming formulations for the installation procedure of offshore wind turbines and then uses exact methods to solve those models. However, we devise a shortest path-like formulations using strong multicommodity flow models of the network. We propose a polyhedral analysis of the set of solutions by identifying novel problem-specific valid inequalities require in the characterization of the convex hull of feasible solutions. Also we design an efficient cutting plane algorithm that identifies the optimal configuration of vessel schedules in order to minimize the installation duration and cost. We present preliminary computational results on the problem specific and the literature instances that are related to the problem formulation. Our method efficiency shall be tested and compared to most of the generated instances in the literature and real word data as well as those related to the subject matter.

ABSTRACT. This paper deals with the determination of optimal locations for pipelines and cable trays in naval design. The problem consists of finding the number and types of cable tray routes to be created between various devices in order to minimize a user defined cost function. We reduce the problem to an \emph{ad hoc} min-cost multicommodity flow problem with additional constraints imposed by technical requirements. This problem is solved for small-sized instances by using off-the-shelf optimization solvers. We also develop an exact relax-and-cut strategy that allows to handle medium-sized instances. For larger instances, we propose a family of heuristic algorithms consisting on the combination of two phases: I) Construction of initial cable trays paths; and II) Transformation to feasible cable trays verifying the technical requirements. For each of them, we also propose different strategies which give rise to several algorithms. These algorithms are compared on a computational experience using two types of instances: the first one based on random instances of different sizes and the second one based on instances with well-defined corridors to asses the availability of our methodology to enforce the creation of cable trays. Finally, we also analyze a real size case study provided by our industrial partner, Ghenova, a leading Naval Engineering company, validating our proposal to find solutions for this problem.

ABSTRACT. Today, Scanning Transmission Electron Microscopy plays an important role in designing nanomaterials to be used in the development of different fields, such as green energy sources, catalysis and environmental protection. The Electron Tomography procedure involves a three-stage process: recording the original sample using an electron microscope; reconstructing the object under study from the information provided by the first stage; and segmenting the images before or after they are reconstructed.

The discrete ordered median problem presents an application in electron tomography image segmentations. The adaptability of this problem to the different instances achieves high-quality image segmentations. However, the solutions provided by the discrete ordered median problem for large scale instances are obtained in high computing times. Image size is of great importance in electron tomography experiments, since the larger the image size, the higher the quality of the image. Therefore, applying this problem to images constituted by a large number of intensities could be impractical for electron tomography experiments due to the large number of images to be segmented.

With the goal of reducing the computation times, this work introduces different heuristic procedures to obtain feasible solutions for the ordered median problem that provide high-quality images in low computing times. Moreover, some noticeable improvements of the heuristic techniques are developed taking advantage of the particular versions of the ordered median function that have been proven to be especially suitable in the electron tomography image segmentation.

ABSTRACT. This work deals with the problem of partitioning a graph into $p$ connected components by optimizing some balancing objective functions related to the vertex weights. Objective functions based on the gap or range of the partition's components, i.e., the difference between the maximum and minimum weight of a vertex in the component, have been already introduced in the literature. Here we introduce the notion of aggregated gap, defined as the sum of the differences between the weights of the vertices and the minimum weight of a vertex in the component. We study new connected $p$-partitioning problems whose objective is a function of the components' aggregated gap, and prove that these problems are NP-hard on general graphs. Mathematical programming formulations are proposed for these problems adopting flow-based constraints for modeling connectivity in a partition. Such formulations are rather general and apply also to the classical non-aggregated gap problems. Extensive computational results, both for aggregated and non-aggregated gap problems, are performed on a set of squared grids and randomly generated graphs with up to 120 vertices, and a number of components ranging from 2 to 9. In our experiments, we test several alternative formulations for our problems providing a comparative analysis of their performance.

ABSTRACT. The minimum and maximum cuts of an undirected edge-weighted graph are classic problems in graph theory. While the Min-Cut Problem can be solved in $P$, the Max-Cut Problem is NP-Complete. Exact and heuristic methods have been developed for solving them. For both problems, we introduce a natural extension in which cutting an edge induces a cost. Our goal is to find a cut such that minimises the sum of the cut weights but, at the same time, it restricts its total cut cost to a given budget. We prove that both restricted problems are NP-Complete and we also study some properties. Finally, we develop exact algorithms to solve both and also a non-exact algorithm for the min-cut case based on a Lagreangean relaxation that provides most of the times optimal solutions. Their performance is reported by an extensive computational experience.

ABSTRACT. This paper deals with the k-way normalized cut problem in networks. The normalized cut function was defined to solve some issues concerning the interpretability of the minimum cut problem, which is a classical problem in graph theory whose aim is to provide the bipartition that minimizes the number of edges between nodes from different subsets, applied to partitioning and districting problems. Instead of considering just the number of external edges of each subset, the minimum k-way normalized cut problem tries to minimize the external edge density of each subset of a k-partition, also considering the number of internal edges. In addition, the problem can be extended to a weighted graph in order to minimize the sum of external weight density of the subsets. The minimum k-way normalized cut allows us to locate groups of nodes that accumulate a high internal weight density. Considering that these weights can represent a large number of different interesting parameters, this organization is really useful as facility location planning in order to locate in each of the clusters a facility that accumulates a high weight density. We show several applications of the minimum k-way normalized problem to facility location. We present a methodology using mathematical optimization to provide mixed integer linear programming formulations for the problem. The paper also develops a branch-and-price algorithm for the above mentioned problem which scales better than the compact formulations. Extensive computational experiments assess the usefulness of these methods to solve the k-way normalized cut problem over different location problems on large graphs and random graphs. In addition, all methods have been analysed and studied in order to try to improve them as much as possible.

ABSTRACT. Unlike ground vehicle routing problems, drone routing problems are characterized by the fact that drones can enter and leave the edges at any point and serve only part of them. Therefore, the service of an edge can be shared by several drones, making an already difficult problem much harder. As in previous works, we approach the problem by adding a set of intermediate points to each original edge, obtaining then a classic arc routing problem where a set of given edges must be traversed. In the Min Max Multi-Trip Location Arc Routing Problem (MM-MT-LARP), we consider a depot from which a set of P trucks, each one carrying a drone, must travel to P out of D available points (D <= P), where the drone is launched. Each drone has a limited autonomy which allows it to fly a maximum time L before having to get back to the launching point to change its battery so that it can start another route. Once the drone has completed all its routes, the truck goes back to the depot. The goal of the MM-MT-LARP is to determine the launching point for each truck and find a set of drone routes for each truck, each one starting and ending at its launching point and with flight time not greater than L, in such a way that all the drones’ routes jointly traverse all the given edges and the largest total time of all the trucks (time of traveling to the launching point, flight time of the drone and time of traveling back to the depot) is minimized. In this talk, we present an integer linear programming formulation and a metaheuristic algorithm for the MM-MT-LARP, as well as some preliminary computational results on a set of instances with different characteristics.

ABSTRACT. In this work we study Capacitated Prize-collecting Location Routing Problems (CPLRPs) on trees.

Introduction

In CPLRPs there is a set of users with demand, located at the vertices of a tree, each of which is associated with a profit, and each edge has a cost. To serve the demand a set of routes must be set up, each of them starting and ending at a open node. The activation of a node has an associated cost. In addition, each node has a capacity that must not be exceeded by the demand of the nodes associated with the route that starts from that node.

The objective is to maximize the total net profit, defined as the total income from service to the selected demand vertices, minus the total cost that includes the overall set-up cost of activated facilities plus the routing cost of the edges used in the routes.

Results

For the uncapacitated problem, a mathematical programming formulation is presented, which has the integrality property. The formulation models a directed forest where each connected component hosts at least one open facility, which becomes the root of the component.

For the capacitated version, an extensive computational study has been carried out to test the performance of some Lagrangian relaxation.

ABSTRACT. Recent advancements in drone technology have made it possible for these aerial vehicles to have the capability of capturing images and making deliveries during the same flight. This capability has many applications, such as in humanitarian emergencies, where drones can deliver medications to hard-to-reach areas and capture images of disaster-affected zones. However, the payload capacity of drones is still quite limited, and the weight of the cargo being transported significantly impacts energy consumption and flight times. In this talk, we present the Load-Dependent drone General Routing Problem (LDdGRP), where a drone must traverse a set of edges and make a certain delivery at some vertices of a graph. The goal is to minimize the total duration of the drone route while accounting for the effect of the load carried by the drone on the traversal time of the edges. We propose a formulation for this problem and conduct an analysis of the associated polyhedron of solutions, while introducing families of valid inequalities to strengthen the formulation. We design a branch-and-cut algorithm to solve the problem and perform extensive computational tests on instances with a maximum of 7 deliveries and 96 edges to be traversed.

ABSTRACT. This work deals with two different route design problems in a continuous space with neighbours and barriers: the shortest path and the travelling salesman problems with neighbours and barriers. Each one of these two elements, neighbours and barriers, makes the problems harder than their standard counterparts. Therefore, mixing both together results in a new challenging problem that, as far as we know, has not been addressed before but that has applications for inspection and surveillance activities and the delivery industry assuming uniformly distributed demand in some regions. We provide exact mathematical programming formulations for both problems assuming polygonal barriers and neighbours that are second-order cone (SOC) representable. These hypotheses give rise to mixed integer SOC formulations that we preprocess and strengthen with valid inequalities. The work also reports computational experiments showing that our exact method can solve instances with 75 neighbourhoods and a range between 125-145 barriers.

ABSTRACT. The use of conic structures in mathematical optimization problems has been widely recognized within the last few years. The development of interior point methods with specialized barriers has given room to efficiently solve problems involving cones with high practical interest. The incorporation of exact techniques to solve problems involving cones in different off-the-shelf optimization solvers has allowed practitioners to use these tools to make decisions in different fields. This is the case of continuous facility location, machine learning, power flow, radiotherapy, portfolio selection, and geometric programming, among many others. Thus, a lot of theoretical results have emerged to understand the geometry of different representations of cones. In this paper, we analyze a general type of power cone, the (α,p)-power cone. This cone has in particular cases the p-order cone and the power cone, and its efficient representation into an optimization problem allows to solve tons of problems that appear in different fields, particularly in continuous location problems. An extended representation of a set is an equivalent reformulation of the set through the inclusion of the set in a higher dimensional space and its after-transformation as a product of simpler sets. In this paper, we derive different extended representations of any (α,p)-power cone by means of simpler power cones and study its complexity. In case α is a rational vector and p is a rational number, we provide extended representations of the cone as 3-dimensional rotated quadratic cones. The main advantage of these simpler cones is that they are efficiently handled by most of the off-the-shelf optimization solvers. We show that a naive representation is highly inefficient compared to a guided representation, and provide bounds for the complexity of the representations in terms of α and p.

ABSTRACT. The aim of this study is to contribute to the literature of competitive delocation by addressing the problem faced by a large firm (the leader) who tries to reduce its network by closing a predefined number of facilities, on the knowledge that his competitor (the follower) -who is also engaged in a restructuring process- will react strategically to his actions. An important contribution of this study is the introduction of a novel notion of loyalty: the loyalty radius. This notion, presumes that certain customers will still be willing to visit a facility of their favorite provider, despite the fact that a competitor's facility may be located at a shorter distance, provided that the open facility is located within certain admissible distance.

The problem is modelled as a bi-level competitive delocation model and is formulated as a variant of the well-known $(r|p)$-centroid problem. These type of problems are complex to solve. For instance, even in the simplest form where both levels are linear programs, \cite{jeroslow1985polynomial} demonstrates that the bi-level problem is NP-hard. In our case, we consider a binary-binary linear bi-level problem.

Two exact methods are used: a proposed depth-first search implicit enumeration algorithm based on the ideas given in \cite{bard1992algorithm} and a generic solver of mixed-integer linear bi-level programming problems presented in \cite{fischetti2017new}. Additionally, two metaheuristics are developed: a nested GRASP algorithm and a nested hybrid GRASP-tabu search algorithm.

The four algorithms are used for solving a diverse set of instances of the problem. The analysis of an instance based on a real-life-setting, and intensive numerical experimentation, provide evidence on the effectiveness of the algorithms for the solution of real-size problems, and confirm the practical validity of our modelling approach. Our results also highlight the importance of taking into account spatial loyalty in network restructuring scenarios. It is noteworthy to emphasize that both metaheuristic algorithm obtain the optimal solution of the problem in less computational time. Its effectiveness and efficiency has been proven by the extensive computional experimentation conducted.

The numerical results highlight the importance of taking into consideration customers' behaviour, in particular loyalty, when engaging in restructuring processes. The main conclusion is that whereas in absence of loyalty restructuring efforts tend to benefit the leader, the existence of loyalty changes the balance, and the follower seems to be able to capture a larger segment of the market. Additionally, our results suggest that acknowledging the existence of loyalty in the planning process tends to bring larger benefits to the follower, who seems to be able to better adapt his/her restructuring strategy.

ABSTRACT. In recent years, there has been a significant increase in the outsourcing of various practices. This trend has been particularly prominent in the logistics sector, where it encompasses activities like last-mile delivery and full integration with external operators, including 3-PL logistics partners. Similarly, the airline industry has also experienced outsourcing in processes such as check-in, luggage management, cabin crew and even flights, among others. The outsourcing of these processes offers several advantages, including enhanced flexibility and a reduced dependency on hiring and training specialized staff. Given the increasing prevalence of this trend, it is crucial to study and model this type of situations from a network design perspective to gain a better understanding of how the outsourcing decisions contributes to the overall revenue of a major firm when it faces such a process. It is equally important to consider the companies' viewpoint as they too aim to optimize their revenues. The objective of this research is to address the transportation of demand between different origins and destinations (commodities) when the major firm, referred to as the Leader, already possesses a hub network of major hubs and chooses to outsource the demands coming from and going to the remaining non-hub locations using third-party companies (carriers) in order to maximize its overall profit. We model this problem as a Bi-Level Mixed Integer Non-Linear Programming (MINLP) model, which we subsequently linearize to obtain a Bi-Level Mixed Integer Linear Programming (MILP) formulation. Leveraging the inherent properties associated with the independency of assignments and costs of each carrier, we discretize the outsourcing cost decisions, enabling us to express the model as a Single-Level MILP. The costs and solutions derived from solving this model are shown to be bi-level optimal. Computational results demonstrate that we are able to solve instances of 200 nodes and 6 carriers to optimality within one hour. These findings provide motivation for studying more complex systems in the future.