Please use this identifier to cite or link to this item:
A Study on Applying RVND Local Search Strategy for Vehicle Routing Problems
|Authors: ||Liu , Da-Yuan|
|Contributors: ||NTOU:Department of Computer Science and Engineering|
CVRP;iterative local search;Random Variable Neighborhood Descent
|Issue Date: ||2018-08-22T06:56:37Z
|Abstract: ||本論文探討物流配送車輛路徑問題(capacitated vehicle routing program, CVRP)，實做了由Anand Subramanian所提出的反覆局部搜尋策略並以此做低搜尋次數實驗探討。並且我們基於原反覆局部搜尋策略提出了以開發與探索為觀點的兩階段式搜尋策略來解決車輛路徑問題，並且以這兩種搜尋策略做不同的搜尋次數下的表現。以一階段式搜尋策略與兩階段式搜尋策略為主體，用來觀測在兩階段式不同的分配法與一階段式搜尋策略的效能在低迭代次數下的表現效果，最後再以兩階段式搜尋策略與一階段式搜尋策略皆未達到最佳解的題目來進行高跌代次數下的效能表現。|
In this research work, we study the capacitated vehicle routing programs (CVRP) and their solution techniques. We solved the CVRP problems with ILS-RVND schemes, an iterative local-search approach based on RVND (Random Variable Neighborhood Descent). We investigated different variations of the original ILS-RVND and discussed the performance impacts between these different variations. In particular, we proposed a two-stage approach to conduct the ILS-RVND schemes, in which we partitioned the computation efforts of the ILS-RVND into two parts to balance between exploitation and exploration. In the first stage (the search stage) we allocate parts of computation efforts to find a set of possible candidation solutions to be exploited in the next stage (the refinement stage). Based on a public benchmark data set, we compared performances between the two approaches: original ILS-RVND (one-stage version) and the two-stage ILS-RVND. The results shows both of the two versions of ILS-RVND schems can achieve good solution quality, with the ABSG (Average Best Solution Gaps to the BKS (best known solution)) less than 0.1%. Also, we showed, from the results, the proposed two-stage ILS-RVND can improve ABSG further, whenever the partition parameters were chosed carefully.
|Appears in Collections:||[資訊工程學系] 博碩士論文|
Files in This Item:
All items in NTOUR are protected by copyright, with all rights reserved.