Search

Geographic information systems, global positioning systems, traffic flow sensors and cellular phones are sources of real-time traffic data in road networks. However, many vehicle routing algorithms do not account for this real-time information. In this paper, we consider the problem of adjusting in real-time a time-dependent delivery plan to respond to dynamic changes in travel times. We also consider a variant of the problem in which some customer requests can be canceled. The goal is to minimize disruption by maintaining as much as possible the current planned routes, although without compromising too much solution quality. Computational results obtained by solving instances with up to 500 customers are reported and compared with a strategy that maintains the planned routes, whatever the cost.

In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart.

Network stability is a key performance metric in supporting real time communication over wireless networks. Because of high bandwidth demand and dynamic traffic variation, several paths in Wireless Mesh Networks (WMNs) are expected to be unstable. High levels of network instability can lead to interferences, packet losses and high delays. In this paper, we address the stability problem of WMNs. Instability in these networks is caused mainly by link quality fluctuations and frequent route flapping. First, we present the key factors that may cause network instability. Then, we propose a new technique, called Node Stability-based Routing (NSR), using the entropy function to define a node stability and a probability function to select an appropriate gateway. Simulation results show that NSR can significantly improve the overall network performance compared to techniques using interference and channel switching (MIC), Expected Transmission count (ETX) or load at gateways as a routing metric, Reinforcement learning-based best path to best gateway (RLBDR), and nearest gateway (i.e., shortest path to gateway).

This paper presents a new formulation for the risk averse stochastic reservoir management problem. Using recent advances in robust optimization and stochastic programming, we propose a multi-stage model based on minimization of a risk measure associated with floods and droughts for a hydro-electrical complex. We present our model and then identify approximate solutions using standard affine decision rules commonly found in the literature as well as lifted decision rules. Finally, we conduct thorough numerical experiments based on a real river system in Western Quebec and conclude on the relative performance of families of decision rules.

In this paper, we consider a multi-attribute technician routing and scheduling problem motivated by an application for the maintenance and repair of electronic transaction equipment. This problem i...

Due to exorbitant product variety, very limited space, and other factors, organizing efficient and timely deliveries of parts and subassemblies to final assembly within the factory is one of the most pressing problems of modern mixed-model assembly production. Many automobile producers have implemented the so-called “supermarket” concept to transfer material to the assembly line frequently and in small lots. Supermarkets are decentralized logistics areas on the shop floor where parts are intermediately stored for nearby assembly cells, to be ferried there by small transport vehicles (called tow trains or tuggers). This paper tackles the operational problem of drawing up schedules for these tow trains, such that the assembly line never starves for parts while also minimizing in-process inventory, thus satisfying just-in-time goals. We prove strong NP-completeness of the problem and present exact and heuristic solution methods. In a computational study, the procedures are shown to perform very well, solving realistic instances to (near-)optimality in a matter of minutes, clearly outperforming the simple cyclic schedules commonly used in industrial practice. We also provide some managerial insight into the right degree of automation for such a part feeding system.

Real-time re-planning in reaction to disruptions can be done effectively and efficiently for realistic LTSP instances.Time-space networks can be exploited to incorporate impacts of disruptions and to reduce the size of the problem.MIP technology can be exploited in this context: effective solutions found in a short computational time. In this paper, we present a mathematical programming model based on a time-space network representation for solving real-time transportation problems in forestry. We cover a wide range of unforeseen events that may disrupt the planned transportation operations (e.g., delays, changes in the demand and changes in the topology of the transportation network). Although each of these events has different impacts on the initial transportation plan, one key characteristic of the proposed model is that it remains valid for dealing with all the unforeseen events, regardless of their nature. Indeed, the impacts of such events are reflected in a time-space network and in the input parameters rather than in the model itself. The empirical evaluation of the proposed approach is based on data provided by Canadian forestry companies and tested under generated disruption scenarios. The test sets have been successfully solved to optimality in short computational times and demonstrate the potential improvement of transportation operations incurred by this approach.

In this paper, we propose a novel heuristic algorithm for the volumetric-modulated arc therapy treatment planning problem, optimizing the trade-off between delivery time and treatment quality. We present a new mixed integer programming model in which the multi-leaf collimator leaf positions, gantry speed, and dose rate are determined simultaneously. Our heuristic is based on column generation; the aperture configuration is modeled in the columns and the dose distribution and time restriction in the rows. To reduce the number of voxels and increase the efficiency of the master model, we aggregate similar voxels using a clustering technique. The efficiency of the algorithm and the treatment quality are evaluated on a benchmark clinical prostate cancer case. The computational results show that a high-quality treatment is achievable using a four-thread CPU. Finally, we analyze the effects of the various parameters and two leaf-motion strategies.

