English  |  正體中文  |  简体中文  |  Items with full text/Total items : 26988/38789
Visitors : 2319078      Online Users : 33
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/49322

Title: 利用RVND區域搜尋策略解車輛路徑問題
A Study on Applying RVND Local Search Strategy for Vehicle Routing Problems
Authors: Liu , Da-Yuan
劉大園
Contributors: NTOU:Department of Computer Science and Engineering
國立臺灣海洋大學:資訊工程學系
Keywords: 物流配送車輛路徑問題;跨路徑區域搜尋;反覆局部搜尋策略
CVRP;iterative local search;Random Variable Neighborhood Descent
Date: 2015
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.
URI: http://ethesys.lib.ntou.edu.tw/cgi-bin/gs32/gsweb.cgi?o=dstdcdr&s=G0010157033.id
http://ntour.ntou.edu.tw:8080/ir/handle/987654321/49322
Appears in Collections:[資訊工程學系] 博碩士論文

Files in This Item:

File Description SizeFormat
index.html0KbHTML3View/Open


All items in NTOUR are protected by copyright, with all rights reserved.

 


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback