Analysis of evolutionary algorithms for constrained routing problems /

Download
2004
Demir, Erdem
This study focuses on two types of routing problems based on standard Traveling Salesman Problem, which are TSP with pickup and delivery (TSPPD) and TSP with backhauls (TSPB). In both of these problems, there are two types of customers, i.e. أdelivery customersؤ demanding goods from depot and أpickup customersؤ sending goods to depot. The objective is to minimize the cost of the tour that visits every customer once without violating the side constraints. In TSPB, delivery customers should precede the pickup customers, whereas the vehicle capacity should not be exceeded in TSPPD. The aim of the study is to propose good Evolutionary Algorithms (EA) for these two problems and also analyze the adaptability of an EA, originally designed for the standard TSP, to the problems with side constraints. This effort includes commenting on the importance of feasibility of the solutions in the population with respect to these side constraints. Having this in mind, different EA strategies involving feasible or infeasible solutions are designed. These strategies are compared by quantitative experiments realized over a set of problem instances and the results are given.

Suggestions

Optimization of time-cost-resource trade-off problems in project scheduling using meta-heuristic algorithms
Bettemir, Önder Halis; Sönmez, Rifat; Department of Civil Engineering (2009)
In this thesis, meta-heuristic algorithms are developed to obtain optimum or near optimum solutions for the time-cost-resource trade-off and resource leveling problems in project scheduling. Time cost trade-off, resource leveling, single-mode resource constrained project scheduling, multi-mode resource constrained project scheduling and resource constrained time cost trade-off problems are analyzed. Genetic algorithm simulated annealing, quantum simulated annealing, memetic algorithm, variable neighborhood ...
Dissimilarity maximization method for real-time routing of parts in random flexible manufacturing systems
Saygin, C; Kilic, SE (Springer Science and Business Media LLC, 2004-04-01)
This paper presents a dissimilarity maximization method (DMM) for real-time routing selection and compares it via simulation with typical priority rules commonly used in scheduling and control of flexible manufacturing systems (FMSs). DMM aims to reduce the congestion in the system by selecting a routing for each part among its alternative routings such that the overall dissimilarity among the selected routings is maximized. In order to evaluate the performance of DMM, a random FMS, where the product mix is...
Using System Dynamics for Strategic Performance Management in Construction
Yildiz, Acelya Ecem; Dikmen Toker, İrem; Birgönül, Mustafa Talat (American Society of Civil Engineers (ASCE), 2020-03-01)
Balanced scorecard (BSC) and strategy maps (SMs) are among the most popular strategic performance management methods that have been proposed in the literature to define, analyze, and monitor performance and strategies. Despite their popularity, BSC and SMs have been criticized for their inability to simulate dynamic interrelations between performance measures and strategies over time. In this paper, a dynamic SM was developed by using system dynamics (SD) modeling based on the BSC framework. This paper desc...
Multi-objective combinatorial optimization using evolutionary algorithms
Özsayın, Burcu; Köksalan, Murat; Department of Industrial Engineering (2009)
Due to the complexity of multi-objective combinatorial optimization problems (MOCO), metaheuristics like multi-objective evolutionary algorithms (MOEA) are gaining importance to obtain a well-converged and well-dispersed Pareto-optimal frontier approximation. In this study, of the well-known MOCO problems, single-dimensional multi-objective knapsack problem and multi-objective assignment problem are taken into consideration. We develop a steady-state and elitist MOEA in order to approximate the Pareto-optim...
Analysis of a deterministic demand production/inventory system under nonstationary supply uncertainty
Gullu, R; Onol, E; Erkip, N (Informa UK Limited, 1997-08-01)
In this article we investigate a periodic review inventory model under deterministic dynamic demand and supply unavailability. In a given period, supply is either available or completely unavailable with given probabilities. Supply unavailability probabilities are nonstationary over time. We show the optimality of an order-up-to level policy, and obtain a newsboy-like formula that determines the optimal order-up-to levels. Our formula would provide guidence as to the appropriate amount of inventory to stock...
Citation Formats
E. Demir, “Analysis of evolutionary algorithms for constrained routing problems /,” M.S. - Master of Science, Middle East Technical University, 2004.