透過您的圖書館登入
IP:3.83.187.36
  • 學位論文

軟性時窗與回程撿收之車輛途程問題研究

The Vehicle Routing Problem with Soft Time Window and Backhaul Constraints

指導教授 : 胡黃德
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


本論文是運用塔布搜尋法(Tabu Search)於具時窗限制及回程撿收的車輛途程問題(Vehicle Routing Problem with Backhaul and Time Window, VRPBTW)。具回程撿收的車輛途程問題(Vehicle Routing Problem with Backhaul, VRPB)是傳統車輛途程問題(Vehicle Routing Problem, VRP)的延伸。傳統車輛途程問題,只考慮運送(Linehaul)貨品,而具回程撿收(Backhaul)的車輛途程問題,則是將顧客分為兩個子集合:運送顧客,將貨品自中央場站配送至顧客處;撿收顧客,將自顧客處收集的貨品帶回中央場站。具回程撿收的車輛途程問題的研究中,大多限制撿收須在所有運送之後,這個限制的原因是如果為了撿收貨品而必須在車上重新安排貨品,是很不方便的,且通常運送的貨品具有較高的優先權。但是若按照裝卸貨的順序來堆放貨品且顧客的需求具有時窗限制,則這個限制就可以被取消。本研究嘗試取消此項限制,並以「撿收容許百分比」來限制前幾站不可為撿收顧客,以避免無法滿載出發的問題。而且,顧客開始被服務的時間必須在特定的時間區間之中。本研究以塔布搜尋法求解,運用三種初始解與三種交換法之組合,並利用田口方法找出最適合的因子組合。本研究以標準題庫測試,並以其他相關研究及最佳解比較。結果顯示,若在運送之前容許撿收之措施,將可有效地降低途程成本及車輛數。

並列摘要


This article describes a tabu search heuristic for the vehicle routing problem with backhaul and time window (VRPBTW). The vehicle routing problem with backhaul (VRPB) is the extension of the classical vehicle routing problem (VRP). The VRP only considers the delivery of customers to the stations. However, for the VRPB, the set of customers is partitioned into two subsets : linehaul customers where a given quantity of goods is delivered from a central depot, and backhaul customers where a given quantity of goods is collected from a backhaul customer and transported to the depot. To the VRPB problem, the backhaul must be served after the linehaul on each route. This constraint arises because it is often inconvenient to rearrange linehaul loads onboard in order to accommodate new pick-up loads, and linehaul are generally with higher priority stops than backhauls. If we arrange the load depend on route sequence and the load have time window constraint, this constraint will be relaxed. This study is to relax this constraint and find out its feasibility. We utilize pick-up allowance rate (PAR) to forbid the front of route which can’t be backhauled. Furthermore, the time of beginning of service at each customer must occur within a particular time interval. We utilized tabu search heuristic coupled with three initial solution and three exchange methods to solve the VRPB. Taquchi method was also utilized to find the best design parameters. Computational results are reported on standard set of test problems. The results shows that the use of PAR can reduce the route cost and number of vehicle.

參考文獻


Shoshana, A.,“The Vehicle Routing Problem with Delivery and
林書銘,「塔布搜尋法於含時窗與裝載限制車輛途程問題解算之研究」,
廖亮富,「含時窗限制多部車車輛途程問題解算之研究」,元智大學工業
敖君瑋,「禁制搜尋法於軟性時窗限制之車輛途程問題研究」,元智大學
Spacefilling Curve with Optimal Partition Heuristic for

被引用紀錄


李美儀(2015)。車輛路線相關問題之回顧與國內發展之分析〔碩士論文,國立交通大學〕。華藝線上圖書館。https://doi.org/10.6842%2fNCTU.2015.00488
張寶豐(2003)。以複合啟發式演算法求解時窗限制車輛途程問題〔碩士論文,中原大學〕。華藝線上圖書館。https://doi.org/10.6840%2fcycu200300178
陳百傑(2002)。以啟發式演算法求解時窗限制車輛途程問題〔碩士論文,中原大學〕。華藝線上圖書館。https://doi.org/10.6840%2fcycu200200299
陳契伸(2001)。硬性/軟性時窗限制之車輛途程問題研究〔碩士論文,中原大學〕。華藝線上圖書館。https://doi.org/10.6840%2fcycu200100262
俞錫強(2006)。零場站之車輛途程模式〔碩士論文,元智大學〕。華藝線上圖書館。https://doi.org/10.6838%2fYZU.2006.00191

延伸閱讀