An ant colony algorithm for solving multi-depot vehicle routing problems with time windows | |
| Author | Tossaporn Nakay |
| Call Number | AIT Thesis no.ISE-05-15 |
| Subject(s) | Algorithms Travel time (Traffic engineering) |
| Note | A thesis submitted in partial fulfillment of the requirements for the degree of Master of Engineering, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Thesis ; no. ISE-05-15 |
| Abstract | The Multi-Depot Vehicle Routing Problem with Time Windows (MDVRPTW) involves servicing a set of customers from a set of depots at a specific time window of each customer. The objective of the problem is to minimize the total travel distance and vehicle usage to supply all customers from several depots in their required hours. Since MDVRPTW is an NP-hard combinatorial problem, heuristic is an appropriate approach to solve this problem. In this study, a meta-heuristics based on Ant Colony System (ACS) with local search procedures (2-opt and hybrid 2-opt*/Or-opt) is proposed to solve MDVRPTW. The algorithm assigns the number of ant colonies equal to the number of depots. A number of trials is conducted for selecting the appropriate parameters and choosing the method to implement solution construction. Additionally, comparisons with local search procedure and effect of random initial pheromone have been extensively studied in this paper. The results showed that ACS with serial construction gives the good result in both total distance and number of vehicles. Random initial pheromone can increase the chance to jump out from local optima, but takes a longer computation time. Comparison with the best result from Or-Library, ACS can be competitive in terms of number of vehicles, but still gets worse total distance. |
| Year | 2005 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. ISE-05-15 |
| Type | Thesis |
| School | School of Advanced Technologies (SAT) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Anulark Techanitisawad; |
| Examination Committee(s) | Voratas Kachitvichyanukul ;Bohez, Erik L. J. ; |
| Scholarship Donor(s) | Thai Asahi Glass Public Company Limited ; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 2005 |