Title :
Effect of genetic sectoring on vehicle routing problems with time windows
Author :
Thangiah, S.R. ; Gubbi, Ananda V.
Author_Institution :
Dept. of Comput. Sci., Slippery Rock Univ., PA, USA
Abstract :
In vehicle routing problems with time windows (VRPTW), a set of vehicles with limited capacity and travel time, are to routed from a central depot to a set of geographically dispersed customers with known demands within specified time windows. The VRSPTW is an NP-hard problem. That is, the time taken to solve it optimally increases exponentially with respect to the size of the problem. Genetic sectoring is a partitioning method that uses a genetic algorithm to find feasible solutions for the VRPTW. The genetic sectoring method was tested on a standard set of VRPTW problems. The solutions obtained using genetic sectoring gave better solutions than known conventional methods. The authors carry out a statistical analysis of the solutions obtained using genetic sectoring, to ascertain the kind of problems in which it would be advantageous to use the genetic sectoring method
Keywords :
genetic algorithms; optimisation; NP-hard problem; VRSPTW; central depot; feasible solutions; genetic algorithm; genetic sectoring method; geographically dispersed customers; partitioning method; specified time windows; statistical analysis; time windows; travel time; vehicle routing problems; Artificial intelligence; Biological cells; Computer science; Dispersion; Genetic algorithms; Intelligent robots; Intelligent vehicles; Job shop scheduling; Laboratories; Routing;
Conference_Titel :
Developing and Managing Intelligent System Projects, 1993., IEEE International Conference on
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-3730-7
DOI :
10.1109/DMISP.1993.248624
