In this paper, we consider the problem of planning non-pharmaceutical interventions to control the spread of infectious diseases. We propose a new model derived from classical compartmental models; however, we model spatial and population-structure heterogeneity of population mixing. The resulting model is a large-scale non-linear and non-convex optimisation problem. In order to solve it, we apply a special variant of covariance matrix adaptation evolution strategy. We show that results obtained for three different objectives are better than natural heuristics and, moreover, that the introduction of an individual's mobility to the model is significant for the quality of the decisions. We apply our approach to a six-compartmental model with detailed Poland and COVID-19 disease data. The obtained results are non-trivialand sometimes unexpected; therefore, we believe that our model could be applied to support policy-makers in fighting diseases at the long-term decision-making level.

The recent Covid-19 outbreak put healthcare resources under enormous pressure. Governments and healthcare authorities faced major challenges in securing and delivering critical supplies such as personal protective equipment (PPE) and test kits. As timely distribution of critical supplies exceeded government resources, certain sectors, negatively impacted by the pandemic, offered their storage and distribution capabilities; both helping with the crisis and creating economic revenue. We investigate the problem of optimally leveraging the capacity and efficiency of underutilized distribution networks to enhance the capability of government supply networks to meet healthcare needs for critical supplies. We model the problem as a dynamic distribution planning problem that decides on the re-purposing of storage facilities, the allocation of demand, and the timely distribution of limited PPE supplies to different jurisdictions. From a resource provider's perspective, the goal is to maximize demand fulfillment based on priorities set out by the government, as well as maximize economic value to participating networks. As uncertainty is a prevalent feature of the problem, we adopt a robust framework due to the lack of historical data on such supply uncertainties. We provide a mixed integer programming formulation for the adversarial problem and present a cutting plane algorithm to solve the robust model efficiently under both polyhedral and ellipsoidal uncertainty sets. We build a case study for the province of Ontario, Canada, and run extensive analysis of the service and economic value trade-off, and the effects of modeling demand priorities and supply uncertainties.

The outbreak of COVID-19 dramatically impacts the global economy. Mass COVID-19 vaccination is widely regarded as the most promising way to fight against the pandemic and help return to normal. Many governments have authorized certain types of vaccines for mass vaccination by establishing appointment platforms. Mass vaccination poses a vital challenge to decision-makers responsible for scheduling a large number of appointments. This paper studies a vaccination site selection, appointment acceptance, appointment assignment, and scheduling problem for mass vaccination in response to COVID-19. An optimal solution to the problem determines the open vaccination sites, the set of accepted appointments, the assignment of accepted appointments to open vaccination sites, and the vaccination sequence at each site. The objective is to simultaneously minimize 1) the fixed cost for operating vaccination sites; 2) the traveling distance of vaccine recipients; 3) the appointment rejection cost; and 4) the vaccination tardiness cost. We formulate the problem as a mixed-integer linear program (MILP). Given the NP-hardness of the problem, we then develop an exact logic-based Benders decomposition (LBBD) method and a matheuristic method (MH) to solve practical-sized problem instances. We conduct numerical experiments on small- to large-sized instances to demonstrate the performance of the proposed model and solution methods. Computational results indicate that the proposed methods provide optimal solutions to small-sized instances and near-optimal solutions to large ones. In particular, the developed matheuristic can efficiently solve practical-sized instances with up to 500 appointments and 50 vaccination sites. We discuss managerial implications drawn from our results for the mass COVID-19 vaccination appointment scheduling, which help decision-makers make critical decisions.

We consider a retail firm selling a durable product in a volatile market where the demand is price-sensitive and random but its distribution is unknown. The firm dynamically replenishes inventory and adjusts prices over time and learns about the demand distribution. Assuming that the demand model is of the multiplicative form and unmet demand is partially backlogged, we take the empirical Bayesian approach to formulate the problem as a stochastic dynamic program. We first identify a set of regularity conditions on demand models and show that the state-dependent base-stock list-price policy is optimal. We next employ the dimensionality reduction approach to separate the scale factor that captures observed demand information from the optimal profit function, which yields a normalized dynamic program that is more tractable. We also analyze the effect of demand learning on the optimal policy using the system without Bayesian update as a benchmark. We further extend our analysis to the case with unobserved lost sales and the case with additive demand.

