ALIO/EURO 2021-2022: XTH JOINT ALIO/EURO INTERNATIONAL CONFERENCE ON APPLIED COMBINATORIAL OPTIMIZATION
PROGRAM FOR WEDNESDAY, APRIL 13TH
Days:
previous day
all days

View: session overviewtalk overview

09:00-10:30 Session WA1
09:00
Crowd-shipping: An Open VRP Variant with Stochastic Destinations
PRESENTER: Michel Gendreau

ABSTRACT. We consider a problem setting in which a Crowd-Shipping Platform (CSP) must deliver heterogeneous packages to customers from a central depot over a wide geographic area using a fleet of professional vehicles and a pool of Occasional Drivers (OD). We define a two-stage stochastic model with recourse, which is solved exactly through a Branch-and-Price approach. The cost of each route considered includes a cost associated with the risk that the route will not be completed by an OD. Computational results are reported for instances having between 25 and 100 customers.

09:22
Integer programs for a simultaneous vehicle routing and crew scheduling problem
PRESENTER: Mauro Lucci

ABSTRACT. In this work, we present two IP formulations for a simultaneous vehicle routing and crew scheduling problem, involving pickup-and-delivery requests with multiple time windows. Crews are composed of 1 or 2 drivers and any of them can descend in specific locations to rest or change trucks, which offers more planning options but creates a high interdependence. We perform tests on instances of up to 8 requests and a planning horizon of 1 week, obtaining that one of the formulations outperforms the other. These results are improved when a heuristic that provides an initial solution is used.

09:44
A Branch-Cut-and-Price Algorithm for the Time-Dependent Electric Vehicle Routing Problem with Time Windows

ABSTRACT. The adoption of electric vehicles (EVs) within last-mile deliveries is considered one of the key transformations towards more sustainable logistics. The inclusion of EVs introduces new operational constraints to the models such as a restricted driving range and the possibility to perform recharges in-route. The discharge of the typical batteries is complex and depends on several variables, including the vehicle travel speed, but most of the approaches assume that the energy consumption depends only on the distance traveled. This becomes relevant for distribution problems in large cities, where traffic congestion affects severely the travel speeds. In this paper, we introduce a general version of the Time-Dependent Electric Vehicle Routing Problem with Time Windows (TDEVRPTW), which incorporates the time-dependent nature of the transportation network both in terms of travel times and the battery consumption. We propose a unifying framework to integrate other critical time-dependent times arising during the operations previously studied in the literature, such as the waiting and charging times. We propose a state of the art branch-cut-and-price (BCP) algorithm. Based on extensive computational experiments, we show that the approach is very effective solving instances with up to 100 customers with different time dependent contexts and, although being more general, its performance is comparable with specifici algorithms for time-independent instances. From a managerial standpoint, our experiments indicate that neglecting the travel speeds can affect the quality of the solutions obtained, where up to 40 percent of the infeasibilities induced by neglecting the time dependency can be caused by exceeding the battery capacity.

10:06
An Enhanced Branch-and-Price Algorithm for the Vehicle Routing Problem with Time Windows over Road Networks

ABSTRACT. Classical Vehicle Routing Problem (VRP) variants are usually modeled through the so-called customer graph. The problem is formulated over a complete graph, where the vertices represent the set of requests and the depot and the set of arcs models the movement of a vehicle between two given customers. However, modelling the VRPs directly through the customer graph can show some limitations from a practical perspective. In some contexts, the path between two customers is affected by more than one metric,often opposing, such as the travel time and the cost of the route. In this paper we study the VRP with Time Windows over a Road Network (VRPTW-RN), a variant of the VRPTW where the vehicles are allowed to move only through the underlying network, composed of both customer vertices as well as non-customer nodes representing the connection between two relevant paths. We propose an enhanced Branch-and-Price algorithm, incorporating an improved bidirectional labeling algorithm as well as a new branching rule within the context of VRPs with intermediate stops. From our computational experiments, we observe a significant reduction in the computation times when compared to the other exact approach from the related literature.

09:00-10:30 Session WA2
09:00
On the distribution of nutritional status transition probabilities through a hierarchical beta mixture model

ABSTRACT. This work addresses the problem of estimating the probability density function for each nutritional status considering the sex and the kind of transition a person suffers between two consecutive periods. To this end, an optimization scheme is proposed based on a hierarchical model considering previously known information as input to estimate mixture densities through the expectation maximization algorithm. Besides, a goodness-of-fit metric is shown based on the shared area of the actual density obtained from a Dirichlet distribution and its close relation with the Beta distribution. Thus, several experiments are performed showing a goodness-of-fit of 93.1%, at least.

