Search

This paper attempts to provide some insight into the structure of' a large class of fleet scheduling problems. Scheduling under fixed due date constraints is shown to be easily solved using a new formulation of the problem. Scheduling under flexible due date constraints is shown to be inherently complex, and strong evidence is given for asserting that no efficient (polynomial bounded) algorithm, exists for solving this problem exactly. A fast heuristic approach is described which has worked well in some school bus scheduling applications. [ABSTRACT FROM AUTHOR]

This article studies a capacitated fixed-charge multiperiod location–transportation problem in which, while the location and capacity of each facility must be determined immediately, the determination of the final production and distribution of products can be delayed until actual orders are received in each period. In contexts where little is known about future demand, robust optimization, namely using a budgeted uncertainty set, becomes a natural method for identifying meaningful decisions. Unfortunately, it is well known that these types of multiperiod robust decision problems are computationally intractable. To overcome this difficulty, we propose a set of tractable conservative approximations for the problem that each exploit to a different extent the idea of reducing the flexibility of the delayed decisions. While all of these approximation models outperform previous approximation models that have been proposed for this problem, each also has the potential to reach a different level of compromise between efficiency of resolution and quality of the solution. A row generation algorithm is also presented to address problem instances of realistic size. We also demonstrate that full flexibility is often unnecessary to reach nearly, or even exact, optimal robust locations and capacities for the facilities. Finally, we illustrate our findings with an extensive numerical study where we evaluate the effect of the amount of uncertainty on the performance and structure of each approximate solution that can be obtain d. [ABSTRACT FROM AUTHOR]

We study an emergency response network design problem that integrates relief (supply) and evacuation (demand) sides under disaster location and intensity uncertainties which, in turn, dictate uncertainty in terms of the location and amount of demand. Representing these uncertainties by discrete scenarios, we present a stochastic programming framework in which two second stage objectives, the average and worst case costs, are combined. In our model, we minimize, over all of the scenarios, the fixed costs of opening supply centers and shelters, and the weighted sum of average and worst case flow costs. Thus, the model gives the decision maker the flexibility to put relative emphasis on the worst case and average flow cost minimization and explore outcomes in terms of total costs and network configurations. To solve large scale instances with varying relative weights, we devise alternative Benders Decomposition approaches. We implement these by using an advanced callback feature of the solver while simultaneously incorporating several performance-enhancing steps that help to improve runtimes significantly. We conduct a detailed computational study to highlight the efficiency of our proposed solution methodology. Furthermore, we apply our approach in a realistic case study based on Geographical Information Systems data on coastal Texas and present interesting insights about the problem and the resulting network structures for varying weights assigned to objectives. [ABSTRACT FROM AUTHOR]