Noraini, Mohd Razali (2015) An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints. Procedia - Social and Behavioral Sciences, 195. pp. 1922-1931. ISSN 1877-0428, ESSN: 1877-0428. (Published)
|
PDF
An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints.pdf - Published Version Download (388kB) | Preview |
Abstract
The vehicle routing problem is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Vehicle routing problem has many applications in the fields of transportation, distribution and logistics. In this study, the vehicle routing problem subject to precedence constraints has been modeled as the Travelling Salesman Problem (TSP) with precedence constraints. Vehicle routing problem is difficult to solve using exact methods especially for large size instances due to computational expensive. Therefore, metaheuristic method based genetic algorithm has been developed to obtain feasible and optimal solution with less computation time. The conventional genetic algorithm procedure for TSP, with an order-based representation might generate invalid candidate solutions when precedence constraints are involved. In order to obtain feasible solution which does not violate precedence constraints, a route repair based topological sort technique is used and integrated in the genetic algorithm procedure. In this paper, a new algorithm is developed and the performances as well as the quality of the solution were evaluated against large scale test problems. The results from the computational experiments demonstrate that the algorithm with ‘earliest position’ task selection mechanism, linear order crossover and inversion mutation has better results in terms of number of generations and computation time to converge to optimal solution. The genetic operators used in this study are capable to introduce new fitter offspring and does not trapped in a local optimum. Therefore, it can be stated that the genetic algorithm approach developed in this study is efficient in solving large scale vehicle routing problem subject to precedence constraints with the objective of minimizing the distance travelled.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Genetic algorithm; Topological sort; Vehicle routing problem; Precedence constraints |
| Subjects: | T Technology > TS Manufactures |
| Faculty/Division: | Faculty of Manufacturing Engineering |
| Depositing User: | Mrs. Neng Sury Sulaiman |
| Date Deposited: | 12 Apr 2016 06:38 |
| Last Modified: | 08 Feb 2018 03:51 |
| URI: | http://umpir.ump.edu.my/id/eprint/10151 |
| Download Statistic: | View Download Statistics |
Actions (login required)
 |
View Item |