A Route-Nearest Neighbor Algorithm for Large-Scale Vehicle Routing Problem
Authors:
- Ruhan HeRHRuhan He
- Weibin XuWXWeibin Xu
- Ying WangYWYing Wang
- Wei ZhanWZWei Zhan
- 1 April 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 390-393
Abstract
We present a new neighbor search algorithm named route-nearest neighbor (RNN) for searching the next node in large-scale vehicle routing problem (VRP). The RNN algorithm is used to divide the area customers into several routes. The key step in the route construction is how to search the next node (i.e., neighbor). Different from the Nearest Neighbor (NN) algorithm that search the neighbor of the current node, the RNN algorithm searches the neighbor of route. The objective of the route is to design a group of geographically closed customers within capacity. The experiments were carried out on a real dataset with 6772 tobacco customers. The results demonstrate that the RNN algorithm has better geographically closed customers than traditional NN algorithm.Keywords
This publication has 4 references indexed in Scilit:
- Active-guided evolution strategies for large-scale capacitated vehicle routing problemsComputers & Operations Research, 2007
- An efficient variable neighborhood search heuristic for very large scale vehicle routing problemsComputers & Operations Research, 2007
- A two-phase hybrid metaheuristic for the vehicle routing problem with time windowsEuropean Journal of Operational Research, 2005
- Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search AlgorithmsTransportation Science, 2005