The determination of critical facilities in supply chain networks has been attracting the interest of the Operations Research community. Critical facilities refer to structures including bridges, railways, train/metro stations, medical facilities, roads, warehouses, and power stations among others, which are vital to the functioning of the network. In this study we address a trilevel optimization problem for the protection of depots of utmost importance in a routing network against an intelligent adversary. We formulate the problem as a defender-attacker-defender game and refer to it as the trilevel -interdiction selective multi-depot vehicle routing problem (3LRI-SMDVRP). The defender is the decision maker in the upper level problem (ULP) who picks depots to protect among existing ones. In the middle level problem (MLP), the attacker destroys depots among the () unprotected ones to bring about the biggest disruption. Finally, in the lower level problem (LLP), the decision maker is again the defender who optimizes the vehicle routes and thereby selects which customers to visit and serve in the wake of the attack. All three levels have an identical objective function which is comprised of three components. (i) Operating or acquisition cost of the vehicles. (ii) Traveling cost incurred by the vehicles. (iii) Outsourcing cost due to unvisited customers. The defender aspires to minimize this objective function while the attacker tries to maximize it. As a solution approach to this trilevel discrete optimization problem, we resort to a smart exhaustive enumeration in the ULP and MLP. For the LLP we design a metaheuristic algorithm that hybridizes Variable Neighborhood Descent and Tabu Search techniques adapted to the Selective MDVRP (SMDVRP). The performance of this algorithm is demonstrated on 33 MDVRP benchmark instances existing in the literature and 41 SMDVRP instances generated from them. Numerical experiments on a large number of 3LRI-SMDVRP instances attest that our comprehensive method is effective in dealing with the defender-attacker-defender game on multi-depot routing networks.

In so-called random preference models of probabilistic choice, a decision maker chooses according to an unspecified probability distribution over preference states. The most prominent case arises when preference states are linear orders or weak orders of the choice alternatives. The literature has documented that actually evaluating whether decision makers' observed choices are consistent with such a probabilistic model of choice poses computational difficulties. This severely limits the possible scale of empirical work in behavioral economics and related disciplines. We propose a family of column generation based algorithms for performing such tests. We evaluate our algorithms on various sets of instances. We observe substantial improvements in computation time and conclude that we can efficiently test substantially larger data sets than previously possible.

Decision-making problems in emergency response are usually risky and uncertain due to the limited decision data and possible evolvement of emergency scenarios. This paper focuses on a risk decision-making problem in emergency response with several distinct characteristics including dynamic evolvement process of emergency, multiple scenarios, and impact of response actions on the emergency scenarios. A method based on Fault Tree Analysis (FTA) is proposed to solve the problem. By analyzing the evolvement process of emergency, the Fault Tree (FT) is constructed to describe the logical relations among conditions and factors resulting in the evolvement of emergency. Given different feasible response actions, the probabilities of emergency scenarios are estimated by FTA. Furthermore, the overall ranking value of each action is calculated, and a ranking of feasible response actions is determined. Finally, a case study on H1N1 infectious diseases is given to illustrate the feasibility and validity of the proposed method.

We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.

Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.

High throughput biological data need to be processed, analyzed, and interpreted to address problems in life sciences. Bioinformatics, computational biology, and systems biology deal with biological problems using computational methods. Clustering is one of the methods used to gain insight into biological processes, particularly at the genomics level. Clearly, clustering can be used in many areas of biological data analysis. However, this paper presents a review of the current clustering algorithms designed especially for analyzing gene expression data. It is also intended to introduce one of the main problems in bioinformatics - clustering gene expression data - to the operations research community.

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.

This paper introduces multi-directional local search, a metaheuristic for multi-objective optimization. We first motivate the method and present an algorithmic framework for it. We then apply it to several known multi-objective problems such as the multi-objective multi-dimensional knapsack problem, the bi-objective set packing problem and the bi-objective orienteering problem. Experimental results show that our method systematically provides solution sets of comparable quality with state-of-the-art methods applied to benchmark instances of these problems, within reasonable CPU effort. We conclude that the proposed algorithmic framework is a viable option when solving multi-objective optimization problems.

In this paper, we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP). The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm outperforms existing solution methods for the 2E-VRP and achieves excellent results on the LRP.

We formulate a bi-objective covering tour model with stochastic demand where the two objectives are given by (i) cost (opening cost for distribution centers plus routing cost for a fleet of vehicles) and (ii) expected uncovered demand. In the model, it is assumed that depending on the distance, a certain percentage of clients go from their homes to the nearest distribution center. An application in humanitarian logistics is envisaged. For the computational solution of the resulting bi-objective two-stage stochastic program with recourse, a branch-and-cut technique, applied to a sample-average version of the problem obtained from a fixed random sample of demand vectors, is used within an epsilon-constraint algorithm. Computational results on real-world data for rural communities in Senegal show the viability of the approach.

The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15%. Moreover, improvements of up to 41% can be achieved for some test instances.

This article comprises the first theoretical and computational study on mixed integer programming (MIP) models for the connected facility location problem (ConFL). ConFL combines facility location and Steiner trees: given a set of customers, a set of potential facility locations and some inter-connection nodes, ConFL searches for the minimum-cost way of assigning each customer to exactly one open facility, and connecting the open facilities via a Steiner tree. The costs needed for building the Steiner tree, facility opening costs and the assignment costs need to be minimized. We model ConFL using seven compact and three mixed integer programming formulations of exponential size. We also show how to transform ConFL into the Steiner arborescence problem. A full hierarchy between the models is provided. For two exponential size models we develop a branch-and-cut algorithm. An extensive computational study is based on two benchmark sets of randomly generated instances with up to 1300 nodes and 115,000 edges. We empirically compare the presented models with respect to the quality of obtained bounds and the corresponding running time. We report optimal values for all but 16 instances for which the obtained gaps are below 0.6%.