Efficiency analysis of tabu search heuristic for static dial-a-ride problem
Multi-vehicle routing has become increasingly important due to the rapid development in autonomous vehicle technology and Internet of Things. By developing better multivehicle routing algorithms, the current transportation system can be made more efficient and travel time can be significantly reduce...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/73146 |
| _version_ | 1811697343580340224 |
|---|---|
| author | Ho, Song Guang |
| author2 | Justin Dauwels |
| author_facet | Justin Dauwels Ho, Song Guang |
| author_sort | Ho, Song Guang |
| collection | NTU |
| description | Multi-vehicle routing has become increasingly important due to the rapid development in autonomous vehicle technology and Internet of Things. By developing better multivehicle routing algorithms, the current transportation system can be made more efficient and travel time can be significantly reduced. A future-proof algorithm must be one that utilize all available data (i.e. traffic condition, weather condition) to make routing algorithm more accurate and efficient. There are many algorithms developed to solve diala-ride problem. One of them is tabu search algorithm developed for dial-a-ride problems by Cordeau and Laporte in 2003. This thesis investigates ways to reduce the computational time of tabu search algorithm by proposing an improved tabu search algorithm. The efficiency validation of the algorithm has been performed using twelve variants of the major parameters. These variants are based on the type of insertion techniques, neighborhood evaluation methods and time window adjustments used. There are two types of insertion techniques: one-step and two-step insertion; there are three types of neighborhood evaluation techniques: one-level, two-level and three-level neighborhood evaluation. The effect of implementing time window adjustment is also tested. From the extensive simulations, it has been identified that three-level neighborhood evaluation technique and time window adjustment are crucial to improve the efficiency. One-step and two-step insertion both have their own advantages, and should be applied according to application specifications and needs. Number of iteration for the tabu search algorithm should also be adjusted accordingly to reduce the computation time. |
| first_indexed | 2024-10-01T07:53:45Z |
| format | Thesis |
| id | ntu-10356/73146 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:53:45Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/731462023-07-04T15:47:48Z Efficiency analysis of tabu search heuristic for static dial-a-ride problem Ho, Song Guang Justin Dauwels School of Electrical and Electronic Engineering DRNTU::Engineering::Electrical and electronic engineering Multi-vehicle routing has become increasingly important due to the rapid development in autonomous vehicle technology and Internet of Things. By developing better multivehicle routing algorithms, the current transportation system can be made more efficient and travel time can be significantly reduced. A future-proof algorithm must be one that utilize all available data (i.e. traffic condition, weather condition) to make routing algorithm more accurate and efficient. There are many algorithms developed to solve diala-ride problem. One of them is tabu search algorithm developed for dial-a-ride problems by Cordeau and Laporte in 2003. This thesis investigates ways to reduce the computational time of tabu search algorithm by proposing an improved tabu search algorithm. The efficiency validation of the algorithm has been performed using twelve variants of the major parameters. These variants are based on the type of insertion techniques, neighborhood evaluation methods and time window adjustments used. There are two types of insertion techniques: one-step and two-step insertion; there are three types of neighborhood evaluation techniques: one-level, two-level and three-level neighborhood evaluation. The effect of implementing time window adjustment is also tested. From the extensive simulations, it has been identified that three-level neighborhood evaluation technique and time window adjustment are crucial to improve the efficiency. One-step and two-step insertion both have their own advantages, and should be applied according to application specifications and needs. Number of iteration for the tabu search algorithm should also be adjusted accordingly to reduce the computation time. Master of Science (Computer Control and Automation) 2018-01-03T07:50:13Z 2018-01-03T07:50:13Z 2018 Thesis http://hdl.handle.net/10356/73146 en 89 p. application/pdf |
| spellingShingle | DRNTU::Engineering::Electrical and electronic engineering Ho, Song Guang Efficiency analysis of tabu search heuristic for static dial-a-ride problem |
| title | Efficiency analysis of tabu search heuristic for static dial-a-ride problem |
| title_full | Efficiency analysis of tabu search heuristic for static dial-a-ride problem |
| title_fullStr | Efficiency analysis of tabu search heuristic for static dial-a-ride problem |
| title_full_unstemmed | Efficiency analysis of tabu search heuristic for static dial-a-ride problem |
| title_short | Efficiency analysis of tabu search heuristic for static dial-a-ride problem |
| title_sort | efficiency analysis of tabu search heuristic for static dial a ride problem |
| topic | DRNTU::Engineering::Electrical and electronic engineering |
| url | http://hdl.handle.net/10356/73146 |
| work_keys_str_mv | AT hosongguang efficiencyanalysisoftabusearchheuristicforstaticdialarideproblem |