09:22
Decomposition Algorithms for Energy Management under Uncertain Generation
PRESENTER: Helena García

ABSTRACT. Due to climate change concerns, many governments have pushed for higher penetration of variable and intermittent renewable energy sources. Among these energy sources, photovoltaic (PV) generation is one of the most sought off, in particular by domiciliary users and small companies. The main drawback of this source of energy is its variability and not being available for the whole day. One way of canceling or diminishing this drawback is to use energy storage systems, like batteries. Although storage systems are currently expensive, its price has dropped significantly in the last decade and many studies indicate that they will become an economically viable alternative in the coming years.

In this work, we present a novel approach to schedule the use of these storage units in a PV generation system, based on stochastic optimization. Using real historical data, we analyze different methods for generating scenarios for our optimization model, we also develop decomposition methodologies in systems with limited computation, showing that the resulting decision support system improves current scheduling policies significantly. We further validate our results by testing the resulting schedules in a real prototype.

09:44
Using Lagrangean Decomposition for computing improved RLT bounds for some quadratic 0-1 optimization problems with linear constraints

ABSTRACT. The RLT method of Adams and Sherali essentially transforms a combinatorial optimization problem with a quadratic objective function and linear constraints into a linear optimization model of significantly larger size. One advantage of the transformation is that, ignoring the remaining 0-1 restrictions on the variables, it can transform a nonconvex quadratic objective function into a linear one. The main tool consists in defining new variables that are products of two binary variables, for instance, given binary variables xi and xj, they introduce variable yij = xi.xj and subsequently replace all instances of the product xi.xj by yij, and xj.xi by yji. This process linearizes the objective function, and the model becomes a 0-1 linear programming problem, however of a much larger size. The model is strengthened by multiplying the linear constraints by all x variables in turn and substituting variables yij wherever the product xi.xj appears. We showed that a specific Lagrangean relaxation (LR) of an RLT formulation for certain pure 0-1 quadratic models with linear constraints, coupled with the Integer Linearization Property (ILP), can produce decomposable models and improved bounds, and much reduced computation time compared with the standard RLT approach, rendering the approach usable for much larger instances than reported earlier. Yet, in order to produce a decomposable model, that relaxation required the dualization of only one (either one) out of two important symmetric subsets of RLT constraints in order to avoid overlapping index sets, as this would prevent the relaxed model from being decomposable. The symmetry arises from the fact that obviously xi.xj is equal to xj.xi and yij should be equal to yji . Yet adding these constraints would destroy the decomposability of the model, as index sets would be overlapping. There is however another way of exploiting the symmetry of these original sets of constraints, without ignoring half of them, and that may yield even stronger bounds than those obtained. At the cost of increasing the computation time relative to LR, Lagrangean decomposition LD will construct two subproblems, each containing one of these two sets of constraints, after splitting the original variables yij, into two, vij and wji, and dualizing the symmetry constraints that they should be identical, i.e., vij = wji. In short, constraints such as Ay <= b become Av <= b and Awt <= b, after variable y has been replaced respectively by v and w, and the constraint v = wt has been dualized. One must then solve two similar but independent subproblems, one in v and one in w. If neither of these subproblems has the integrality property, then the Lagrangean decomposition bound can be strictly better than the original LR bounds. We will present results for the GQAP (Generalized Quadratic Assignment Problem) and the QKP (Quadratic Knapsack Problem), two of the models considered.

10:06
Forestry: managing economies of scale

ABSTRACT. We present a model that incorporates economies of scale (EoS) in forestry: finding optimal multiperiod harvesting schedule for forests divided into stands, maximizing the net yield. Decisions are the stands to be harvested in each period; Among others, the constraints are maximum variation of timber between periods, harvesting capacity and demand. Since a relevant cost is the harvesting operation setting up, stands’ adjacency can be considered to obtain savings (EoS) if 2 or 3 adjacent stands are harvested in the same period. A powerful visualization scheme to analyze the results is presented.

10:30-11:00Coffee Break
11:00-12:00 Session WB1: Plenary Talk
11:00
Mathematical optimization for social network analysis: The impact of passive users in influence maximization

