Two-stage Particle Swarm Optimization Algorithm for the Time Dependent Alternative Vehicle Routing ProblemHsiao-Fan Wang* and Yen-Yi Lee
Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, Taiwan, ROC
- *Corresponding Author:
- Hsiao-Fan Wang
Department of Industrial Engineering & Engineering Management
National Tsing Hua University, Hsinchu, Taiwan, ROC
Tel: 886 3 571 5131
E-mail: [email protected]
Received date: May 26, 2014; Accepted date: June 27, 2014; Published date: July 02, 2014
Citation: Wang HF, Lee YY (2014) Two-stage Particle Swarm Optimization Algorithm for the Time Dependent Alternative Vehicle Routing Problem. J Appl Computat Math 3: 170. doi: 10.4172/2168-9679.1000170
Copyright: © 2014 Wang HF, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
This study considered a Time Dependent Alternative Vehicle Routing Problem (TDAVRP) in a multi-graph network (TDAVRP) and was formulated into a Mixed Integer Programming model. Due to its NP nature, an algorithm based on Particle Swarm Optimization (PSO) with local improvement was developed to speed up the solution procedure. By using different sets of Solomon’s benchmark problems and continuous travel time functions, the accuracy and efficiency of the two-stage PSO were evaluated. The computational results showed that the proposed algorithm is capable of deriving optimal or near optimal solutions in a short period of time when the size of the problems are small and is able to obtain feasible solutions within a reasonable time when solving the large problems which cannot be solved by ILOG CPLEX. In addition, Sensitivity Analysis was conducted to evaluate the performances of the parameters. The results indicated that the number of customers is a sensitive parameter and will influence the required number of vehicles, value of violations and percentage of alternative edges in the solution sets.