An ant colony algorithm for solving the multi-depot vehicle routing problem | |
| Author | Dang Duy Linh |
| Call Number | AIT Thesis no.ISE-03-13 |
| Subject(s) | Vehicles Heuristic programming |
| 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-03-13 |
| Abstract | This thesis document is the author's research of Multi-Depot Vehicle Routing Problem. The objective of the problem is to find route serving all customers from several depots while minimizing the cost of travel and vehicles usage. Combinatorial optimization problems of this kind are NP-hard and are best solved by heuristics. In this study a new Ant colony-based heuristic named "Multiple Ant Colonies" was developed for obtaining an approximate solution to this problem. Most heuristics in the literature solve the Multi-Depot Vehicle Routing Problem in two stages: clustering and routing. With Multiple Ant heuristic, we try to assign customer to depot and construct route at the same time by using more than one ant colony. The heuristic was tested on several standard problems. The results showed that Multiple Ant heuristic performs very well with small and medium scale problems (up to 200 nodes) and acceptable with larger problem size. |
| Year | 2003 |
| Corresponding Series Added Entry | Asian Institute of Technology. Thesis ; no. ISE-03-13 |
| 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) | Huynh Trung Luong;Voratas Kachitvichyanukul; |
| Scholarship Donor(s) | Petro Vietnam Corporation; |
| Degree | Thesis (M.Eng.) - Asian Institute of Technology, 2003 |