Feasible Initial Population with Genetic Diversity for a Population-Based Algorithm Applied to the Vehicle Routing Problem with Time Windows
Joint Authors
Cruz-Chávez, Marco Antonio
Martínez-Oropeza, Alina
Source
Mathematical Problems in Engineering
Issue
Vol. 2016, Issue 2016 (31 Dec. 2016), pp.1-11, 11 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2016-02-17
Country of Publication
Egypt
No. of Pages
11
Main Subjects
Abstract EN
A stochastic algorithm for obtaining feasible initial populations to the Vehicle Routing Problem with Time Windows is presented.
The theoretical formulation for the Vehicle Routing Problem with Time Windows is explained.
The proposed method is primarily divided into a clustering algorithm and a two-phase algorithm.
The first step is the application of a modified k -means clustering algorithm which is proposed in this paper.
The two-phase algorithm evaluates a partial solution to transform it into a feasible individual.
The two-phase algorithm consists of a hybridization of four kinds of insertions which interact randomly to obtain feasible individuals.
It has been proven that different kinds of insertions impact the diversity among individuals in initial populations, which is crucial for population-based algorithm behavior.
A modification to the Hamming distance method is applied to the populations generated for the Vehicle Routing Problem with Time Windows to evaluate their diversity.
Experimental tests were performed based on the Solomon benchmarking.
Experimental results show that the proposed method facilitates generation of highly diverse populations, which vary according to the type and distribution of the instances.
American Psychological Association (APA)
Cruz-Chávez, Marco Antonio& Martínez-Oropeza, Alina. 2016. Feasible Initial Population with Genetic Diversity for a Population-Based Algorithm Applied to the Vehicle Routing Problem with Time Windows. Mathematical Problems in Engineering،Vol. 2016, no. 2016, pp.1-11.
https://search.emarefa.net/detail/BIM-1112101
Modern Language Association (MLA)
Cruz-Chávez, Marco Antonio& Martínez-Oropeza, Alina. Feasible Initial Population with Genetic Diversity for a Population-Based Algorithm Applied to the Vehicle Routing Problem with Time Windows. Mathematical Problems in Engineering No. 2016 (2016), pp.1-11.
https://search.emarefa.net/detail/BIM-1112101
American Medical Association (AMA)
Cruz-Chávez, Marco Antonio& Martínez-Oropeza, Alina. Feasible Initial Population with Genetic Diversity for a Population-Based Algorithm Applied to the Vehicle Routing Problem with Time Windows. Mathematical Problems in Engineering. 2016. Vol. 2016, no. 2016, pp.1-11.
https://search.emarefa.net/detail/BIM-1112101
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1112101