臺灣博碩士論文加值系統

物流系統中運輸成本佔了相當大的比例，因此如何發展一套切合企業本身所需的派車配送法則，以降低運輸成本及增加企業利潤是目前各企業的工作要務之一。一般的回程撿收車輛途程問題（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%）.

目錄
頁次
中文摘要…………………………………………………………………………i
英文摘要…………………………………………………………………………………ii
致謝………………………………………………………………………………iii
目錄………………………………………………………………………………iv
表目錄……………………………………………………………………………vii
圖目錄……………………………………………………………………………viii
第一章 緒論………………………………………………………………………1
1.1 研究背景與動機…………………………………………………………1
1.2 研究目的…………………………………………………………………2
1.3 研究範圍與假設…………………………………………………………2
1.4 研究流程…………………………………………………………………3
第二章 文獻探討…………………………………………………………………5
2.1 車輛途程問題之概論……………………………………………………5
2.2 車輛途程問題之分類……………………………………………………5
2.3 具時窗限制之車輛途程問題解法………………………………………7
2.4 多車種車輛途程問題法…………………………………………………8
2.5 回程撿收相關文獻整理…………………………………………………10
2.6 遺傳演算法………………………………………………………………11
2.6.1 遺傳演算法簡介……………………………………………………11
2.6.2 遺傳演算法的系統設定……………………………………………12
2.6.3 遺傳演算法基本運算子……………………………………………13
2.6.4 遺傳演算法之演算流程……………………………………………21
2.6.5 遺傳演算法之優缺點………………………………………………22
第三章 模式建立與研究方法……………………………………………………23
3.1 問題描述……………………………………………………………………23
3.2 數學模式……………………………………………………………………25
3.3編碼、解碼與適應度函數…………………………………………………27
3.4初始母體產生方法…………………………………………………………27
3.4.1 最鄰近法（一）……………………………………………………28
3.4.2 最鄰近法（二）……………………………………………………28
3.5 複製方法………………………………………………………………31
3.6 交配方法………………………………………………………………31
3.7 突變方法………………………………………………………………31
3.8 結束法則………………………………………………………………31
3.9 遺傳演算法流程………………………………………………………31
第四章 測試題目…………………………………………………………………33
4.1 測試題目介紹……………………………………………………………33
4.1.1 VRPTW 測試題目…………………………………………………33
4.1.2 VRPBTW 測試題目…………………………………………………33
4.1.3 VRPBTW 求解步驟…………………………………………………34
4.2 輸入/輸出畫面及操作說明……………………………………………37
第五章 實驗設計與結果…………………………………………………………40
5.1 田口方法簡介……………………………………………………………40
5.2 實驗設計…………………………………………………………………42
5.2.1 前期試驗………………………………………………………………44
5.2.2 田口實驗……………………………………………………………45
5.2.3 起始解效果之比較…………………………………………………47
5.3 測試VRPTW題庫…………………………………………………………49
5.4 測試VRPBTW題目…………………………………………………………50
第六章 結論與建議………………………………………………………………54
6.1 結論………………………………………………………………………54
6.2 建議………………………………………………………………………55
參考文獻…………………………………………………………………………56
附錄一 網路最佳解………………………………………………………………60
附錄二 VRPTW實驗數據…………………………………………………………61
附錄三 多車種實驗數據…………………………………………………………63
附錄四 單車種實驗數據…………………………………………………………73