A novel time dependent version of the Traveling Purchaser Problem is presented.A LP model introducing constrains to represent dynamically changing quantities is defined.An exact method based on a branch-and-cut algorithm exploiting the structure of the problem is described.Experiments over a wide set of instances show the efficacy of the proposed approach. The deterministic Traveling Purchaser Problem looks for a tour visiting a subset of markets in order to satisfy a positive discrete demand for some products at minimum traveling and purchasing costs. In this paper, we assume that the quantities available in the markets for all the products are time-varying decreasing at a constant rate. We propose a compact mixed integer formulation for the problem, and strengthen it with the introduction of connectivity constraints. A new branching strategy and a primal heuristic enforcing the bounding operations have been embedded into a branch-and-cut framework. The branching rule exploits a simple valid inequality and the potential presence of necessary markets. The resulting method outperforms CPLEX 12.6 when used to solve the proposed model. The algorithms have been tested on standard TSPLIB instances, modified to include products and quantities that decrease at different rates of consumption.

The Benders decomposition algorithm has been successfully applied to a wide range of difficult optimization problems. This paper presents a state-of-the-art survey of this algorithm, emphasizing its use in combinatorial optimization. We discuss the classical algorithm, the impact of the problem formulation on its convergence, and the relationship to other decomposition methods. We introduce a taxonomy of algorithmic enhancements and acceleration strategies based on the main components of the algorithm. The taxonomy provides the framework to synthesize the literature, and to identify shortcomings, trends and potential research directions. We also discuss the use of the Benders Decomposition to develop efficient (meta-)heuristics, describe the limitations of the classical algorithm, and present extensions enabling its application to a broader range of problems.

This paper addresses the generation of scenario trees to solve stochastic programming problems that have a large number of possible values for the random parameters (possibly infinitely many). For the sake of the computational efficiency, the scenario trees must include only a finite (rather small) number of scenarios, therefore, they provide decisions only for some values of the random parameters. To overcome the resulting loss of information, we propose to introduce an extension procedure. It is a systematic approach to interpolate and extrapolate the scenario-tree decisions to obtain a decision policy that can be implemented for any value of the random parameters at little computational cost. To assess the quality of the scenario-tree generation method and the extension procedure (STGM-EP), we introduce three generic quality parameters that focus on the quality of the decisions. We use these quality parameters to develop a framework that will help the decision-maker to select the most suitable STGM-EP for a given stochastic programming problem. We perform numerical experiments on two case studies. The quality parameters are used to compare three scenario-tree generation methods and three extension procedures (hence nine couples STGM-EP). We show that it is possible to single out the best couple in both problems, which provides decisions close to optimality at little computational cost.

In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three-phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.

This paper proposes a two-stage stochastic mixed-integer programming model for a closed-loop supply chain network design problem in the context of modular structured products in which the reverse network entails several types of recovery options. It accounts for uncertainty in the quality status of the return stream, modeled as binary scenarios for each component in the reverse bill of material corresponding to such products. To deal with the intractable number of scenarios in the proposed model, a scenario reduction scheme is adapted to the problem of interest to preserve the most pertinent scenarios based on a modified Euclidean distance measure. The reduced stochastic large-scale optimization problem is then solved via a L-shaped algorithm enhanced with surrogate constraints and Pareto-optimal cuts. Numerical results indicate that the scenario reduction algorithm provides good quality solutions to the stochastic problem in a reasonable amount of time through applying the enhanced L-shaped method.

Vehicle routing problems have been at the core of distribution issues in logistics planning for more than 50 years. Since the seminal paper of Dantzig and Ramser (1959), thousands of papers have been devoted to these problems. It is interesting to note, however, that the great majority of this plethoric literature deals with problems in which the distribution plan that is to be determined by solving some optimization formulation will proceed without incidents.

In this paper, we propose an extension of the vehicle routing problem with cross-docking that takes into account resource constraints at the cross-dock. These constraints limit the number of docks that can be used simultaneously. To solve this new problem, we adapt a recently proposed matheuristic based on large neighborhood search. In particular, we focus on the feasibility tests for insertions and compare heuristics and constraint programming strategies. Finally, computational experiments on instances adapted from the vehicle routing problem with cross-docking are reported. They give insights on the impact of a limited cross-dock capacity on the routing cost.