ABSTRACT. Online social networks have evolved to crucial communication channels used by different stakeholders such as individuals, companies, or political parties. They are commonly used in online marketing campaigns that can be considerably more effective than traditional ones. Such campaigns can heavily benefit from quantitative analysis leading to a profound knowledge of the dynamics of online social networks. Fundamental problems that arise in this context include the identification of influential network nodes that may trigger a large information propagation cascade and the identification of (homogeneous) communities. In this talk, we focus on the former class of problems which are often referred to as influence maximization problems and typically aim to maximize the (expected) number of reached network participants. We will first provide an overview over problem variants considered in the literature and recently proposed algorithms based on mathematical programming. In the second part of the talk, we focus on several, recently introduced extensions. These include alternative objective functions and the (explicit) consideration of passive users who view but do not forward content. We introduce a mixed-integer non-linear programming formulation that incorporates these aspects and an exact linearization for the latter based on generalized Benders decomposition. Finally, we report results from a computational study showing that the new problem variants can lead to more effective marketing campaigns and discuss topics for future research.

12:00-13:50 Session WC1
12:00
Location of Primary Health Care Units in Multi-Institutional Health Care System

ABSTRACT. In this work, we address the problem of locating and upgrading primary health care units (HCUs) within a multi-institutional public system. This problem consists of the allocation of demand to HCUs of multiple institutions, the location of additional capacity in current HCUs, and the location of new HCUs to minimize the total traveled distance (TTD) by people from the demand points to HCUs. In this scheme, each institution has its demand and HCUs, but some level of capacity can be shared among them to enlarge the overall capacity of the system. The number of kernels is used in the problem to determine the capacity of an HCU. This basic unit of capacity determines the amount of demand that can be covered by a medical staff team (doctor, nurses, and technicians). This problem is motivated by a real-world application in the Mexican Health Care System, and a novel integer programming model was introduced for providing a more efficient regionalization of the resources.

12:22
Solving the latency location routing problem with hybrid metaheuristics
PRESENTER: Alan Osorio-Mora

ABSTRACT. This paper presents an hybrid metaheuristic to solve the Latency Location Routing Problem (LLRP). The LLRP is an NP-hard problem which combines two combinatorial-optimization problems: the Cumulative Capacitated Vehicle Routing Problem (CCVRP)  and the Facility Location Problem (FLP). The LLRP consists of determining the location of at most Nf facilities, and the routes that Nv homogeneous vehicles must perform, with the aim of minimizing the sum of the arrival times at the customers (latency). This kind of problem is appropriate for modeling customer-centric problems, in which the customer satisfaction is more important than the economic issues. Some examples are the post-disaster operations, humanitarian logistics, perishable food transportation, and home health care logistics. The LLRP was introduced recently, and can be considered as a relative new trend in the location routing field. The authors proposed a mixed-integer linear programming formulation to model the problem, and solved the LLRP using a memetic algorithm and a recursive granular algorithm.

In this talk we propose an algorithm which combines simulated annealing with variable neighborhood search (VNS) procedures to solve the problem. While the simulated annealing process is used as a diversification strategy, the VNS procedure is applied as an intensification stage. Extensive computational experiments on 76 LLRP benchmark instances were performed. The results show that the proposed methodology is competitive with the state of the art algorithms both in terms of computing time andsolution quality. The hybrid algorithms are able to udpate the best known solution for the majority of the instances in the benchmark dataset.

12:44
An exact algorithm for districting with p-center-based dispersion minimization
PRESENTER: Roger Z. Ríos

ABSTRACT. We present an exact solution method based for a districting problem with balancing and connectivity constraints with the objective of minimizing a p-center dispersion measure. The proposed iterative algorithm uses auxiliary covering-based integer programming models that help validate if, for given values of the objective function of the original problem, it is possible to find feasible solutions with at most p territories. Empirical tests on instances with up to 300 basic units reveal that the proposed algorithm performs significantly faster than the best-known exact solution method.

13:06
Optimal location of loading/unloading bays in urban areas, model and case study
PRESENTER: Germán Faller

ABSTRACT. We address the problem of determining the optimal number and location of slots within the urban parking space, reserved to perform operations of delivery and/or pick-up of goods to/from a set of given clients. We extend an existing mixed integer-linear programming model for the location of slots and demand assignment, by adding constraints which allow to control both the distance between clients and slots, and the splitting of required parking time for each client. We apply and compare both models using a case study related to the central business district of a medium-sized city.

13:28
Solving the integration of storage location and order picking activities in a warehouse

ABSTRACT. In a supply chain, order picking is the process of taking products from a storage location inside of a warehouse to complete customer orders. On the other hand, the storage location of products is another activity that may affect the picking if it is not optimized. We study the integration of both activities and propose a solution method applied to a real-world problem of a company in Mexico. The aim is to find the best assignment of products to locations that minimizes the total picking time. Computational results are presented.

