next day
all days

View: session overviewtalk overview

10:45-11:05Coffee Break
11:05-12:05 Session S1: Hub Location and Applications
Single-allocation hub location with upgraded connections

ABSTRACT. In this work we assume that there is a budget that can be invested in im- proving network connections, understanding that improving a connection can consist of activities as diverse as changing a vehicle for another with less fuel consumption or paying a small fee to avoid traffic jams or even paving a path. In this context, it is possible to solve the single hub location problem at the same time the set of connections to upgrade is decided. Two types of connections are distinguished, the connections between hubs and the connections between spokes and hubs and a quota is established for both values.

The Waste-to-Biomethane Logistic Problem
PRESENTER: Víctor Blanco

ABSTRACT. In this work, we study the Waste-to-Biomethane Logistic Problem, which consists of deciding the location of the different plants and pipelines involved in the transformation and distribution of biomethane, and the way the product is transported, minimizing the overall transportation cost with the given installation budget. This logistic system behind biogas production is complex, with different agents, different production and conversion technologies, and different types of demand centers. We provide a general and flexible family of mathematical optimization models to make decisions in locating biogas plants and distributing the different types of elements along a complex network.

The profit-oriented hub line location problem with elastic demand

ABSTRACT. The hub line location problem (HLLP) has relevant applications in public transportation planning design (tram, subways, express bus lane, etc.) and road network design. The aim of the HLLP is to locate $p$ hubs connected by a path that is composed by p-1 hub arcs in such a way that the total travel time of the origin-destination pairs is minimized. If the direct travel time between an origin-destination is smaller than any path using the line, the demand is routed without using the hub line. HLLP assumes that demand between each origin and destination can be a priori estimated and that the resulting constructed hub line network does not have any effect on the demand.

In this work, we extend the HLLP. Particularly, we introduce the profit-oriented hub line location problem with elastic demand (ED-HLLP). This model uses a gravity model to include the elasticity of demand. Gravity models have been previously used to model elastic demand in network design problems. The main goal of ED-HLLP is to maximize the revenue of the total time reduction provided by the hub line considering elastic demand. Thus, this new model takes into account the long-term impact on the demands that opening a hub line can have.

We propose different non-linear formulations to address this problem. The main difference between these formulations is the way in which the line structure is modeled. Besides, we introduce three main linear formulations. These linear formulations use the possible paths using the hub line as variables. Consequently, it is necessary to use a preprocessing phase that calculates the candidate paths for each origin-destination. For this preprocessing phase, we provide efficient algorithms to create all possible candidate paths. Finally, we also present a computational experience that evaluates the strengths and limits of these formulations for ED-HLLP.

12:10-13:10 Session S2: Discrete Location
Budget-constrained center upgrading in the p-center location problem: A math-heuristic approach

ABSTRACT. Recently, we have investigated different upgrading strategies in the context of the p-center problem (Anton-Sanchez et al. 2023). We focus on the so-called unweighted vertex-restricted p-center problem and consider the possibility of upgrading a set of connections to different centers as well as the possibility of upgrading entire centers, i.e., all connections made to them. In the aforementioned work, two variants for these perspectives are analyzed: in the first, there is a limit on the number of connections or centers that can be upgraded; in the second, an existing budget is assumed for the same purpose. We introduce different mixed-integer linear programming models for those problems (based on those previously proposed by Daskin (2013) and Calik and Tansel (2013)) and we show that, in most cases, an optimal solution can be obtained within an acceptable computing time using an off-the-shelf solver. Nevertheless, this is not the case for the budget-constrained center-upgrading model, i.e., when an exogenous budget is considered for upgrading centers. The aim of the work at hand is to present the development of a math-heuristic seeking high-quality feasible solutions in that specific case.

We propose a genetic algorithm for budget-constrained center upgrading, whose structure is as follows: once an initial population has been generated, crossover, mutation, and local search operators are carried out in all iterations until the stopping condition occurs. Furthermore, an intensified local search is performed in some iterations, which is ruled by some given probability. We have encoded the solutions in such a way that we only save the value of the p open centers. Hence, each individual is a combination of p centers from the candidates. We approximate the fitness of an individual (objective function value) by using a linear optimization model that provides a good upper bound on that value. Moreover, we try to improve this upper bound further by reallocating some demand nodes. As a consequence of the way the fitness of an individual is obtained, our genetic algorithm turns out to be a math-heuristic, in which the calculation of the fitness function is not trivial.

The results show that the math-heuristic finds good feasible solutions in a short time. For all instances, the results provided by the algorithm, even if they are not optimal solutions, provide hopefully good upper bounds for the problems.

The Induced Facility Location Problem with Upgrading