Short-term hydrogeneration scheduling aims at minimizing water consumption for the next 7–15 days on an hourly basis, while satisfying the electrical load as well as many operational, regul...

In this paper, we propose a new recourse policy for the vehicle routing problem with stochastic demands (VRPSD). In this routing problem, customer demands are characterized by known probability distributions. The actual demand values are only revealed upon arriving at a customer location. The objective of the problem is to plan routes minimizing the travel cost and the expect recourse cost. The latter cost is a result of a predetermined recourse policy designed to handle route failures. Given the planned routes, such failures may occur in the event where a vehicle has insufficient capacity to serve the current customer or the next customer. In the relevant literature, there are three types of recourse policies: (i) classical, where failures at customers are handled by return trips to the depot, (ii) optimal restocking, where preventive restocking trips to the depot are performed based on optimized customer-specific thresholds, and failures are handled by return trips to the depot, and (iii) rule-based policies, where preventive restocking trips are performed based on thresholds established by preset rules, and failures are handled by performing return trips to the depot. While the first type is rather myopic, the last two types of recourse policies use simplistic comparisons of the vehicle’s residual capacity to trigger recourse actions. In this paper, we propose a more advanced rule-based recourse policy, which does not solely depend on the vehicle’s residual capacity. To do so, we first propose a taxonomy that groups rule-based policies into three classes, we then propose the first hybrid recourse policy, which simultaneously combines two of these classes, namely risk and distance. We develop an exact solution algorithm for the VRPSD with this hybrid recourse policy and conduct a broad range of computational experiments. The algorithm is able to solve instances with up to 60 customers, and for certain experimental configurations, the exact algorithm solves to optimality up to 79% of the instances. Finally, we show that when the optimal routes of the hybrid policy are operated under the optimal restocking policy they yield a marginal average cost difference.

In this paper, we study a Capacitated Lot Sizing Problem with Stochastic Setup Times and Overtime (CLSPSSTO). We describe a mathematical model that considers both regular costs (including production, setup and inventory holding costs) and expected overtime costs (related to the excess usage of capacity). The CLSP-SSTO is formulated as a two-stage stochastic programming problem. A procedure is proposed to exactly compute the expected overtime for a given setup and production plan when the setup times follow a Gamma distribution. A sample average approximation procedure is applied to obtain upper bounds and a statistical lower bound. This is then used to benchmark the performance of two additional heuristics. A first heuristic is based on changing the capacity in the deterministic counterpart, while the second heuristic artificially modifies the setup time. We conduct our computational experiments on well-known problem instances and provide comprehensive analyses to evaluate the performance of each heuristic. (C) 2018 Elsevier B.V. All rights reserved.

This paper addresses a technician routing and scheduling problem motivated by an application for the repair and maintenance of electronic transactions equipment. The problem exhibits many special features like multiple time windows for service, an inventory of spare parts carried by each technician and tasks that may require a special part to be performed. A problem-solving methodology based on tabu search, coupled with an adaptive memory, is proposed. The inclusion of solutions (local minima) in the adaptive memory takes into account both quality and diversity. Results are reported on test instances with up to 200 tasks. A comparison with a previously developed branch-and-price algorithm is also reported on instances of small size.

The travel time to proceed from one location to another in a network is an important consideration in many urban transportation settings ranging from the planning of delivery routes in freight transportation to the determination of shortest itineraries in advanced traveler information systems. Accordingly, accurate travel time predictions are of foremost importance. In an urban environment, vehicle speeds, and consequently travel times, can be highly variable due to congestion caused, for instance, by accidents or bad weather conditions. At another level, one also observes daily patterns (e.g., rush hours), weekly patterns (e.g., weekdays versus weekend), and seasonal patterns. Capturing these time-varying patterns when modeling travel speeds can provide an immediate benefit to commercial transportation companies that distribute goods, since it allows them to better optimize their routes and reduce their environmental footprint. This paper presents the first part of a project aimed at optimizing time-dependent delivery routes in an urban setting. It focuses on the prediction of travel speeds using as input GPS traces of commercial vehicles collected over a significant period of time. The proposed algorithmic framework is made of a number of macro-steps where different machine learning and data mining methods are applied. Computational results are reported on real data to empirically demonstrate the accuracy of the obtained predictions.