12:00-13:50 Session WC2
12:00
Strategic berth template problems with homogeneous and heterogeneous frequencies
PRESENTER: Elena Fernández

ABSTRACT. Broadly speaking, berth allocation problems aim at assigning berthing positions and service times to calling ships at a container terminal. Due the relevance and actual economic implications of these problems, different variants and extensions have been studied in the literature. One such extension is to assume that the fixed planning horizon is repeated in a cyclic fashion, giving rise to berth template problems (BTP). A relevant BTP is the Strategic Berth Template Problem (SBTP), which combines strategic and operational decisions for medium-term berth planning of a given set of cyclically calling ships. While the strategic decisions dictate the ship calls that will be served and those whose service call will be rejected, the operational decisions determine the berth template that will be applied in a cyclic fashion in the considered planning horizon. Furthermore, the SBTP incorporates additional conditions linking the strategic acceptance/rejection decisions to ships belonging to certain groups. The SBTP was introduced in Imai et al., who proposed a first formulation and several Lagrangean heuristics. The initial formulation, which remained computationally unexplored, was analyzed in Iris et al., who also proposed a different formulation based on the solution of a generalized set-packing problem.

One of the modeling assumptions of the SBTP is that it is homogeneous, in the sense that the length of the cycle is the same for all calls. In this work we address the homogeneous SBTP (Ho-SBTH) and introduce the heterogeneous STBP (He-SBTH), its extension where it is no longer assumed that all ships have the same cycle length (frequency).

12:22
Fairness in Maximal Covering Location Problems
PRESENTER: Victor Blanco

ABSTRACT. We provide a general mathematical programming based framework to incorporate fairness measures from the facilities' perspective to Discrete and Continuous Maximal Covering Location Problems (MCLP). We assume that a given number of services is to be located to maximize the demand covered by the different agents in which a fairly ideal solution, one would desire to ``independently'' maximize the covered demand of each of the services, not affecting negatively to the coverage of the others. However, since the demands are usually indivisible, in most cases, an advantageous solution for one service harms others. As already happens in other decision problems, one may prefer to slightly sacrifice the overall covered demand in order to equalize the different covered demands among the open services. We incorporate fairness criteria to the MCLP by means of a novel measure that combines the concept of alpha-fairness and certain Ordered Weighted Averaging (OWA) aggregation operators of the covered demands of each service. We provide a general models and several reformulation as Mixed Integer Second Order Cone Optimization problems. We also empirically analyze the performance of the different approaches proposals.

12:44
E-grocery distribution logistics: The storage location assignment problem
PRESENTER: David Winkelmann

ABSTRACT. E-grocery retailing enables customers to order online while the retailer delivers the purchase within a determined time slot. Retailers are faced with the additional fulfilment processes picking and delivery. Therefore, a key challenge is the allocation of articles to picking stations within the distribution warehouses. While a re-allocation is cost-intensive, different requirements have to be fulfilled, e.g. articles with a high weight have to be assigned to early stations. To avoid congestion and delay leading to a dissatisfying service for customers, the articles have to be allocated such that demand is balanced across stations. Using real-world data provided by a European e-grocery retailer, we use MIP-based approaches to optimise the article assignment considering within-week variation in demand.

13:06
A profit-maximizing hub network design problem considering hub congestion, time-sensitive demands and 2-stop paths

ABSTRACT. Hub location models are used to design transportation networks for airlines, parcel delivery, LTL truck companies, etc. There are previous works considering congestion, time-sensitive demands, and profit maximization, but not necessarily at the same time. We formulate and solve a profit-maximizing hub network design problem considering simultaneously hub congestion, time-sensitive demands through stepwise functions, allowing paths with one or two stops (hubs). The resulting formulation is very challenging to solve up to optimality, resulting in large optimality gaps. We developed a set of variable fixing procedures to speed up the solution procedure. Preliminary results show the convenience of the proposed variable fixing procedures. Future research also includes the development of an ad-hoc decomposition approach.

13:28
Hub Location Models with protection under failures
PRESENTER: Victor Blanco

ABSTRACT. In this work we propose two alternative hub location models with protection under failures, which guarantee that solution networks are such that for each commodity there exists an original and at least one alternative routing path. Both models minimize the sum of the set-up costs of the activated hubs and inter-hub arcs, plus the expected value of the routing costs of the original and alternative paths but differ essentially in how this is enforced. The first model imposes that the alternative routing path contains at most one inter-hub arc and builds it explicitly. The second model is more flexible, in the sense that it allows that arbitrarily large sequences of inter-hub arcs are used in the alternative routing paths, although alternative paths are not built explicitly. Extensive computational experiments have been carried out on a large set of benchmark instances based on the well-known CAB and AP data sets, for varying settings of the failure probabilities and other cost parameters. The obtained results are summarized and analyzed, and managerial insights are derived. Finally, an empirical analysis of the performance of the two proposed models has been carried out.

