Title :
Ant Colony Optimization for the Single Vehicle Pickup and Delivery Problem with Time Window
Author :
Huang, Yu-Hsuan ; Ting, Chuan-Kang
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Chung Cheng Univ., Chiayi, Taiwan
Abstract :
The single vehicle pickup and delivery problem with time window (1-PDPTW) is an important class of vehicle routing problem. This problem aims to find a shortest route for a single vehicle to deliver objects from origin to destination, subject to load limit and time window of delivery. This study develops an ant colony optimization (ACO) method for the 1-PDPTW. Specifically, the constraints of time window and capacity are both considered in the transition probability of ants. Furthermore, we proposed a repair operator to deal with infeasible routes. Experimental results show that the proposed ACO can outperform genetic algorithm and tabu search in terms of solution quality. The results also validate the effectiveness of the repair operator in improving the feasibility and length of routes.
Keywords :
genetic algorithms; goods distribution; probability; search problems; transportation; 1-PDPTW; ACO method; ant colony optimization; genetic algorithm; infeasible routes; load limit; repair operator; shortest route; single vehicle pickup and delivery problem; solution quality; tabu search; time window; transition probability; vehicle routing problem; ant colony optimization; constraint handling; evolutionary computation; pickup and delivery problem; time window;
Conference_Titel :
Technologies and Applications of Artificial Intelligence (TAAI), 2010 International Conference on
Conference_Location :
Hsinchu
Print_ISBN :
978-1-4244-8668-7
Electronic_ISBN :
978-0-7695-4253-9
DOI :
10.1109/TAAI.2010.90