中華僑泰物流股份有限公司。（2001,02）。[Online]. Available：
http://ctdc.com/about_c00.htm
全日物流股份有限公司。（2001,02）。[Online]. Available：
http://www.gpnstore.com.tw/equipm.asp
交通大學運輸工程與管理學系網路實驗室。（2001,03）。
[Online].Available：
http://www.tem.edu.tw/~network/
吳亮瑩，「單一物流中心配送車輛途程問題之研究－以遺傳演算法求解」，國
立成功大學工業管理研究所，碩士論文，1999。
林書銘，「禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究」，元智
大學工業工程所，碩士論文，1998。
宮大川、邱垂宏、王孔政、張國華、陳慧芬，「醫院公車運輸系統行進路線與
排班之規劃」，工業工程學刊，第18卷，第2期，pp.43-56，2001。
陳柏宏，「應用基因演算法於水火力發電排程問題之研究」，國立台灣工業技
術學院，博士論文，1995。
陳宏坤，「應用遺傳演算法於倉儲批發量販業之賣場設施佈置問題之究」，元
智大學工業工程所，碩士論文，2000。
梁俊卿，「遺傳演算法應用於自動倉儲系統撿取作業之規劃」，元智大學工業
工程所，碩士論文，1998。
張祖明，「多車種車輛路線問題啟發式解法之研究」，國立交通大學土木工程
研究所，碩士論文，1994。
張建邦，「應用遺傳演算法於服務系統設施細部佈置問題之研究－以醫院為
例」，元智大學工業工程所，碩士論文，1998。
敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學工業
工程所，碩士論文，1999。
徐俊誠，「車輛途程含取貨問題解法之研究」，大葉大學工業工程所，碩士論
文，2000。
黃冠華，「遺傳演算法於時窗限制下多車種車輛途程問題之應用」，東海大學
工業工程研究所，碩士論文，1999。
黃聖峰，「考量回程撿收之車輛途程問題研究」，大葉大學工業工程所，碩士
論文，1999。
曾維豪，「軟性時窗與回程撿收之車輛途程問題研究」，元智大學工業工程
所，碩士論文，2000。
經濟部商業司，物流經營管理實務，經濟部，中國生產力中心，1996。
廖亮富，「含時窗限制多部車車輛途程問題解算之研究」，元智大學工業工程
所，碩士論文，1998。
潘順興，「遺傳演算法於配送點選擇之應用」，中央大學資訊管理研究所，碩
士論文，1996。
鄭春生，品質管理，三民書局，台北，1995。
顏成佑，「基因演算法解算染性時窗車輛途程問題之研究」，元智大學工業工
程所，碩士論文，2000。
蘇木春、張孝德，機器學習、類神經網路模糊系統及基因演算法則，全華科技
圖書，1997。
寶成物流有限公司。（2001,02）。[Online]. Available：
http://netcity3.web.hinet.net/UserData/bocha/car.htm
Ahuja, R. K. and J. Orlin, “Developing Fitter Genetic
Algorithms,” Informs Journal on Computing, 1997, Vol.9,
No.3, pp.251-253.
Bodin, L., B. Golden, T. Doyle and W. Stewart, “Approximate
Traveling Salesman Algorithms,” Operation Research, 1980,
Vol. 128, pp. 549-711.
Bodin, L., B. Golden, A. Assad and D. Bull, “Routing and
Scheduling of Vehicles and Crews：The State of The Art,”
Computers & Operations Research, 1983, Vol. 10, pp.62-211.
Bowerman, R. L., P. H. Calamai and G. B. Hall, “The
Spacefilling Curve with Optimal Partition Heuristic for
Vehicle Routing Problem,” European Journal of Operational
Research, 1994, Vol. 76, pp. 128-142.
Derochers, M. snd T. W. Verhoog , “A New Heuristic or the
Fleet Size and Mix Vehicle Routing Problem,” Computers &
Operations Research, 1991, Vol. 18, No. 3, pp. 263-274.
Duhamel, C., J. Potvin and J. Rousseau, “A Tabu Search
Heuristic for the Vehicle Routing Problem with Backhauls and
Time Windows,” Transportation Science, 1997, Vol. 31, No. 1,
pp. 45-49.
Gheysens, F. G., B. Golden and A. Assad, “A Heuristic for
Determining Fleet Size and Composition,” Mathematical
Programming Studies, 1986, Vol. 26, pp. 233-236.
Golden, B., A. Assad, L. Levy and F. Ghysens, “The Fleet Size
and Mix Vehicle Routing Problem,” Computers & Operations
Research, 1994, Vol. 1, pp. 49-66.
Goeschalcky, M. and C. Jacobs-Blecha, “The Vehicle Routing
Problem with Backhauls,” European Journal of Operational
Research, 1998, Vol. 42, pp. 39-51.
Kershenbaum, A., “When Genetic Algorithms Work Best,” Informs
Journal on Computing, 1997, Vol.9, No.3, pp.254-255.
Mosheiov, G., “Vehicle Routing with Pick-Up and Delivery: Tour-
Partitioning Heuristics,” Computers & Industrial
Engineering, 1998, No. 3, pp. 669-684.
Nanry, W. P. and J. Barnes, “Solving the PickUp and Delivery
Problem with Time Windows using Reactive Tabu Search,”
Transportation Research, Part B 34, 2000, pp. 107-121.
Potvin, J., C. Duhamel and F. Guertin, “A Genetic Algorithm
for Vehicle Routing with Backhauls,” Applied Intelligence,
1996, Vol. 6, pp. 345-355.
Salhi, S. K. and R. Graham, “Incorporating Vehicle Routing
into the Vehicle Fleet Composition,” European Journal of
Operational Research, 1993, Vol. 66, pp. 313-330.
Thangiah, S. R., J. Potvin and T. Sum, “Heuristic Approaches
to Vehicle Routing with Backhauls and Time Windows,”
Computers & Operations Research, 1996, Vol. 22, No.11, 1996,
pp. 1043-1057.
Toth, P. and D. Vigo, “An Exact Algorithm for the Vehicle
Routing Problem with Backhauls,” Transportation Science,
1997, Vol. 31, No. 4, pp. 372-385.
Toth, P. and D. Vigo, “A Heuristic Algorithm for the Symmetric
and Asymmetric Vehicle Routing Problem with Backhauls,”
European Journal of Operational Research, 1999, Vol. 113, pp.
528-543.
VRPTW Benchmark Problems.（2001,03）.[Online]. Available：
http://www.cba.neu.edu/~msolomon/problems.htm