This problem involves optimizing product collection and redistribution from production locations to a set of processing plants over a planning horizon. This horizon consists of several days, and the collection-redistribution is performed on a repeating daily basis. A single routing plan must be prepared for the whole horizon, taking into account the seasonal variations in the supply. We model the problem using a sequence of periods, each corresponding to a season. We propose an adaptive large-neighborhood search with several specifically designed operators and features. The results show the excellent performance of the algorithm in terms of solution quality and computational efficiency.

Stochastic vehicle routing, which deals with routing problems in which some of the key problem parameters are not known with certainty, has been an active, but fairly small research area for almost 50 years. However, over the past 15 years we have witnessed a steady increase in the number of papers targeting stochastic versions of the vehicle routing problem (VRP). This increase may be explained by the larger amount of data available to better analyze and understand various stochastic phenomena at hand, coupled with methodological advances that have yielded solution tools capable of handling some of the computational challenges involved in such problems. In this paper, we first briefly sketch the state-of-the-art in stochastic vehicle routing by examining the main classes of stochastic VRPs (problems with stochastic demands, with stochastic customers, and with stochastic travel or service times), the modeling paradigms that have been used to formulate them, and existing exact and approximate solution methods that have been proposed to tackle them. We then identify and discuss two groups of critical issues and challenges that need to be addressed to advance research in this area. These revolve around the expression of stochastic phenomena and the development of new recourse strategies. Based on this discussion, we conclude the paper by proposing a number of promising research directions.

Durable products are characterized by their modular structured design as well as their long life cycle. Each class of components involved in the multi-indenture structure of such products requires a different recovery process. Moreover, due to their long life cycle, the return flows are of various quality levels. In this article, we study a closed-loop supply chain in the context of durable products with generic modular structures. To this end, we propose a mixed-integer programming model based on a generic disassembly tree where the number of each sub-assembly depends on the quality status of the return stream. The model determines the location of various types of facilities in the reverse network while coordinating forward and reverse flows. We also consider the legislative target for the recovery of used products as a constraint in the problem formulation. We present a Benders decomposition-based solution algorithm together with several algorithmic enhancements for this problem. Computational results illustrate the superior performance of the solution method.

We consider the problem of designing supply networks for producing and distributing goods under restricted customer order lead times. Companies apply various instruments for fulfilling orders within preset lead times, such as locating facilities close to markets, producing products to stock, choosing fast modes of transportation, or delivering products directly from plants to customers without the use of distribution centers. We provide two alternative models that consider these options to a different extent, when designing multi-layer, multi-product facility networks that guarantee meeting restricted lead times. A computational evaluation compares both models with respect to solvability and the quality of the obtained networks. We find that formulating the problem as a time–space network flow model considerably helps to design high-quality networks. Furthermore, the lead times quoted to customers affect the design of all layers in the supply network. In turn, this shows that when service requirem...

Wireless mesh networks (WMNs) are currently used to provide broadband access to the Internet anytime and anywhere. Generally, WMNs consist of mesh routers equipped with one or more interfaces allowing connectivity to the Internet through gateways. To route traffic from sources to destinations, many routing protocols have been proposed in the literature. However, most of them take into account at most one metric (e.g., interferences, packet losses, and load at gateways). Moreover, almost all of these schemes consider only one type of interferences: interflow or intraflow. In this paper, we propose a new source routing and gateway selection scheme, which is called source-based routing (SBR), that improves the performance of WMNs. SBR uses a novel routing metric, which is a combination of packet losses, intraflow and interflow interferences, and load at gateways, to select best paths to reach selected gateways. Simulation results show that the proposed SBR improves the network performance and outperforms existing routing schemes, which are based on expected transmission count (ETX), nearest gateway (NG; i.e., shortest path to gateway), load at gateways (LG), or interference ratio (IR); more specifically, SBR yields 33%, 26%, 13%, and 10% more throughput compared with LG, ETX, NG, and IR, respectively.

The vehicle routing problem with hard time windows and stochastic service times ( VRPTW-ST ) introduced by Errico et al. (2013) in the form of a chance-constrained model mainly differs from other vehicle routing problems with stochastic service or travel times considered in the literature by the presence of hard time windows. This makes the problem extremely challenging. In this paper, we model the VRPTW-ST as a two-stage stochastic program and define two recourse policies to recover operations feasibility when the first stage plan turns out to be infeasible. We formulate the VRPTW-ST as a set partitioning problem and solve it by exact branch-cut-and-price algorithms. Specifically, we developed efficient labeling algorithms by suitably choosing label components, determining extension functions, and developing lower and upper bounds on partial route reduced cost to be used in the column generation step. Results on benchmark data show that our methods are able to solve instances with up to 50 customers for both recourse policies.

