整合時窗限制與回程撿收之多車種車輛途程問題

The Vehicle Routing Problem With Backhaul and Time Window Constraints

魏宗徹(Zong-Che Wei)

指導教授 ： 胡黃德 博士

元智大學/工程學院/工業工程與管理學系/碩士(2001年)

摘要

物流系統中運輸成本佔了相當大的比例，因此如何發展一套切合企業本身所需的派車配送法則，以降低運輸成本及增加企業利潤是目前各企業的工作要務之一。一般的回程撿收車輛途程問題（Vehicle Routing Problem with Backhaul, VRPB）大都限制撿收須在所有運送之後，顧客的作業內容不是單純的送貨就是單純的撿收，而且都假設單一車種。本研究嘗試將上述的限制與假設放寬，在送貨與撿收的優先權限制方面，以允許撿收百分比來放寬，當送出的貨物量達到車輛載重量一定百分比後，即可不受送貨優先權的限制，但同一時間點送貨量加撿貨量不得超過車輛的載重限制。再者將顧客分為三個子集合：運送顧客，將貨品自場站配送至顧客處；撿收顧客，將貨品自顧客處收集帶回場站；運送與撿收混合顧客，首先將顧客需要的貨品卸下，再把場站需要的貨品帶回。最後，我們並同時比較單一車種與多車種之情況。本研究以遺傳演算法求解，運用兩種初始解、兩種交配法與兩種突變法之組合，並利用田口方法找出最適合的因子水準與參數組合。最後，我們以Solomon題庫測試，並將其修改為具回程撿收的多車種題型。結果顯示，撿收顧客為所有顧客的50﹪、允許撿收百分比為10﹪時，會得到較低的總成本。而且，多車種在總成本方面平均比單車種節省19.5 ﹪，車輛平均利用率提升了14.4 ﹪。

關鍵字

遺傳演算法 ； 車輛途程問題 ； 多車種 ； 時窗限制 ； 回程撿收

並列摘要

The transportation cost accounts for a large amount in logistics system, hence how to design a useful vehicle routing rule can reduce the transportation cost and increase the profit is the primary issues for the company. Ordinary Vehicle Routing Problem with Backhaul（VRPB）assumes that the pickup operations are followed by delivery. The operations are either simple delivery or pickup, and single vehicle type is assumed. The purpose of this study was to allow the priority flexibility of pickup and delivery via pickup allowance rate. Where the delivery goods was over the specified percents of carrying capacity, this vehicle could break the priority of delivery and then made both delivery and pickup operation at the customer station. However, both delivery and pickup operation could not exceed the vehicle capacity constraint. Customers were classified by 3 subgroups, one for delivery（or linehaul）, one for pickup（or backhaul）and the other is the mix of linehaul and backhaul. We also study the imparts of both single type and mixed type vehicle on the solution. A genetic algorithm was applied to the problem and parameters were determined by Taguchi Method for optimal design. The test problem by Solomon were tested to check the feasibility of the approach. The results show that the minimize total cost occurred at the level of pickup customers is 50% and percent of pickup allowance is 10%. The mix vehicle consideration performs better is total cost（-19.5%）and average utilization（+14.4%）.

並列關鍵字

Genetic Algorithm ； Vehicle Routing Problem (VRP) ； Mixed Vehicle ； Time Window Constraint ； Backhaul

參考文獻

and Asymmetric Vehicle Routing Problem with Backhauls,”

[Online].Available：

林書銘，「禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究」，元智

陳宏坤，「應用遺傳演算法於倉儲批發量販業之賣場設施佈置問題之究」，元

梁俊卿，「遺傳演算法應用於自動倉儲系統撿取作業之規劃」，元智大學工業