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...
| Main Author: | |
|---|---|
| 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 |