.png){kind=icon}
.png){kind=icon}
Return
A parallel algorithm for the vehicle routing problem with time window constraints
.png){kind=icon}
PRE
AI
DOI：10.1023/A:1018948011707.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we describe a new parallel tabu search heuristic for the vehicle routing problem with time window constraints (VRPTW). The neighborhood structure we propose is based on simple customer shifts and allows us to consider infeasible interim-solutions. Similarly to the column generation approach used in exact algorithms, all routes generated by the tabu search heuristic are collected in a pool. To obtain a new initial solution for the tabu search heuristic, a fast set covering heuristic is periodically applied to the routes in the pool. The parallel heuristic has been implemented on a Multiple-Instruction Multiple-Data computer architecture with eight nodes. Computational results for Solomon's benchmark problems demonstrate that our parallel heuristic can produce high-quality solutions.
Keywords:
vehicle routing problem
time windows
tabu search
parallel algorithms
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W
Organization
No organization information available