虛擬場站補貨車輛途程問題;The Linehaul-Feeder Vehicle Routing Problem with Virtual Depots

NCUIR > Engineering College > Department of Civil Engineering > Research Project > Item 987654321/25577

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/25577

Title:	虛擬場站補貨車輛途程問題;The Linehaul-Feeder Vehicle Routing Problem with Virtual Depots
Authors:	陳惠國
Contributors:	土木工程學系
Keywords:	車輛途程問題;虛擬場站補貨;Vehicle Routing Problem;Virtual Depot;Meta-heuristics;Cost SharingMethod;Threshold Method;交通運輸
Date:	2010-07-01
Issue Date:	2010-06-10 17:29:28 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	台灣都市地區部分巷道狹窄，致使大型貨車進出、臨時停車皆不容易。為因應此問題，物流業者使用機動性高但載貨量較小之輕便車輛(如機車)進行貨物配送，然而此舉可能造成車輛往返配送場站中心之次數與距離增加。近年來已有部分業者利用載貨量大但機動性較低之大車(如貨車)搭配機動性高但載貨量較小之小車(如機車)進行聯合貨物配送，亦即大車、小車各自進行貨物配送，當小車送貨完畢時，除了返回場站補貨亦可選擇直接前往大車臨停位置進行補貨，補貨完畢後小車即可再繼續進行送貨服務，節省小車往返場站之次數、距離與時間。針對上述問題描述，本研究分成兩年期分別加以執行。第一年期提出「虛擬場站補貨車輛途程問題」之架構，先進行文獻回顧，根據問題特性建構混合整數規劃模型，並將提出「建構初始解」與「改善初始解」之兩階段求解演算法，由於「虛擬點補貨車輛途程問題」非常複雜，在成本資訊不確定與不完整的限制下，建構初始解無法一次完成，因此本研究將研提多步驟之初始解演算法，且為便於探討演算效率之高低，也將提出「預估平均法」、「門檻法」兩種不同觀念之啟發式求解架構以便於比較，至於改善初始解階段則以一般之交換法為之。所研擬之模型架構與求解演算法之正確性，將以測試題庫The VRP Web 為基礎，從中挑選出 20 題左右加以必要之修改，進行測試、分析與比較。第二年期之研究將提出「時窗限制之虛擬場站補貨車輛途程問題」之架構，這個研究主題與第一年期研究最大之差異在於考量需求點之時窗限制，納入時窗限制之考量將使得模型之架構更符合現實問題之情境，但也使得原已極為複雜之問題更加難以用傳統之演算法觀念求解，值是之故，本研究將引用巨集近似演算法，例如大洪水法、粒子群演算法或禁忌法，加以求解，並進行測試、分析與比較。The problem consists of a big vehicle and a set of small vehicles. During operation, the big vehicle departs from the physical depot (PD) and traverses all virtual depots (VD), whereas a set of small vehicles performs delivery to customers and, if necessary, reloads the commodity either from the PD or from the big vehicle at a VD before continuing their work. The objective of the operation is to minimize vehicles’ total travel cost. To deal with this interesting problem, a two-year span research is proposed. In the first year, the described problem, named the linehaul-feeder vehicle routing problem with virtual depots (LFVRP-VD), will be formulated as a mixed integer programming problem. In view of uncertain and incomplete cost information, two heuristics embedding the cost-sharing method and the threshold method, respectively, will be proposed for solving the LFVRP-VD. The formulated model and proposed solution heuristics will then be demonstrated with about twenty test problems to be adopted and modified from a VRP benchmark problem set that is currently available in the website “The VRP Web”. In the second year the LFVRP-VD problem will be further extended to take the time window constraints into consideration, and hence renamed the linehaul-feeder vehicle routing problem with virtual depots and time windows (LFVRP-VD-TW). This extended problem is clearly more complex than its previous version and indeed very difficult to solve by the traditional two-stage solution heuristics. For this reason, we will adopt meta-heuristics, like Tabu Search or Great deluge algorithm instead to solve the LFVRP-VD-TW problem. 研究期間 : 9808 ~ 9907
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Civil Engineering] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	467	View/Open

社群 sharing

Loading...