An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints

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...

Full description

Bibliographic Details
Main Author: Noraini, Mohd Razali
Format: Article
Language:English
Published: Elsevier Ltd. 2015
Subjects:
Online Access:http://umpir.ump.edu.my/id/eprint/10151/1/An%20Efficient%20Genetic%20Algorithm%20for%20Large%20Scale%20Vehicle%20Routing%20Problem%20Subject%20to%20Precedence%20Constraints.pdf
_version_ 1796990744213323776
author Noraini, Mohd Razali
author_facet Noraini, Mohd Razali
author_sort Noraini, Mohd Razali
collection UMP
description 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.
first_indexed 2024-03-06T11:56:05Z
format Article
id UMPir10151
institution Universiti Malaysia Pahang
language English
last_indexed 2024-03-06T11:56:05Z
publishDate 2015
publisher Elsevier Ltd.
record_format dspace
spelling UMPir101512018-02-08T03:51:47Z http://umpir.ump.edu.my/id/eprint/10151/ An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints Noraini, Mohd Razali TS Manufactures 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. Elsevier Ltd. 2015 Article PeerReviewed application/pdf en http://umpir.ump.edu.my/id/eprint/10151/1/An%20Efficient%20Genetic%20Algorithm%20for%20Large%20Scale%20Vehicle%20Routing%20Problem%20Subject%20to%20Precedence%20Constraints.pdf 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) http://www.sciencedirect.com/science/article/pii/S1877042815036824 doi:10.1016/j.sbspro.2015.06.203
spellingShingle TS Manufactures
Noraini, Mohd Razali
An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints
title An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints
title_full An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints
title_fullStr An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints
title_full_unstemmed An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints
title_short An Efficient Genetic Algorithm for Large Scale Vehicle Routing Problem Subject to Precedence Constraints
title_sort efficient genetic algorithm for large scale vehicle routing problem subject to precedence constraints
topic TS Manufactures
url http://umpir.ump.edu.my/id/eprint/10151/1/An%20Efficient%20Genetic%20Algorithm%20for%20Large%20Scale%20Vehicle%20Routing%20Problem%20Subject%20to%20Precedence%20Constraints.pdf
work_keys_str_mv AT norainimohdrazali anefficientgeneticalgorithmforlargescalevehicleroutingproblemsubjecttoprecedenceconstraints
AT norainimohdrazali efficientgeneticalgorithmforlargescalevehicleroutingproblemsubjecttoprecedenceconstraints