In this paper, the integrated planning of production, maintenance, and quality in deteriorating systems is investigated. The production planning part of the model addresses a multi-product lot-sizing problem with deteriorating quality and in quality planning, we discuss the optimal determination of an inspection process that is used to study the hidden state of the system. Considering imperfect maintenance linked to the machine age and with several possibilities for improving the machine conditions, a maintenance plan determines the type of operations to be performed on the machine in each intrusion. These decisions are simultaneously linked to the lot-sizing and quality decisions where the objective function minimizes the total cost of the system. A numerical example and sensitivity analysis of the problem are also presented.

This paper studies the robust optimization approach for the routing problem encountered in daily maintenance operations of a road network. The uncertainty of service time is considered. The robust optimization approach yields routes that minimize total cost while being less sensitive to substantial deviations of service times. A robust optimization model is developed and solved by the branch-and-cut method. In computational experiments, the behavior of the robust solutions and their performance are analyzed using Monte Carlo simulation. The robust optimization model is also compared with a classic chance-constrained programming model. The experimental analysis provides managerial insights for decision makers to determine an appropriate routing strategy.

This paper introduces a version of the classical traveling salesman problem with time-dependent service times. In our setting, the duration required to provide service to any customer is not fixed but defined as a function of the time at which service starts at that location. The objective is to minimize the total route duration, which consists of the total travel time plus the total service time. The proposed model can handle several types of service time functions, e.g., linear and quadratic functions. We describe basic properties for certain classes of service time functions, followed by the computation of valid lower and upper bounds. We apply several classes of subtour elimination constraints and measure their effect on the performance of our model. Numerical results obtained by implementing different linear and quadratic service time functions on several test instances are presented.

While the storage properties and the anticipation potential of many classes of power system loads (such as thermal loads) can be exploited to mitigate renewable sources variability, the challenge to do so in an optimal and coherentmanner is significant. This is due to the sheer number and dynamic diversity of the loads that can be involved in any large-scale application. The smartDESC concept is a control architecture that was developed for this purpose. It builds on the more pervasive communication means currently available (such as Advanced Metering Infrastructures), as well as the mathematical tools of (i) aggregate load modeling, (ii) renewable energy forecasting, (iii) optimizationtheory, deterministic or stochastic, and (iv) some recent developments in control of large-scale systems based ongame theory, and so-called mean-field (MF) control theory, which allow a scalable yet optimal approach to thedecentralized control of large pools of loads. This paper presents the building blocks of the smartDESC architecture,together with an associated simulator and simulation results.

A new hybrid approach for the rail-truck intermodal transportation problem of hazardous materials (hazmat) is proposed. This approach analyzes and assesses the risk in the terminals or storage facilities in the transport network. Hybrid techniques are inherently complex since they combine elements of different nature (quantitative and qualitative techniques). This hybrid approach is based on an event tree analysis (ETA) method, which makes use of a decision tree to logically develop the possible outcomes of an initiating event. This hybrid approach focuses on the interaction between hazmat and their danger characteristics in railroad terminals. ETA describes incidents from three different perspectives: induced incidents, incidents caused by external causes, and incidents caused by simultaneous and independent events. Incidents are modeled through conditional probabilities under normal conditions based on the records from PHMSA [1]. The results show that the magnitude of risk depends largely on the dangerousness level of the interaction among materials in the transport node and the time when external events happen. This approach is also proposed as a new tool to help the decision maker in transport networks to assess better the latent risk and magnitude of the incidents, when several dangerous materials are in a node at the same time.

This paper investigates the problem of scheduling a set of jobs on a single batching machine to minimize the maximum lateness, where jobs may be subject to precedence constraints and incompatibilities. Single batching machine scheduling has many applications, but this study is particularly motivated by single crane scheduling in an automated storage and retrieval system (AS/RS): given a set of transport requests, which requests should be processed together in the same dual command cycle, and in what order should the cycles be processed? Since storage and retrieval requests may refer to the same physical item, precedence constraints must be observed. Moreover, the crane may not be capable of handling multiple storage or retrieval requests in the same cycle, hence the need to account for incompatibilities. We present a novel exact algorithm based on branch & Benders cut, which is shown to solve even large instances with more than 100 jobs to optimality in many cases. For the special case without precedence constraints and incompatibilities, it improves on several best-known upper bounds from the literature.

