Back to Search
Start Over
A spatial parallel heuristic approach for solving very large-scale vehicle routing problems
- Source :
- Transactions in GIS. 21:1130-1147
- Publication Year :
- 2017
- Publisher :
- Wiley, 2017.
-
Abstract
- The vehicle routing problem (VRP) is one of the most prominent problems in spatial optimization because of its broad applications in both the public and private sectors. This article presents a novel spatial parallel heuristic approach for solving large-scale VRPs with capacity constraints. A spatial partitioning strategy is devised to divide a region of interest into a set of small spatial cells to allow the use of a parallel local search with a spatial neighbor reduction strategy. An additional local search and perturbation mechanism around the border area of spatial cells is used to improve route segments across spatial cells to overcome the border effect. The results of one man-made VRP benchmark and three real-world super-large-scale VRP instances with tens of thousands of nodes verify that the presented spatial parallel heuristic approach achieves a comparable solution with much less computing time.
- Subjects :
- 050210 logistics & transportation
Mathematical optimization
Reduction strategy
021103 operations research
Computer science
05 social sciences
0211 other engineering and technologies
Spatial partition
Poison control
02 engineering and technology
Border effect
Spatial optimization
Region of interest
0502 economics and business
Vehicle routing problem
General Earth and Planetary Sciences
Space partitioning
Subjects
Details
- ISSN :
- 13611682
- Volume :
- 21
- Database :
- OpenAIRE
- Journal :
- Transactions in GIS
- Accession number :
- edsair.doi...........c2506df1b8cead92e039a3345422e9df