13:50-15:00Lunch Break
15:00-16:30 Session WD1
15:00
Optimization of steel production planning considering continuous-casting and rolling processes
PRESENTER: Nelson Torres

ABSTRACT. Steel is a widely used material with applications on a extensive variety of areas, from home appliance to construction projects like bridges and buildings. Because of its versality, its production plants are also very different, and there is no single optimization tool used to schedule production in steel plants. Our goal is to schedule coils (orders of steel) by a MIP model, minimizing the total cost of production, considering a plant with four stages of production: steel-making, continuous casting, direct transferring and rolling. Because of this configuration and the direct transferring, we need to consider several operational and security requirements in this model. We use the setup of the Nucor facility in Alabama, US, where schedules are generated ”manually” by their operators. A day usually has 2 batches of 100-150 coils, that have to be casted in two parallel casters.

We propose a coil-based model to help schedulers generate near-optimal solutions in an operationally feasible time, which is a more specific approach than most of the proposed models in the literature, that usually are heat-based models where coils are grouped based on their grade and scheduled without many coil unique considerations.

15:22
The Vehicle Routing Problem with Release Dates and Drone Resupply

ABSTRACT. This presentation introduces the Vehicle Routing Problem with Release Dates and Drone Resupply, consisting of finding a set of routes for a fleet of trucks to deliver orders that become available throughout the day. Once the trucks start their routes, they need not return to the depot to collect newly available orders, as these orders are sent to them via drones. Assuming that the orders’ release times are known at the beginning of the day, a MILP formulation is presented. We also developed a matheuristic approach for solving large-size instances, which outperforms state-of-the-art solvers.

15:44
An extended IP formulation for the Freight on Transport problem

ABSTRACT. The boom of e-commerce in the last decade, and its growth projections for the coming years, raises new challenges as retailers and couriers innovate their supply chains to keep up with demand. Last-mile delivery (LMD), the segment of the supply chain which starts at the last distribution centre and ends at the customer's doorstep, is particularly affected. The growth of volume in LMD has also caused concern, especially in dense urban environments where the externalities (traffic, emissions, etc.) have become noticeable. Several authors in Operational Research (OR), Environmental Engineering, Urban Planning and Economics have proposed alternative LMD implementations which aim at reducing the externalities while guaranteeing a timely and inexpensive service. Solutions range from congestion taxes and economic incentives, up to deliveries using autonomous drones. We focus on one promising operational practice: integrating public transport within LMD, to leverage unused capacity and reduce the number of delivery vehicles in the city. This concept has emerged during the last years and is gaining attraction, both academically and in practice. In our study, we consider a three-echelon system. In the first echelon, transport trucks move parcels from distribution centres to public transport depots or large stations. In the second echelon, public transport vehicles transport the parcels towards the city centre and drop them off at some of their scheduled stops. In the third echelon, zero-emission vehicles (such as cargo bikes) deliver the parcels to the customers' preferred locations. In this work, we propose an extended IP formulation to tackle this problem in practice.

16:06
An Iterated Tabu Search for the Multi-Depot Cumulative Capacitated Vehicle Routing Problem
PRESENTER: Carlos Rey

ABSTRACT. The Multi-Depot Cumulative Capacitated Vehicle Routing Problem (MDCCVRP) considers a set of customers and a set of depots. The objective is to minimize the sum of the arrival times at the customers, which must be visited once by a single-vehicle. Each vehicle has a capacity that cannot be exceeded and can start its route from any depot. The MDCCVRP generalizes the Cumulative Capacitated Vehicle Routing Problem by adding multiple depots. The MDCCVRP was solved in the literature by other authors. Previously, a POPMUSIC algorithm was proposed, which decomposes the problem into smaller sub-problems solved through the commercial solver CPLEX. More recently, some authors proposed a perturbation-based local search algorithm. In this talk, an iterated tabu search is presented to solve the problem. The algorithm starts with a hybrid process for generating an initial solution. The current solution is improved in an iterative way using a roulette-wheel perturbation and a tabu search procedure. The perturbation process applies changes on the vehicles/depots relations. After the perturbation, a tabu search procedure is applied on different neighborhoods under the best improve criterion. The results on MDCCVRP benchmark instances show that the proposed algorithm is competitive with those presented in the literature, obtaining high-quality solutions in reasonable computing times.