The performance of the minimally invasive surgery (MIS) is enhanced by new Robotic surgical assistants (RSAs) because of the many advantages including small incisions, decreased blood loss, less pain, quicker heating time and the ability to pinpoint locations very precisely. In order to maximize therapeutic effects of the LITT (Laser interstitial thermal therapy) while minimizing side effects, thermal sensors need to be installed at the border between healthy and tumorous tissues. These thermal switches will send a signal to stop the heat process as soon as the temperature is exceeding a trigger. A mathematical formulation and a procedure is proposed that will help the physician prioritize the dosimetry locations and provide a safe dose per location. Such procedure which define the laser power distribution and the ablation position can be used for robot-assisted surgery. Such smart procedure will use a tissue damage prediction tool and bang-bang switch at the edges between healthy and unhealthy tissue to prevent side effect (laser ablation of the healthy tissue). We used a system on chip to control the robotic arm and laser led in order to proceed with the automatic LITT procedure.

International audience; Driven by climate change mitigation efforts, the wind energy industry has significantly increased in recent years. In this context, it is essential to make its exploitation cost-effective. Maintenance of wind turbines therefore plays an essential role reducing breakdowns and ensuring high productivity levels. In this paper we discuss a challenging maintenance scheduling problem rising in the onshore wind power industry. While the research in the field primarily focuses on condition-based maintenance strategies, we aim to address the problem on a short-term horizon considering wind predictions and fine-grained resource management. The objective is to find a maintenance plan that maximizes the revenue from the electricity production of the turbines while taking into account multiple task execution modes and task-technician assignment constraints. To solve this problem, we propose a constraint programming-based large neighborhood search (CPLNS) approach. We also propose two integer linear programming formulations that we solve using a commercial solver. We report results on randomly generated instances built with input from wind forecasting and maintenance scheduling software companies. The CPLNS shows an average gap of 1.2% with respect to the optimal solutions if known, or to the best upper bounds otherwise. These computational results demonstrate the overall efficiency of the proposed metaheuristic.

Canadian Armed Forces is a major contributor to domestic and international disaster relief missions characterizing complex operations demanding significant resources, including equipment, medical supplies, and food. For these operations to be successful, ensuring cost-effective and timely resource utilization and support is crucial. This paper describes the development of models and algorithms to improve distribution and inventory management of resources for disaster missions. A military three-echelon Supply Chain Network problem is specifically targeted. Challenges addressed and novelties of the models include: (a) integration of inventory management and distribution management, (b) simultaneously addressing several realistic features of supply chain management within one problem, (c) having an extended network that includes the different scales for transportation times, and (d) the intrinsic complexities of multiechelon, multi-period discrete optimization problems. Both deterministic and stochastic problems dimensions are addressed. This work is intended to provide advanced decision support tools to support disaster relief logistics military leaders. It is aimed at optimizing supply chain management resources utilization while reducing time and costs to achieve efficient supply delivery such as food, water, medicine and equipment.

In this study, we develop an analytical framework for personalizing the anticoagulation therapy of patients who are taking warfarin. Consistent with medical practice, our treatment design consists of two stages: (i) the initiation stage, modeled using a partially-observable Markov decision process, during which the physician learns through systematic belief updates about the unobservable patient sensitivity to warfarin, and (ii) the maintenance stage, modeled using a Markov decision process, during which the physician relies on his formed belief about patient sensitivity to determine the stable, patient-specific, warfarin dose to prescribe. We develop an expression for belief updates in the POMDP, establish the optimality of the myopic policy for the MDP, and derive conditions for the existence and uniqueness of a myopically optimal dose. We validate our models using a real-life patient data set gathered at the Hematology Clinic of the Jewish General Hospital in Montreal. The proposed analytical framework and case study enable us to develop useful clinical insights, for example, concerning the length of the initiation period and the importance of correctly assessing patient sensitivity.

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation-linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time. HighlightsWe provide reformulations for the quadratic minimum spanning tree problem.Two parallel branch-and-bound algorithms are implemented.For the first time, several instances are solved to proven optimality.

