University of Tennessee, Knoxville TRACE: Tennessee Research and Creative Exchange Doctoral Dissertations Graduate School 8-2012 Solving Combinatorial Optimization Problems Using Genetic Algorithms and Ant Colony Optimization Gautham Puttur Rajappa grajappa@utk.edu Follow this and additional works at: https://trace.edu/utk_graddiss Part of the Industrial Engineering Commons, Operational Research Commons, and the Other Operations Research, Systems Engineering and Industrial Engineering Commons Recommended Citation Rajappa, Gautham Puttur, "Solving Combinatorial Optimization Problems Using Genetic Algorithms and Ant Colony Optimization., University of Tennessee, 2012.edu/utk_graddiss/1478 This Dissertation is brought to you for free and open access by the Graduate School at TRACE: Tennessee Research and Creative Exchange. It has been accepted for inclusion in Doctoral Dissertations by an authorized administrator of TRACE: Tennessee Research and Creative Exchange. For more information, please contact trace@utk. To the Graduate Council: I am submitting herewith a dissertation written by Gautham Puttur Rajappa entitled "Solving Combinatorial Optimization Problems Using Genetic Algorithms and Ant Colony Optimization." I have examined the final electronic copy of this dissertation for form and content and recommend that it be accepted in partial fulfillment of the requirements for the degree of Doctor of Philosophy, with a major in Industrial Engineering.Wilck, Major Professor We have read this dissertation and recommend its acceptance: Charles Noon, Xueping Li, Xiaoyan Zhu Accepted for the Council: Carolyn R.
Hodges Vice Provost and Dean of the Graduate School (Original signatures are on file with official student records.) Solving Combinatorial Optimization Problems Using Genetic Algorithms and Ant Colony Optimization A Dissertation Presented for the Doctor of Philosophy Degree The University of Tennessee, Knoxville Gautham Puttur Rajappa August 2012 Copyright © 2012 by Gautham P. Rajappa All rights reserved. ii DEDICATION To my parents and friends iii ACKNOWLEDGEMENTS First, I would like to express my gratitude to all my committee members. Wilck, my advisor, for hiring me to pursue my Ph.
at the University of Tennessee, Knoxville. You have been a source of inspiration to me and I whole heartedly thank you for supporting and challenging me for the past three years. I have had some of the most interesting conversations ranging from politics to sports with you. Charles Noon, for taking his time out from his busy schedule and sharing his knowledge on my dissertation.
I consider you as my role model. Xueping Li, for providing your valuable inputs on my dissertation and also, for teaching some important courses which have helped me shape my career. Xiaoyan Zhu, for providing your valuable inputs and pushing me to bring the best out of me. Second, I would like to thank all the faculty members from the Departments of Industrial Engineering and Business Analytics.
In particular, I would like to thank Dr. You were there for me whenever I wanted to discuss anything personal or professional. You always answered me with a smile and some of your inputs have really helped me a lot in my personal life. Also, I would like to thank Dr.
Bell from the Business School for providing his valuable inputs on my dissertation. I would also like to thank you for helping me write my first ever journal paper. I honestly believe that the experience of sitting with you in your office and writing the paper gave me a whole new perspective of how journals paper have to be written. Third, I would like to thank all my friends and colleagues, without whose support, I would never have been able to finish my Ph.
My colleagues from UT are some the best students/friends I have ever worked with. In particular, I would like to thank my friends Avik, Ajit, Aju, Karthik, Gagan, Sherin, Rani, Geetika, and Ashutosh from Knoxville, who were always there for me and without whom, life would be very different in Knoxville. Also, I would like to thank my friends Arjun & Sowmya (for planning iv some wonderful vacations), Aubin (my bank), Priyamvad, Pai, Shailesh, Katti, Vincil, Ajay, Uday, Gidda, Sharath, Sarpa, Vinay (for your motivating talks), Durgesh (for your perseverance), and Ameya (the smartest human being that I have ever known). Finally, I would like to thank my parents Shashikala and Rajappa, Bharath (younger brother) and Sandhya (my older cousin sister), who always believed in me and supported me to pursue my dreams.
v ABSTRACT This dissertation presents metaheuristic approaches in the areas of genetic algorithms and ant colony optimization to solve combinatorial optimization problems. Ant colony optimization for the split delivery vehicle routing problem An Ant Colony Optimization (ACO) based approach is presented to solve the Split Delivery Vehicle Routing Problem (SDVRP). SDVRP is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) wherein a customer can be visited by more than one vehicle. The proposed ACO based algorithm is tested on benchmark problems previously published in the literature.
The results indicate that the ACO based approach is competitive in both solution quality and solution time. In some instances, the ACO method achieves the best known results to date for the benchmark problems. Hybrid genetic algorithm for the split delivery vehicle routing problem (SDVRP) The Vehicle Routing Problem (VRP) is a combinatory optimization problem in the field of transportation and logistics. There are various variants of VRP which have been developed of the years; one of which is the Split Delivery Vehicle Routing Problem (SDVRP).
The SDVRP allows customers to be assigned to multiple routes. A hybrid genetic algorithm comprising a combination of Ant Colony Optimization (ACO), Genetic Algorithm (GA), and heuristics is proposed and tested on benchmark SDVRP test problems. Genetic algorithm approach to solve the hospital physician scheduling problem Emergency departments have repeating 24-hour cycles of non-stationary Poisson arrivals and high levels of service time variation. The problem is to find a shift schedule that considers queuing effects and minimizes average patient waiting time and maximizes physicians’ shift preference subject to constraints on shift start times, shift durations and total physician hours available per day.
An approach that utilizes a genetic algorithm and discrete event simulation to solve the physician scheduling problem in a hospital is proposed. The approach is tested on real world datasets for physician schedules. vi TABLE OF CONTENTS CHAPTER I .1 Solving Multiobjective Optimization Problems with Genetic Algorithms. Ant Colony Optimization.
18 Ant Colony Optimization for the Split Delivery Vehicle Routing Problem. SDVRP Problem Formulation and Benchmark Data Sets. Ant Colony Optimization Approach. Conclusions and Future directions.
40 A hybrid Genetic Algorithm approach to solve the Split Delivery vehicle routing problem. Split Delivery Vehicle Routing Problem (SDVRP). Hybrid Genetic Algorithm Approach. Conclusions and Future directions.
57 A Genetic Algorithm approach to solve the physician scheduling problem. Problem Definition and Genetic Algorithm approach .2 Genetic Algorithm Approach. Results, Conclusions, and Future Work .2 Conclusions and Future Work. 93 viii LIST OF TABLES Table 2.2: Comparing ACO results versus Jin et al.3: Comparing ACO results versus Chen et al.4: Post-hoc results (without using a candidate list) .5: Comparison of ACO objective function for Chen et al.6: Comparison of ACO objective function for Jin et al.2: Comparing Hybrid GA results versus Jin et al.3: Comparing Hybrid GA results versus Chen et al.4: Comparison of ACO objective function for Chen et al.5: Comparison of ACO objective function for Jin et al.2: Average number of patients arriving per hour (Dataset 1) .3: Average number of patients arriving per hour (Dataset 2) .4: Feasible shifts with preference (Dataset 1) .5: Feasible shifts with preference (Dataset 2) .8: Weighted sum approach results (Dataset 1) .9: Weighted sum approach results (Dataset 2) .10: Number of patients of capacity (Dataset 1) .11: Number of patients of capacity (Dataset 2).
83 ix LIST OF FIGURES Figure 1.1: Genetic Algorithm Flowchart .2: Ant Colony Optimization .2: Hybrid GA Flowchart .1: Genetic Algorithm Flowchart (Dataset 1) .2: Total preference violation v/s Average patient wait time (min)(Dataset 1) .3: Total preference violation v/s Average patient wait time (min)(Dataset 2). Chapter Abstract In this chapter, a brief overview on metaheuristics is presented. Since, this dissertation focuses on Genetic Algorithms and Ant Colony Optimization, a detailed overview of both the metaheuristics is provided in the chapter. Metaheuristics Overview A large number of well-known numerical combinatorial programming, linear programming (LP), and nonlinear programming (NLP) based algorithms are applied to solve a variety of optimization problems.
In small and simple models, these algorithms were always successful in determining the global optimum. But in reality, many optimization problems are complex and complicated to solve using algorithms based on LP and NLP methods. Combinatorial optimization (Osman and Kelly, 1996a) can be defined as a mathematical study of finding an optimal arrangement, grouping, ordering, or selection of discrete objects usually finite in number. A combinatory optimization problem can be either easy or hard.
We call the problem easy if we can develop an efficient algorithm to solve for optimality in a polynomial time. If an efficient algorithm does not exist to solve for optimality in a polynomial time, we call the problem hard. An optimal algorithm to compute optimality for hard problems requires a large number of computational steps which grows exponentially with the problem size. The computational drawbacks of such algorithms for complex problems have led researchers to develop metaheuristic algorithms to obtain a (near) optimal solution.
The term "metaheuristic” was first coined by Fred Glover (1986). Generally, it is applied to problems classified as NP-Hard or NP-Complete but could also be applied to other combinatorial optimization problems. Metaheuristics are among the best known methods for a good enough and cheap (i., minimal computer time) solution for NP-Hard or NP- Complete problems. Some of the typical examples where metaheuristics are used are the traveling salesman problem (TSP), scheduling problems, assignment problems, and vehicle routing problems (VRP).
Such types of problems falls under combinatory optimization problems. According to Osman and Laporte (1996b), a metaheuristic 2 algorithm is defined as: "An iterative generation process which guides a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space, learning strategies are used to structure information in order to find efficiently near-optimal solutions." According to Blum and Roli (2003a), metaheuristics are strategies that guide a search process which explore the search space to find a (near-) optimal solution. Metaheuristics are not problem-specific and may make use of domain- specific knowledge in the form of heuristics. Some of the well known metaheuristic approaches are genetic algorithm, simulated annealing, Tabu search, memetic algorithm, ant colony optimization, particle swarm optimization, etc.
The following sections provide an overview of Genetic Algorithms and Ant Colony Optimization, which are relevant to this dissertation. Genetic Algorithms Genetic algorithms are population based search algorithms to solve combinatorial optimization problems. It was first proposed by John Holland (1989). They generate solutions for optimization problem based on theory of evolution using concepts such as reproduction, crossover and mutation.
The fundamental concept of a genetic algorithm states a set of conditions to achieve global optima. These conditions describe the reproduction process and ensure that better solution remain in future generations and weaker solutions be eliminated from future generations. This is similar to the Darwin’s survival of fittest concept in the theory of evolution. A typical genetic algorithm (GA) consists of the following steps (Holland, 1989): Step 1: Generate an initial population of N solutions.
Step 2: Evaluate each solution of the initial population using a fitness function/objective function. Step 3: Select solutions as parents for the new generation based on probability or randomness. The best solutions (in terms of fitness or objective) have a higher probability of being selected than poor solutions. 3 Step 4: Use the parent solutions from Step 3 to produce the next generation (called offspring).
This process is called as crossover. The offspring are placed in the initial set of solutions replacing the weaker solutions. Step 5: Randomly alter the new generation by mutation. Usually this is done using a mutation probability.
Step 6: Repeat Steps 2 through 5 until a stopping criteria is met. A flowchart of a simple GA is shown in Figure 1.