:::
Trans. Planning Journal
| Title | Applications of the GIDS Metaheuristic to the Periodic Vehicle Routing Problem |
|---|---|
| Author | Anthony Fu-Wha Han, Yuh-Jen Cho |
| Summary | The periodic vehicle routing problem (PVRP), a different from the conventional vehicle routing problem (VRP), considers the different delivery frequencies that customers may require during a dispatch period of time. This paper presents a new metaheuristic approach, i.e. the generic intensification and diversification search (GIDS), to solve the PVRP. The GIDS integrates the use of some recently developed generic search methods such as threshold accepting (TA) and great deluge algorithm (GDA), and the meta-strategies of intensification and diversification for intelligent search. The GIDS includes three components: multiple initialization constructor (MIC), generic search for intensification (GSI), and perturbation search for diversification (PSD). We designed five modules and proposed several modified algorithms for the implementation of the GIDS to PVRP. A bank of thirty-two PVRP benchmark instances was tested by several different implementations of GIDS. All programs were coded in UNIX C and ran on a SUN SPARC 10 workstation. Computational results are very encouraging. We found that the average deviation from the thirty-two best-known solutions is merely 0.26 %. Moreover, using GIDS we have updated the best-known solutions for six of the thirty-two benchmark instances. |
| Vol. | 31 |
| No. | 1 |
| Page | 1 |
| Year | 2002 |
| Month | 3 |
Count Views:453