We introduce the integrative cooperative search method ( ICS ), a multi-thread cooperative search method for multi-attribute combinatorial optimization problems. ICS musters the combined capabilities of a number of independent exact or meta-heuristic solution methods. A number of these methods work on sub-problems defined by suitably selected subsets of decision-set attributes of the problem, while others combine the resulting partial solutions into complete ones and, eventually, improve them. All these methods cooperate through an adaptive search-guidance mechanism, using the central-memory cooperative search paradigm. Extensive numerical experiments explore the behavior of ICS and its interest through an application to the multi-depot, periodic vehicle routing problem, for which ICS improves the results of the current state-of-the-art methods.

We introduce a new vehicle routing problem class in which customers are divided into a number of customer zones defined through geographical or timing characteristics. The customers of each of these zones must be serviced within time windows by dedicated routes originating at associated supply points characterized by hard time windows and very limited waiting facilities, if any. A key feature of the problem is that a vehicle can be used to cover routes in different zones at different times. The objective is to minimize the total transportation cost to ensure that the customers are serviced on time and that vehicles arrive at the next customer zone just in time for the next assignment. The problem is addressed by a decomposition-based heuristic. Lower-bound procedures and benchmark problem instances are introduced, highlighting the satisfactory performance of the heuristic. Finally, a wide range of sensitivity analyses on several key parameters reveal interesting facets of the behavior of this new problem ...

We address a generalization of the asymmetric Traveling Salesman Problem where routes have to be constructed to satisfy customer requests, which either involve the pickup or delivery of a single commodity. A vehicle is to be routed such that the demand and the supply of the customers is satisfied under the objective to minimize the total distance traveled. The commodities which are collected from the pickup customers can be used to accommodate the demand of the delivery customers. In this paper, we present three mathematical formulations for this problem class and apply branch-and-cut algorithms to optimally solve the model formulations. For two of the models we derive Benders cuts based on the classical and the generalized Benders decomposition. Finally, we analyze the different mathematical formulations and associated solution approaches on well-known data sets from the literature.

In this article, we address a real life optimization problem, the rail track inspection scheduling problem. This problem consists of scheduling railway network inspection tasks. The objective is to minimize the total deadhead distance while performing all inspection tasks. Different 0-1 integer formulations for the problem are presented. A heuristic based on both Benders and Dantzig-Wolfe decompositions is proposed to solve this rich arc routing problem. Its performance is analyzed on a real life dataset provided by the French national railway company. The proposed algorithm is compared to a dynamic programming-based heuristic. Its ability to schedule the inspection tasks of 1 year on a sparse graph with thousand nodes and arcs is assessed. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 661, 40-56 2015

This paper presents two-stage bi-objective stochastic programming models for disaster relief operations. We consider a problem that occurs in the aftermath of a natural disaster: a transportation system for supplying disaster victims with relief goods must be established. We propose bi-objective optimization models with a monetary objective and humanitarian objective. Uncertainty in the accessibility of the road network is modeled by a discrete set of scenarios. The key features of our model are the determination of locations for intermediate depots and acquisition of vehicles. Several model variants are considered. First, the operating budget can be fixed at the first stage for all possible scenarios or determined for each scenario at the second stage. Second, the assignment of vehicles to a depot can be either fixed or free. Third, we compare a heterogeneous vehicle fleet to a homogeneous fleet. We study the impact of the variants on the solutions. The set of Pareto-optimal solutions is computed by applying the adaptive Epsilon-constraint method. We solve the deterministic equivalents of the two-stage stochastic programs using the MIP-solver CPLEX.

In this paper, we consider tactical planning for a class of multi-period vehicle routing problems (MPVRP). This problem involves optimizing daily product collections from several production locations over a given planning horizon. In this context, a single routing plan for the whole horizon must be prepared, and the seasonal variations in the producers' supplies must be taken into account. Production variations over the horizon are approximated using a sequence of periods, each corresponding to a production season, while the intra-period variations are neglected. We propose a mathematical model that is based on the two-stage a priori optimization paradigm. The first stage corresponds to the design of a plan which, in the second stage, takes the different periods into account. The proposed set partitioning-based formulation is solved using a branch-and-price approach. The subproblem is a multi-period elementary shortest path problem with resource constraints (MPESPPRC), for which we propose an adaptation of the dynamic-programming-based label-correcting algorithm. Computational results show that this approach is able to solve instances with up to 60 producers and five periods.