ABSTRACT. We consider a new model for facility location problems on graphs where two kinds of weights are associated with each edge, namely allocation and derived costs. The allocation cost is related to the cost of assigning the demand points to the facilities. The derived cost represents any cost derived of the allocation of the demand points. Each customer will be assigned to the facility providing the lowest allocation cost. Moreover, a budget is given to reduce the derived costs. The aim is to simultaneously find the location of facilities and the distribution of a budget in the edges of the graph to reduce the derived costs associated to the allocation of the demand nodes to the facilities, in order to minimize the upgraded derived costs.

Framework for Fairness Analysis in Location Problems

ABSTRACT. Ordered optimization allows a straightforward and flexible generalization for facility location problems since many well-known problems in the literature can be modeled using an ordered formulation. This is the case for median, center or centdian problems, but also, since negative and non-monotonous vectors of weights are allowed, of obnoxious location problems, modeling preferences or other abstract concepts such as, for example, envy. In the context of fairness theory, the ordered optimization can be used to create a common framework for the inclusion and analysis of the concept of equity in location problems, where compensation of allocation costs is based on the fact that a solution that is good for the system does not have to be acceptable for all single parties if their costs to reach the system are too high in comparison to other parties.

In this communication, we present new enhancements for the Discrete Ordered Median Problem (DOMP), a location problem where client-facility allocations are ranked, see \cite{ref1}. First, we review the current most competitive formulations in the literature and show how the DOMP can be used for the generalization of many facility location problems. We use a Benders decomposition approach to improve state-of-the-art results for a general criteria selection, see \cite{ref2}. We also describe how to include inter-facility connection to the DOMP by means of a minimum spanning tree, in order to present how to apply the DOMP as a framework for fairness analysis in connected facility problems as remark.

13:10-14:10Lunch at ICMS
14:10-15:10 Session S3: Covering Problems
A novel integrated approach for locating agricultural sensors based on the zoning and p-median problems
PRESENTER: Tiare Torres

ABSTRACT. Precision Agriculture (PA) is a very relevant field of study nowadays. Its objective is to increase efficiency, yields, productivity and, at the same time, reduce the environmental impact of usual agronomic practices in the agricultural industry through the use of technology and data analysis. Due to the benefits that the use of PA brings, many farmers decide to implement them, but due to the costs, they can only have access to a limited number of devices. Therefore, in this contribution we will develop an integrated approach for the management zone delineation problem and the discrete location of sensors problem to increase the representativeness of nonhomogeneous soil properties. The proposed model is solved using the integer programming solver Gurobi in Julia JuMP and computational results from a set of instances are presented to show the impact of the adopted methodology.

Some insights on the Conditional Value-at-Risk approach for the Maximal Covering Location Problem with an uncertain number of facilities
PRESENTER: Ricardo Gázquez

ABSTRACT. The maximal covering location problem (MCLP) lies in the area of Covering Problems which is a well-defined branch of Location Science \cite{GarciaMarin:2019}. In particular, the MCLP maximize the amount of demand covered within a maximal service distance by locating a fixed number of facilities \cite{ChurchReVelle1974}.

Many different approaches to the problem have been developed since its introduction, among them the MCLP with uncertainty. Uncertainty is usually assumed in aspects such as travel time (which would affect distance) or customer demands. Very few papers have worked with uncertainty in the number of facilities to be located (see e.g., \cite{uncertainty1,uncertainty2}).

In this talk, we focus in the MCLP with uncertainty on the number of facilities to be located and treat it as a two-stage problem. In the first stage, a decision has to be made on an initial set of facilities to locate; it is a here-and-now decision. In the second stage, a set of additional locations is selected, and we assume that the exact number of facilities to locate in the second stage is not known in advance---it corresponds to information that will be revealed at a future point in time, for example, based on a budget whose volume is not yet known.

This problem is useful in many applications such as telecommunication antennas and repeaters, in managing the location of cameras over a city and even in problems of electric vehicle charging stations, where cities are currently developing plans for the placement of the stations.

Finally, we model the problem using the Conditional Value-at-Risk (CVaR). This consists of minimizing a convex combination of the maximum regret with respect to a set of scenarios with jointly probability at least $\alpha$ and the expected regret with respect to the remainder scenarios~(see also, \cite{RockafellarUryasev:2000,RockafellarUryasev:2002})

We derive a mathematical programming model for the problem and derive some interesting conclusions on the obtained results, both on synthetic and real-world datasets.

Setting second-level facilities in the multi-product maximal covering location problem

ABSTRACT. In hierarchical facility location problems, the goal is to locate a set of interacting facilities at different levels of a hierarchical framework. In this context, we introduce a model which considers a first-level system of already established services (factories, product sources, etc.), a second-level system of facilities (warehouses, shops, etc.) to determine their location and their supply of products, and a third-level system of clients demanding different products produced in the first-level and provided by the second-level facilities.

Each client demands different products and has distinct preferences for the same product depending on the first-level facility producing that product. In this model, called multi-product maximal covering second-level facility location problem, there is a maximum number of different products that can be offered at each second-level facility and also a budget constraint for the total cost of the facility locations. % established high-level facilities (factories, product sources, etc.) and a set of clients with different product demands and with distinct preferences depending on the high-level facility providing the product.

