• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 54
  • 31
  • 18
  • 6
  • 2
  • 2
  • 1
  • Tagged with
  • 130
  • 130
  • 44
  • 42
  • 37
  • 36
  • 36
  • 36
  • 30
  • 28
  • 27
  • 24
  • 22
  • 21
  • 19
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

A set-covering based heuristic algorithm for the periodic vehicle routing problem

Cacchiani, Valentina, Hemmelmayr, Vera, Tricoire, Fabien 30 January 2014 (has links) (PDF)
We present a hybrid optimization algorithm for mixed-integer linear programming, embedding both heuristic and exact components. In order to validate it we use the periodic vehicle routing problem (PVRP) as a case study. This problem consists of determining a set of minimum cost routes for each day of a given planning horizon, with the constraints that each customer must be visited a required number of times (chosen among a set of valid day combinations), must receive every time the required quantity of product, and that the number of routes per day (each respecting the capacity of the vehicle) does not exceed the total number of available vehicles. This is a generalization of the well-known vehicle routing problem (VRP). Our algorithm is based on the linear programming (LP) relaxation of a set-covering-like integer linear programming formulation of the problem, with additional constraints. The LP-relaxation is solved by column generation, where columns are generated heuristically by an iterated local search algorithm. The whole solution method takes advantage of the LP-solution and applies techniques of fixing and releasing of the columns as a local search, making use of a tabu list to avoid cycling. We show the results of the proposed algorithm on benchmark instances from the literature and compare them to the state-of-the-art algorithms, showing the effectiveness of our approach in producing good quality solutions. In addition, we report the results on realistic instances of the PVRP introduced in Pacheco et al. (2011) [24] and on benchmark instances of the periodic traveling salesman problem (PTSP), showing the efficacy of the proposed algorithm on these as well. Finally, we report the new best known solutions found for all the tested problems. (authors' abstract)
2

A Study On The Split Delivery Vehicle Routing Problem

Liu, Kai 10 December 2005 (has links)
This dissertation examines the Split Delivery Vehicle Routing Problem (SDVRP), a relaxed version of classical capacitated vehicle routing problem (CVRP) in which the demand of any client can be split among the vehicles that visit it. We study both scenarios of the SDVRP in this dissertation. For the SDVRP with a fixed number of the vehicles, we provide a Two-Stage algorithm. This approach is a cutting-plane based exact method called Two-Stage algorithm in which the SDVRP is decomposed into two stages of clustering and routing. At the first stage, an assignment problem is solved to obtain some clusters that cover all demand points and get the lower bound for the whole problem; at the second stage, the minimal travel distance of each cluster is calculated as a traditional Traveling Salesman Problem (TSP), and the upper bound is obtained. Adding the information obtained from the second stage as new cuts into the first stage, we solve the first one again. This procedure stops when there are no new cuts to be created from the second stage. Several valid inequalities have been developed for the first stage to increase the computational speed. A valid inequality is developed to completely solve the problem caused by the index of vehicles. Another strong valid inequality is created to provide a valid distance lower bound for each set of demand points. This algorithm can significantly outperform other exact approaches for the SDVRP in the literature. If the number of the vehicles in the SDVRP is a variable, we present a column generation based branch and price algorithm. First, a restricted master problem (RMP) is presented, which is composed of a finite set of feasible routes. Solving the linear relaxation of the RMP, values of dual variables are thus obtained and passed to the sub-problem, the pricing problem, to generate a new column to enter the base of the RMP and solve the new RMP again. This procedure repeats until the objective function value of the pricing problem is greater than or equal to zero (for minimum problem). In order to get the integer feasible (optimal) solution, a branch and bound algorithm is then performed. Since after branching, it is not guaranteed that the possible favorable column will appear in the master problem. Therefore, the column generation is performed again in each node after branching. The computational results indicate this approach is promising in solving the SDVRP in which the number of the vehicles is not fixed.
3

Mathematical Programming Algorithms for Reliable Routing and Robust Evacuation Problems

Andreas, April Kramer January 2006 (has links)
Most traditional routing problems assume perfect operability of all arcs and nodes. However, when independent arc failure probabilities exist, a secondary objective must be present to retain some measure of expected functionality. We first briefly consider the reliability-constrained single-path problem, where we look for the lowest cost path that meets a reliability side constraint. This analysis enables us to then examine the reliability-constrained two-path problem, which seeks to establish two minimum-cost paths between a source and destination node wherein at least one path must remain fully operable with some threshold probability. We consider the case in which both paths must be arc-disjoint and the case in which arcs can be shared between the paths. We prove both problems to be NP-hard. We examine strategies for solving the resulting nonlinear integer program, including pruning, coefficient tightening, lifting, and branch-and-bound partitioning schemes. Next, we consider the reliable h-path routing problem, which seeks a minimum-cost set of h ≥ 2 arc-independent paths between a source and destination node, such that the probability that at least one path remains operational is sufficiently large. Our prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. We propose two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms. Finally, we examine the robust design of an evacuation tree, in which evacuation is subject to capacity restrictions on arcs. Given a discrete set of disaster scenarios with varying network populations, arc capacities, transit times, and time-dependent penalty functions, we seek to establish an optimal a priori evacuation tree that minimizes the expected evacuation penalty. The solution strategy is based on Benders decomposition, and we provide effcient methods for obtaining primal and dual sub-problem solutions. We analyze techniques for strengthening the master problem formulation, thus reducing the number of master problem solutions required for the algorithm's convergence.
4

Advances in interior point methods and column generation

González Brevis, Pablo January 2013 (has links)
In this thesis we study how to efficiently combine the column generation technique (CG) and interior point methods (IPMs) for solving the relaxation of a selection of integer programming problems. In order to obtain an efficient method a change in the column generation technique and a new reoptimization strategy for a primal-dual interior point method are proposed. It is well-known that the standard column generation technique suffers from unstable behaviour due to the use of optimal dual solutions that are extreme points of the restricted master problem (RMP). This unstable behaviour slows down column generation so variations of the standard technique which rely on interior points of the dual feasible set of the RMP have been proposed in the literature. Among these techniques, there is the primal-dual column generation method (PDCGM) which relies on sub-optimal and well-centred dual solutions. This technique dynamically adjusts the column generation tolerance as the method approaches optimality. Also, it relies on the notion of the symmetric neighbourhood of the central path so sub-optimal and well-centred solutions are obtained. We provide a thorough theoretical analysis that guarantees the convergence of the primal-dual approach even though sub-optimal solutions are used in the course of the algorithm. Additionally, we present a comprehensive computational study of the solution of linear relaxed formulations obtained after applying the Dantzig-Wolfe decomposition principle to the cutting stock problem (CSP), the vehicle routing problem with time windows (VRPTW), and the capacitated lot sizing problem with setup times (CLSPST). We compare the performance of the PDCGM with the standard column generation method (SCGM) and the analytic centre cutting planning method (ACCPM). Overall, the PDCGM achieves the best performance when compared to the SCGM and the ACCPM when solving challenging instances from a column generation perspective. One important characteristic of this column generation strategy is that no speci c tuning is necessary and the algorithm poses the same level of difficulty as standard column generation method. The natural stabilization available in the PDCGM due to the use of sub-optimal well-centred interior point solutions is a very attractive feature of this method. Moreover, the larger the instance, the better is the relative performance of the PDCGM in terms of column generation iterations and CPU time. The second part of this thesis is concerned with the development of a new warmstarting strategy for the PDCGM. It is well known that taking advantage of the previously solved RMP could lead to important savings in solving the modified RMP. However, this is still an open question for applications arising in an integer optimization context and the PDCGM. Despite the current warmstarting strategy in the PDCGM working well in practice, it does not guarantee full feasibility restorations nor considers the quality of the warmstarted iterate after new columns are added. The main motivation of the design of the new warmstarting strategy presented in this thesis is to close this theoretical gap. Under suitable assumptions, the warmstarting procedure proposed in this thesis restores primal and dual feasibilities after the addition of new columns in one step. The direction is determined so that the modi cation of small components at a particular solution is not large. Additionally, the strategy enables control over the new duality gap by considering an expanded symmetric neighbourhood of the central path. As observed from our computational experiments solving CSP and VRPTW, one can conclude that the warmstarting strategies for the PDCGM are useful when dense columns are added to the RMP (CSP), since they consistently reduce the CPU time and also the number of iterations required to solve the RMPs on average. On the other hand, when sparse columns are added (VRPTW), the coldstart used by the interior point solver HOPDM becomes very efficient so warmstarting does not make the task of solving the RMPs any easier.
5

Stochastic ship fleet routing with inventory limits

Yu, Yu January 2010 (has links)
This thesis describes a stochastic ship routing problem with inventory management. The problem involves finding a set of least costs routes for a fleet of ships transporting a single commodity when the demand for the commodity is uncertain. Storage at consumption and supply ports is limited and inventory levels are monitored in the model. Consumer demands are at a constant rate within each time period in the deterministic problem, and in the stochastic problem, the demand rate for a period is not known until the beginning of that period. The demand situation in each time period can be described by a scenario tree with corresponding probabilities. Several possible solution approaches for solving the problem are studied in the thesis. This problem can be formulated as a mixed integer programming (MIP) model. However solving the problem this way is very time consuming even for a deterministic problem with small problem size. In order to solve the stochastic problem, we develop a decomposition formulation and solve it using a Branch and Price framework. A master problem (set partitioning with extra inventory constraints) is built, and the subproblems, one for each ship, involve solving stochastic dynamic programming problems to generate columns for the master problem. Each column corresponds to one possible tree of schedules for one ship giving the schedule for the ship for all demand scenarios. In each branch-and-bound node, the node problem is solved by iterating between the master problem and the subproblems. Dual variables can be obtained solving the master problem and are used in the subproblems to generate the most promising columns for the master problem. Computational results are given showing that medium sized problems can be solved successfully. Several extensions to the original model are developed, including a variable speed model, a diverting model, and a model which allows ships to do extra tasks in return for a bonus. Possible solution approaches for solving the variable speed and the diverting model are presented and computational results are given.
6

Computational evaluation of a novel approach to process planning for circuit card assembly on dual head placement machines

Chowdhury, Nilanjan Dutta 12 April 2006 (has links)
Dual head placement machines are commonly used in industry for placing components on circuit cards with great speed and accuracy. This thesis evaluates a novel approach for prescribing process plans for circuit card assembly on dual head placement machines. Process planning involves assigning component types to heads and to feeder slots associated with each head and prescribing appropriate sequences of picking, placing and nozzle-changing steps. The approach decomposes these decisions into four inter-related problems: P1, P2, P3 and P4. This thesis reviews this approach; presents a new heuristic to address P1; a method to facilitate P2 and P3 solutions; a method to control nozzle changes in P4; tests approaches to P1, P2, P3 and P4; and presents a thorough analysis of computational results to evaluate the efficacy of the approach which aims to balance workloads on machine heads to maximize assembly line throughput.
7

The dynamic, resource-constrained shortest path problem on an acyclic graph with application in column generation and literature review on sequence-dependent scheduling

Zhu, Xiaoyan 25 April 2007 (has links)
This dissertation discusses two independent topics: a resource-constrained shortest-path problem (RCSP) and a literature review on scheduling problems involving sequence-dependent setup (SDS) times (costs). RCSP is often used as a subproblem in column generation because it can be used to solve many practical problems. This dissertation studies RCSP with multiple resource constraints on an acyclic graph, because many applications involve this configuration, especially in column genetation formulations. In particular, this research focuses on a dynamic RCSP since, as a subproblem in column generation, objective function coefficients are updated using new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic graph with the goal of effectively reoptimizing RCSP in the context of column generation. This method uses a one-time “preliminary” phase to transform RCSP into an unconstrained shortest path problem (SPP) and then solves the resulting SPP after new values of dual variables are used to update objective function coefficients (i.e., reduced costs) at each iteration. Network reduction techniques are considered to remove some nodes and/or arcs permanently in the preliminary phase. Specified techniques are explored to reoptimize when only several coefficients change and for dealing with forbidden and prescribed arcs in the context of a column generation/branch-and-bound approach. As a benchmark method, a label-setting algorithm is also proposed. Computational tests are designed to show the effectiveness of the proposed algorithms and procedures. This dissertation also gives a literature review related to the class of scheduling problems that involve SDS times (costs), an important consideration in many practical applications. It focuses on papers published within the last decade, addressing a variety of machine configurations - single machine, parallel machine, flow shop, and job shop - reviewing both optimizing and heuristic solution methods in each category. Since lot-sizing is so intimately related to scheduling, this dissertation reviews work that integrates these issues in relationship to each configuration. This dissertation provides a perspective of this line of research, gives conclusions, and discusses fertile research opportunities posed by this class of scheduling problems. since, as a subproblem in column generation, objective function coefficients are updated using new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic graph with the goal of effectively reoptimizing RCSP in the context of column generation. This method uses a one-time
8

Dynamic optimization of airspace sector grouping

Treimuth, Tambet 19 January 2018 (has links) (PDF)
The current airspace configuration is highly structured, fixed and is less responsive to changes causing the overall system to lack the flexibility, adaptability, and responsibility needed to handle the increasing air traffic demands in the near future. The work presented in this thesis aims at improving the flexibility and adaptability of today's airspace management in Europe in a pretactical context. We focus on the development of a method to support a process of automatic generation of a sequence of sector configurations composed of predefined sectors. Airspace configurations should be dynamically adjusted to provide maximum efficiency and flexibility in response to demand fluctuations. We dynamically build configurations by combining existing elementary sectors. In this step, any sector combination which forms controllable airspace blocks is eligible and may be used during the day of operation. In this work, we developed efficient methods to solve DAC problem. We formulated and study the sectorization problem from an algorithmic point of view. We proposed methods based on a mathematical modeling and heuristic optimization techniques. We also introduced here an approach to evaluate the workload inside sectors.
9

Lot streaming in a two-stage assembly system and a hybrid flow shop

Cheng, Ming 10 October 2012 (has links)
In this dissertation, we investigate the use of lot streaming in a two-stage assembly system and a two-stage hybrid flow shop in order to improve system performance. Lot streaming accelerates the flow of a production lot through a production process by splitting it into sublots, and then, processing these sublots in an overlapping fashion over the machines, thereby reducing work-in-process and cycle-time. Traditionally, lot streaming has been applied to problems in various flow shop machine configurations. It has also been applied to machine environments of job shop, open shop, and parallel machines. Its application to assembly system is relatively new. The two-stage assembly system that we consider consists of multiple suppliers at Stage 1 with each supplier producing one type of a subassembly (or a component), and one or more assembly locations at Stage 2, where the subassemblies are then put together. Lot-attached and sublot-attached setup time and cost are encountered on the machines at both the stages, and sublot-attached time and cost are encountered for the transfer of sublots from Stage 1 to Stage 2. Mass customization is an example of such a system in which the final assembly of a product is postponed to capture specific customer demands. Dell Computer constitutes a real-life example of this system. A customer picks his/her computer processor, memory, storage, and other equipment, on Dell's web site. Dell's supply chain is configured to obtain subassemblies from suppliers (stage 1), and then, to assemble the requisite systems in different market areas (stage 2). This enables a reduction in operating cost while improving responsiveness to customers. The problem that we address is as follows: Given a maximum number of sublots of each lot, determine the number of sublots to use (assuming equal sublot sizes), and also, the sequence in which to process the lots, in order to minimize two criteria, namely, makespan, total cost. We propose two column generation-based methods that rely on different decomposition schemes. The results of our computational investigation conducted by using randomly generated data sets reveal that the proposed column generation methods obtain solutions in a few seconds of CPU time while the direct solution by CPLEX of a mixed integer programming model of the problem requires much larger CPU times. For the hybrid flow shop lot streaming problem, the machine configuration that we consider consists of one machine at Stage 1 and two machines at Stage 2 (designated as 1+2 system). A single lot is to be processed in the system, and the objective is to minimize the makespan. A removal time is associated with each sublot at Stage 1. We present a mixed integer programming model for this problem to determine optimal number of sublots and sublot sizes. First, we consider the case of a given number of sublots for which we develop closed-form expressions to obtain optimal, continuous sublot sizes. Then, we consider determination of optimal number of sublots in addition to their sizes. We develop an upper bound on optimal number of sublots, and use a simple search procedure in conjunction with the closed-form expressions for sublot sizes to obtain an optimal solution. We also consider the problem of determining integer sublot sizes, and propose a heuristic method that directly solves the mixed integer programming model after having fixed values of appropriate variables. The results of our numerical experimentation reveal the efficacy of the proposed method to obtain optimal, continuous sublot sizes, and also, that of the proposed heuristic method to obtain integer sublot sizes, which are within 0.2% of optimal solutions for the testbed of data used, each obtained within a few seconds of CPU time. The last problem that we address is an extension of the single-lot lot streaming problem for a $1+2$ hybrid flow shop considered above to the case of multiple lots, where each lot contains items of a unique product type. We consider two objectives: minimize makespan, and minimize the sum of the completion times for all the lots. The consideration of multiple lots introduces a complicating issue of sequencing the lots. We use the results derived for the single-lot problem and develop effective heuristic methods for this problem. The results of our computational investigation on the use of different heuristic methods reveal their efficacy in solving this problem. / Ph. D.
10

Simulation Of Random Set Covering Problems With Known Optimal Solutions And Explicitly Induced Correlations Amoong Coefficients

Sapkota, Nabin 01 January 2006 (has links)
The objective of this research is to devise a procedure to generate random Set Covering Problem (SCP) instances with known optimal solutions and correlated coefficients. The procedure presented in this work can generate a virtually unlimited number of SCP instances with known optimal solutions and realistic characteristics, thereby facilitating testing of the performance of SCP heuristics and algorithms. A four-phase procedure based on the Karush-Kuhn-Tucker (KKT) conditions is proposed to generate SCP instances with known optimal solutions and correlated coefficients. Given randomly generated values for the objective function coefficients and the sum of the binary constraint coefficients for each variable and a randomly selected optimal solution, the procedure: (1) calculates the range for the number of possible constraints, (2) generates constraint coefficients for the variables with value one in the optimal solution, (3) assigns values to the dual variables, and (4) generates constraint coefficients for variables with value 0 in the optimal solution so that the KKT conditions are satisfied. A computational demonstration of the procedure is provided. A total of 525 SCP instances are simulated under seven correlation levels and three levels for the number of constraints. Each of these instances is solved using three simple heuristic procedures. The performance of the heuristics on the SCP instances generated is summarized and analyzed. The performance of the heuristics generally worsens as the expected correlation between the coefficients increases and as the number of constraints increases. The results provide strong evidence of the benefits of the procedure for generating SCP instances with correlated coefficients, and in particular SCP instances with known optimal solutions.

Page generated in 0.1589 seconds