Thumbnail
Access Restriction
Subscribed

Author Mukai, N. ♦ Ishii, N.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Special computer methods
Subject Keyword Routing ♦ Data structures ♦ Intelligent vehicles ♦ Tree data structures ♦ Biological cells ♦ Genetic mutations ♦ Artificial intelligence ♦ Automotive engineering ♦ Information science ♦ Genetic algorithms ♦ Evolutionary Approach ♦ Vehicle Routing Problem ♦ R-Tree
Abstract Vehicle Routing Problem (VRP) is a problem to find the minimum path length for a fleet of vehicles which deliver goods from the depot according to demands. Some specific methods for the VRP include evolutionary approaches such as Genetic Algorithms. A naive data structure (i.e., chromosome) for the evolutionary approaches is called Path Representation (PR) which is an ordered list structure which represents a single path. On the other hand, we propose a novel data structure called R-Tree based Path Representation (R-PR). R-PR is a tree structure based on a spatial indexing structure called R-Tree. Each node of R-PR represents a sub-path (i.e., a partial solution) for VRP, and its parent node represents a set of the sub-paths, hierarchically. We compare R-PR with PR by using some of VRP instances by Augerat et al, and the results show that R-PR outperforms PR in large scale instances.
ISBN 9781424456192
ISSN 10823409
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-11-02
Publisher Place USA
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 222.35 kB
Page Count 4
Starting Page 758
Ending Page 761


Source: IEEE Xplore Digital Library