The aim is to locate a set of second-level facilities and to decide the size of them (number of offered products), in such a way that the covered clients' demand is maximized. Therefore, in order to satisfy a customer's demand there must be a double coverage, the customer must be covered by a second-level facility, and this, in turn, by a first-level facility.

We propose a mixed integer linear program (MILP) for this problem which is reinforced by the use of valid inequalities. For cases where the number of valid inequalities is exponential, different separation procedures are developed. In addition, three variants of a heuristic algorithm are proposed. An extensive computational analysis is carried out. This illustrates the usefulness of the valid inequalities and the corresponding separation methods, as well as, shows the good performance of the proposed heuristic algorithms.

15:10-15:15Short Break
16:15-16:35Coffee Break
16:35-17:35 Session S4: Continuous Location
Planar location problems with uncertainty demand points: robustness concepts

ABSTRACT. Finding robust solutions to an optimization problem is an important issue in practice. Various concepts on how to define the robustness of an algorithm or of a solution have been suggested. In this paper, we apply several approaches of robust optimization to a broad class of planar location problems in which the coordinates of the demand points are uncertain. We furthermore present explicit examples and algorithms for planar center problems and compare their solutions for the different robustness concepts.

Touring polytopes, the weighted region and some related location problems
PRESENTER: Justo Puerto

ABSTRACT. In this paper we address two different related problems. We first study the problem of finding a simple shortest path in a $d$-dimensional real space subdivided in several polyhedra endowed with different $\ell_p$-norms. The second problem that we consider is the continuous single facility location or Weber problem that results in this subdivision of $\ell_p$-normed polyhedra. The first problem is a variant of the weighted region problem, a classical path problem in computational geometry introduced in Mitchell and Papadimitriou (JACM 38(1):18-73, 1991). As done in the literature for other geodesic path problems, we relate its local optimality condition with Snell's law and provide an extension of this law in our framework space. We propose a solution scheme based on the representation of the problem as a mixed-integer second order cone problem (MISOCP) using the $\ell_p$-norm modeling procedure given in Blanco et al. (Comput Optim Appl 58(3):563–595, 2014). We derive two different MISOCPs formulations, theoretically compare the lower bounds provided by their continuous relaxations, and propose a preprocessing scheme to improve their performance. The usefulness of this approach is validated through computational experiments. The formulations provided are flexible since some extensions of the problem can be handled by transforming the input data in a simple way. To solve the second problem, we adapt the solution scheme that we developed for the shortest path problem and validate our methodology with extensive computational experiments.

Exact Solution Methods for the p-Median Problem with Manhattan Distance and a River with Crossings
PRESENTER: Thomas Byrne

ABSTRACT. Rivers are a source of fresh, drinkable water, carrying and distributing important salts and nutrients. In supporting plant and animal life, rivers bestow a useful food source as well allow the use of irrigation, essential to food production. Vegetation that thrives around rivers facilitates lower air and surface temperatures by releasing moisture into the atmosphere and providing shade. Additionally, rivers are often crucial for transportation and commerce and more recently have been developed to produce electricity and to provide for leisure activities.

Not surprisingly, large population densities congregate around large rivers. While humans inhabit around 38% of the world’s surface area, humans inhabit over 40% of the area for which a river is the closest water feature. In fact, on average, the closest body of water to a human is a large river at a median distance of 2.2km.

However, in current facility location models, the pivotal influence on travel that a river exerts has not yet been adequately addressed. Despite providing such vital resources to a settlement to this day, rivers are usually impassable but for pre-constructed crossings and so present a very real barrier to anyone hoping to travel besides or to the other side of the river.

We propose a collection of exact solution methods for the p-median problem with Manhattan (l1) distance and a river, a problem we shall refer to as pMPL1(R,C) (where R and C represent the river and its crossing respectively). pMPL1(R,C) requires the locating of several facilities in order to minimise the total travelling distance from the given demand points to their nearest facility. For any route across the river, a crossing point is chosen from a given set of crossings so as to minimise the shortest paths where distance is measured using the Manhattan metric which, taking into account the grid structure prevalent in many cities’ transport infrastructure, is most representative when considering urban applications of facility location.

It is known that the 1-median problem with Manhattan distance is easily solved because its objective function is a piecewise linear function. For the p-median problem with Manhattan distance, a few heuristic algorithms have already been proposed. However, even for this well-known problem, effective algorithms to obtain its exact solution have not yet been studied. The objective function of pMPL1(R,C) is not convex and there are many local minima. Resorting to the existing heuristic methods risks obtaining not the exact solution but one of these local minima. A naïve solution method is to enumerate all the candidate points and to evaluate the objective function at each in order to find the solution. This, not surprisingly, is time-consuming. Instead, we construct a BTST algorithm for pMPL1(R,C) which obtains the exact solution in practical computational time. We compare our algorithm with the naïve enumeration method and show the effectiveness of our algorithm.