Document Actions

Operations and Information Systems

A Cooperative and Adaptive Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

Abstract

In this paper we propose two cooperation schemes to compose new parallel variants of the Variable Neighborhood Search (VNS). On the one hand, a coarse-grained cooperation scheme is introduced which is well suited for being enhanced with a solution warehouse to store and manage the so far best found solutions and a self-adapting mechanism for the most important search parameters. This makes an a priori parameter tuning obsolete. On the other hand, a fine-grained scheme was designed to reproduce the successful properties of the sequential VNS. In combination with the use of parallel exploration threads all of the best solutions and 11 out of 20 new best solutions for the Multi Depot Vehicle Routing Problem with Time Windows were found.

Keywords

URN: urn:nbn:de:0009-20-16535

Fulltext

Get the fulltext as pdf.

Supplementary material

The file "description.rtf" gives a description of the content of the attachments.
Description (RTF-File) [ view | download ]
The file "01_mdvrptw_instances_cordeau.zip" contains the 20 test instances in the txt-format (pr01.txt - pr20.txt) and a description of the files and the file format.
Mdvrptw-Instances-Cordeau (ZIP-File) [ view | download ]
The file "02_mdvrptw_results.xls" contains the detailed results of the best results (instance number 4 does not provide the best result).
Mdvrptw-Results (XLS) [ view | download ]
The file "03_rpvns_32_results.xls" contains the results for each run (out of 10) of the rpvns (replicated parallel vns) with 32 processors (= workers) with a summary.
Rpvns-32-Results (XLS-File) [ view | download ]
The file "04_pseudocode_coarse-grained.txt" contains the pseudo-code for the coarse-grained implementation, to report the correlation of the ascending moves and the corresponding parameters. The pseudo-code for the fine grained implementation is not reported as it is equivalent with the standard vns implementation.
Pseudocode-Coarse-Grained (TXT-File) [ view | download ]

License

Any party may pass on this Work by electronic means and make it available for download under the terms and conditions of the authorcontract. The text of the license may be accessed and retrieved via Internet at no url given

Recommended citation

Polacek M, Benkner S, Doerner KF, Hartl RF (2008). A Cooperative and Adaptive Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows. BuR - Business Research, Vol. 1, Iss. 2, pp. 207-218, URN: urn:nbn:de:0009-20-16535

Please provide the exact URL and date of your last visit when citing this article.