本論文是運用塔布搜尋法(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.
為了持續優化網站功能與使用者體驗,本網站將Cookies分析技術用於網站營運、分析和個人化服務之目的。
若您繼續瀏覽本網站,即表示您同意本網站使用Cookies。