Improved ant colony optimization for solving dial-a-ride-problem
The dial-a-ride problem (DARP) is a combinatorial optimization problem in which passengers claim requests in the form of their departure location, destination and the specific time windows during which they must be picked up and dropped off. A certain number of vehicles are assigned to serve these r...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/73130 |
| _version_ | 1826110902822240256 |
|---|---|
| author | Peng, Guohao |
| author2 | Keveh Azizan |
| author_facet | Keveh Azizan Peng, Guohao |
| author_sort | Peng, Guohao |
| collection | NTU |
| description | The dial-a-ride problem (DARP) is a combinatorial optimization problem in which passengers claim requests in the form of their departure location, destination and the specific time windows during which they must be picked up and dropped off. A certain number of vehicles are assigned to serve these requests while ensuring that the maximum capacities of vehicles are not exceeded and the maximum ride time constraints of passengers, if any, are not violated. In this thesis, an improved ant colony optimization (IACO) algorithm is proposed to address the dial-a-ride-problem. The proposed algorithm works by pre-processing the requests to eliminate the ones that are infeasible from the beginning. In order to select the requests, the algorithm considers factors like time windows, local heuristics and vehicle load. Also, an adjust function is introduced to improve the quality of solutions and chaotic perturbation is used to prevent premature convergence. Numerous simulations have been carried out to demonstrate the efficiency of the proposed algorithm. |
| first_indexed | 2024-10-01T02:41:48Z |
| format | Thesis |
| id | ntu-10356/73130 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:41:48Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/731302023-07-04T15:05:51Z Improved ant colony optimization for solving dial-a-ride-problem Peng, Guohao Keveh Azizan Justin Dauwels School of Electrical and Electronic Engineering DRNTU::Engineering::Electrical and electronic engineering The dial-a-ride problem (DARP) is a combinatorial optimization problem in which passengers claim requests in the form of their departure location, destination and the specific time windows during which they must be picked up and dropped off. A certain number of vehicles are assigned to serve these requests while ensuring that the maximum capacities of vehicles are not exceeded and the maximum ride time constraints of passengers, if any, are not violated. In this thesis, an improved ant colony optimization (IACO) algorithm is proposed to address the dial-a-ride-problem. The proposed algorithm works by pre-processing the requests to eliminate the ones that are infeasible from the beginning. In order to select the requests, the algorithm considers factors like time windows, local heuristics and vehicle load. Also, an adjust function is introduced to improve the quality of solutions and chaotic perturbation is used to prevent premature convergence. Numerous simulations have been carried out to demonstrate the efficiency of the proposed algorithm. Master of Science (Computer Control and Automation) 2018-01-03T07:10:47Z 2018-01-03T07:10:47Z 2018 Thesis http://hdl.handle.net/10356/73130 en 85 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Electrical and electronic engineering Peng, Guohao Improved ant colony optimization for solving dial-a-ride-problem |
| title | Improved ant colony optimization for solving dial-a-ride-problem |
| title_full | Improved ant colony optimization for solving dial-a-ride-problem |
| title_fullStr | Improved ant colony optimization for solving dial-a-ride-problem |
| title_full_unstemmed | Improved ant colony optimization for solving dial-a-ride-problem |
| title_short | Improved ant colony optimization for solving dial-a-ride-problem |
| title_sort | improved ant colony optimization for solving dial a ride problem |
| topic | DRNTU::Engineering::Electrical and electronic engineering |
| url | http://hdl.handle.net/10356/73130 |
| work_keys_str_mv | AT pengguohao improvedantcolonyoptimizationforsolvingdialarideproblem |