The last mile delivery in humanitarian relief supply often happens on a tree or an almost-tree network allowing split deliveries. We present a relief delivery model incorporating a tree network for last mile delivery....
详细信息
The last mile delivery in humanitarian relief supply often happens on a tree or an almost-tree network allowing split deliveries. We present a relief delivery model incorporating a tree network for last mile delivery. We developed a mixedintegerprogramming (MIP) formulation with the goal of minimizing the unsatisfied demand of the population. For better computational performance, we reformulated the MIP exploiting the tree network structure and found that this gave an order of magnitude reduction in computational time. To further improve computational efficiency, we developed a heuristic solution method based on a decomposition scheme applied to the tree network formulation. This led to the Capacitated Vehicle Routing Problem on trees with split deliveries, for which we derived a closed-form solution. This decomposition scheme resulted in a further order of magnitude reduction in computation time. To demonstrate the application of our approach we applied our model to the humanitarian logistics relief operation encountered in the 2015 Nepal earthquake.
In this paper we study resilience of TDMA-based wireless sensor networks to node failures. We investigate exploiting mutlicast routing for providing redundancy in the number of gateways used by data streams, so as to ...
详细信息
In this paper we study resilience of TDMA-based wireless sensor networks to node failures. We investigate exploiting mutlicast routing for providing redundancy in the number of gateways used by data streams, so as to protect them against gateway failures. To do this, we develop an optimization model aiming at packet traffic throughput maximization composed of three mixed-integer programming problem formulations and corresponding solution algorithms. The first formulation assumes predefined multicast routing trees and fixed gateway locations, and optimizes the TDMA frame composition. The second one adds routing trees optimization, while the third formulation additionally includes optimization of gateway locations. We present a numerical study illustrating effectiveness of our model, including efficiency of the solution algorithms. Our results show that substantial gains in traffic throughput can be obtained by including routing trees optimization and optimal gateways selection, especially for high levels of redundancy. (c) 2020 Elsevier B.V. All rights reserved.
In real world maritime routing problems, many restrictions and regulations influence the daily operations. The effects of several of these restrictions have not yet been studied in depth from an operations research pe...
详细信息
In real world maritime routing problems, many restrictions and regulations influence the daily operations. The effects of several of these restrictions have not yet been studied in depth from an operations research perspective. This paper introduces the problem of allocating bulk cargoes to tanks in maritime shipping. A model and several variations are presented, and it is shown that the main problem consists of a number of complicating constraints. The problem studied is crucial when determining whether a given route is feasible for a given ship, and computational experiments are performed to assess the difficulty of solving realistically sized instances. The proposed formulation is hoped to provide a suitable starting point for research on stowage problems in maritime bulk shipping. (C) 2009 Elsevier Ltd. All rights reserved.
In this paper, we study the problem of technical transient gas network optimization, which can be considered a minimum cost flow problem with a nonlinear objective function and additional nonlinear constraints on the ...
详细信息
In this paper, we study the problem of technical transient gas network optimization, which can be considered a minimum cost flow problem with a nonlinear objective function and additional nonlinear constraints on the network arcs. Applying an implicit box scheme to the isothermal Euler equation, we derive a mixed-integer nonlinear program. This is solved by means of a combination of (i) a novel mixed-integer linear programming approach based on piecewise linearization and (ii) a classical sequential quadratic program applied for given combinatorial constraints. Numerical experiments show that better approximations to the optimal control problem can be obtained by using solutions of the sequential quadratic programming algorithm to improve the mixed-integer linear program. Moreover, iteratively applying these two techniques improves the results even further.
We study the resource loading problem, which arises in tactical capacity planning. In this problem, one has to plan the intensity of execution of a set of orders to minimize a cost function that penalizes the resource...
详细信息
We study the resource loading problem, which arises in tactical capacity planning. In this problem, one has to plan the intensity of execution of a set of orders to minimize a cost function that penalizes the resource use above given capacity limits and the completion of the orders after their due dates. Our main contributions include a novel mixed-integer linear-programming (MIP)-based formulation, the investigation of the polyhedra associated with the feasible intensity assignments of individual orders, and a comparison of our branch-and-cut algorithm based on the novel formulation and the related polyhedral results with other MIP formulations. The computational results demonstrate the superiority of our approach. In our formulation and in one of the proofs, we use fundamental results of Egon Balas on disjunctive programming.
In this study, we aim to minimize the total waiting time between successive treatments for inpatients in rehabilitation hospitals (departments) during a working day. Firstly, the daily treatment scheduling problem is ...
详细信息
In this study, we aim to minimize the total waiting time between successive treatments for inpatients in rehabilitation hospitals (departments) during a working day. Firstly, the daily treatment scheduling problem is formulated as a mixed-integer linear programming model, taking into consideration real-life requirements, and is solved by Gurobi, a commercial solver. Then, an improved cuckoo search algorithm is developed to obtain good quality solutions quickly for large-sized problems. Our methods are demonstrated with data collected from a medium-sized rehabilitation hospital in China. The numerical results indicate that the improved cuckoo search algorithm outperforms the real schedules applied in the targeted hospital with regard to the total waiting time of inpatients. Gurobi can construct schedules without waits for all the tested dataset though its efficiency is quite low. Three sets of numerical experiments are executed to compare the improved cuckoo search algorithm with Gurobi in terms of solution quality, effectiveness and capability to solve large instances.
This paper presents an optimization based mathematical modelling approach for a single source single destination crude oil facility location transshipment problem. We began by formulating a mixed-integer nonlinear pro...
详细信息
This paper presents an optimization based mathematical modelling approach for a single source single destination crude oil facility location transshipment problem. We began by formulating a mixed-integer nonlinear programming model and use a rolling horizon heuristic to find an optimal location for a storage facility within a restricted continuous region. We next design a hybrid two-stage algorithm that combines judicious facility locations resulting from the proposed model into a previously developed column generation approach. The results indicate that improved overall operational costs can be achieved by strategically determining cost-effective locations of the transshipment facility.
A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas su...
详细信息
A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems.
In this paper, we study the decision process of assigning elective surgery patients to available surgical blocks in multiple operating rooms (OR) under random surgery durations, random postoperative length-of-stay in ...
详细信息
In this paper, we study the decision process of assigning elective surgery patients to available surgical blocks in multiple operating rooms (OR) under random surgery durations, random postoperative length-of-stay in the intensive care unit (ICU), and limited capacity of ICU. The probability distributions of random parameters are assumed to be ambiguous, and only the mean values and ranges are known. We propose a distributionally robust elective surgery scheduling (DRESS) model that seeks optimal surgery scheduling decisions to minimize the cost of performing and postponing surgeries and the worst-case expected costs associated with overtime and idle time of ORs and lack of ICU capacity (which causes premature discharges or transfers). We evaluate the worst-case over a family of distributions characterized by the known mean values and ranges of random parameters. We leverage the separability of DRESS formulation in deriving an exact mixed-integer nonlinear programming reformulation. We linearize and derive a family of symmetry breaking inequalities to improve the solvability of the reformulation using an adapted column-and-constraint generation algorithm. Finally, we conduct extensive numerical experiments that demonstrate the superior performance of our DR approach as compared to the stochastic programming approach, and provide insights into DRESS. (C) 2020 Elsevier B.V. All rights reserved.
In this paper, we modify Benders' decomposition method by using concepts from the Reformulation-Linearization Technique (RLT) and lift-and-project cuts in order to develop an approch for solving discrete optimizat...
详细信息
In this paper, we modify Benders' decomposition method by using concepts from the Reformulation-Linearization Technique (RLT) and lift-and-project cuts in order to develop an approch for solving discrete optimization problems that yield integral subproblems, such as those that arise in the case of two-stage stochastic programs with integer recourse. We first demonstrate that if a particular convex hull representation of the problem's constrained region is available when binariness is enforced on only the second-stage (or recourse) variables, then the regular Benders' algorithm is applicable. The proposed procedure is based on sequentially generating a suitable partial description of this convex hull representation as needed in the process of deriving valid Benders' cuts. The key idea is to solve the subproblems using an RLT or lift-and-project cutting plane scheme, but to generate and store the cuts as functions of the first-stage variables. Hence, we are able to re-use these cutting planes from one subproblem solution to the next simply by updating the values of the first-stage decisions. The proposed Benders' cuts also recognize these RLT or lift-and-project cuts as functions of the first-stage variables, and are hence shown to be globally valid, thereby leading to an overall finitely convergent solution procedure. Some illustrative examples are provided to elucidate the proposed approach. The focus of this paper is on developing such a finitely convergent Benders' approach for problems having 0-1 mixed-integer subproblems as in the aforementioned context of two-stage stochastic programs with integer recourse. A second part of this paper will deal with related computational experiments.
暂无评论