臺灣博碩士論文加值系統

隨著經濟的發展，為了滿足專業分工的需求，配銷通路已有極大的改變，現代的物流配送過程中，車輛所佔的地位極為重要，如果能在派車前將路線經計算後再指派路徑，將可大幅減少車輛運輸成本。因顧客水準逐漸提高，對於貨品送達時間要求也相對提高。因此，具時窗車輛途程問題(Vehicle Routing Problem with Time Window, VRPTW)的相關研究，也應運而生。
在以往的相關研究中，VRPTW的時間變數(時間窗)，通常被視為明確的數值，但在現實生活中，時間變數時常變動且不易確定，例如：交通號誌、車潮眾多等等，皆會影響到抵達時間，因此本研究將針對具模糊時窗車輛途程問題(Vehicle Routing Problem with Fuzzy Time Window, VRPFTW)進行探討，將時間變數轉換為模糊型態，並利用本研究所構建的演算法，求得較佳的車輛路徑。
本研究所構建之模式係以車輛最少、距離最短為目標，演算法分為3個階段，第一階段運用插入法來求得起始解。第二階段為了減少車輛數量，運用??interchange 1-0節點交換法，改善起始解。第三階段以模擬退火法跳脫區域最佳解，祈能產生較佳的改善解。
最後，利用Solomon分類標竿試題，測試演算法的效率，並與先前學者研究具硬時窗限制的VRPTW最佳解比較，研究發現，本研究提出之演算法皆與國內外學者接近或更好，並具能在短時間內，求得較佳解。另一方面，VRPFTW的結果顯示，服務水準係數的高低，會影響目標成本與顧客滿意程度，係數越高，顧客滿意程度越好，但需花費較多成本；係數越低，顧客滿意程度越差，所需花費成本較少。本研究所建構之VRPFTW模式及其演算法可幫助決策者依照不同顧客的性質，來調整服務水準係數，以產生較佳之車輛途程規畫。

This paper proposes a new hybrid meta-heuristic algorithm for the vehicle routing problem with fuzzy time window(VRPFTW). In the transportation business, time windows are uncertain and the deviation of service time from the customer-specific time window determines the customer’s satisfaction level. The proposed algorithm consists of an initial module with fuzzy and defuzzy operation on the time windows, a car-reducing module, and a distance reduction module. The objective function of the proposed algorithm is to find the minimum number of vehicles and then the shortest total routing distance. The insertion method, the λ-interchange, and the simulated annealing algorithm are introduced in the initial, the car-reducing, and the distance reduction modules respectively.
Experiments are compared with the world classic Solomon’s problems. The empirical results on VRPTW have shown the proposed algorithm has near best-solution performance with quick computing time. Moreover, the model of VRPFTW is established and analyzed. This new hybrid meta-heuristic algorithm can help the managers to determine, a cost-effective routing plan for VRPFTW, that is essential in the field of modern supply chain delivery.

目 錄
摘　要 i
ABSTRACT ii
誌　謝 iii
目 錄 iv
表目錄 vi
圖目錄 vii
1. 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍 3
1.4 研究流程 4
2. 文獻探討 7
2.1 車輛途程問題(Vehicle Routing Problem, VRP) 7
2.2 具時窗限制之車輛途程問題(Vehicle Routing Problem with Time Window, VRPTW) 10
2.2.1 時間窗 10
2.2.2 VRPTW的基本模式 11
2.3 模糊時窗限制之車輛途程問題(Vehicle Routing Problem with Fuzzy Time Window, VRPFTW) 13
2.3.1 模糊理論 13
2.3.2 模糊運算 14
2.3.3 時間窗模糊化 15
2.4 VRP求解方法 15
2.4.1 簡單啟發式解法 16
2.4.2 路線交換法 19
2.4.3 巨集啟發式解法 21
2.5 文獻小結 28
3. 研究方法 29
3.1 問題定義與假設 29
3.2 數學模式之建構 30
3.3 模糊與解模糊 32
3.3.1 模糊化 32
3.3.2 解模糊化 33
3.4 起始解建構模組 34
3.5 車輛縮減建構模組 36
3.6 路線改善模組 38
3.6.1 模擬退火法(Simulated Annealing，SA) 38
3.6.2 路線交換法 41
4. 結果與分析 42
4.1 測試例題說明 42
4.2 實驗環境 43
4.3 參數設定 43
4.4 實驗結果 44
4.4.1 本研究起始解 44
4.4.2 VRPTW最佳解 45
4.4.3 VRPFTW最佳解 48
5. 結論 50
參考文獻 51
附錄 56

中文
王耿彬（2001）。應用遺傳演算法於低溫冷凍物流中心之車輛配送排程規劃（碩士論文，朝陽科技大學，2001）。全國博碩士論文資訊網，089CYUT0031018。
王暢湘（2006）。多場站多車種車輛路線問題之巨集啟發式演算法研究（碩士論文，中華大學，2006）。全國博碩士論文資訊網，094CHPI0425006。
吳琴玲（2000）。物流配送系統之區位-途程問題研究（碩士論文，國立雲林科技大學，2000）。全國博碩士論文資訊網，088YUNTE031020。
李仁鐘、吳宗祐、周碩聰（2007）。改良型螞蟻演算法結合模擬退火法於車輛途程問題之研究。2007數位科技與創新管理研討會（頁717-725）。
柯景文（2002）。禁制搜尋法於動態車輛巡迴路線問題之研究（碩士論文，逢甲大學，2002）。全國博碩士論文資訊網，090FCU05118008。
高秀梅（2003）。蟻群最佳化演算法於時窗限制之車輛途程問題的研究（碩士論文，元智大學，2003）。全國博碩士論文資訊網，091YZU00031030。
陳宏昇（2006）。以模擬退火演算法求解時間視窗限制車輛途程問題（碩士論文，華梵大學，2006）。全國博碩士論文資訊網，094HCHT0396049。
陳建甫（2006）。以基因搜尋法求解多桶格車輛途程問題（碩士論文，南台科技大學，2006）。全國博碩士論文資訊網，094STUT0041008。
陳隆熙（2002）。一個解決TSP問題最佳解的穩定方法—以TA 演算法為例（碩士論文，大葉大學，2002）。全國博碩士論文資訊網，090DYU00030021。
許富雄（2006）。以模擬退火法結合區域搜索法應用於載重限制車輛途程問題（碩士論文，華梵大學，2006）。全國博碩士論文資訊網，094HCHT0396042。
黃至穩（2007）。多重補貨點接駁車輛路線問題之研究（碩士論文，中華大學，2007）。全國博碩士論文資訊網，096CHPI5425023。
萬紘杰（2006）。載運乘客時允許車輛暫停等待之撥召公車問題（碩士論文，國立清華大學，2006）。全國博碩士論文資訊網，095NTHU5031032。
郭佳林（2005）。求解具時間窗之多趟次車輛途程問題（碩士論文，國立交通大學，2005）。全國博碩士論文資訊網，093NCTU5423032。

劉奕青（2003）。自動販賣機存貨途程問題之研究（碩士論文，元智大學，2003）。全國博碩士論文資訊網，091YZU00031023。
魏宗徹（2001）。整合時窗限制與回程撿收之多車種車輛途程問題（碩士論文，元智大學，2001）。全國博碩士論文資訊網，089YZU00030019。
羅敏華（2003）。蟻群最佳化演算法於載重限制之車輛途程問題的研究（碩士論文，元智大學，2003）。全國博碩士論文資訊網，091YZU00031032。
蘇志峰（2000）。具時窗限制之多場站車輛路線問題之研究（碩士論文，國立成功大學，2000）。全國博碩士論文資訊網，090NCKU5041044。

英文
Bartholdi, J. J., Platzman, L. K. (1988). Heuristics Based on Space-filling Cruves for Combinational Problems in Euclidean Space, Management Science, 34, 291-305.
Bent, R. and Hentenryck, P. V. (2001). A Two-stage Hybrid Local Search for the ehicle Routing Problem with Time Windows. Department of Computer Science, University of Brown, Tech. Rep. CS-01-06.
Berger, J., Barkaoui, M., and Bräysy, O. (2003). A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows, Information Systems and Operations Research, 41, 179-194.
Bodin, L., Golden, B., Assad, A., Ball, M. (1981). The state of the art in the routingand scheduling of vehicles and crews. U.S. Department of Transportation Urban Mass Transportation Administration, 1-52.
Bodin, L., Golden, B., Assad, A., Ball, M. (1983). Routing and Scheduling of Vehicles and Crews: the state of the art, Computers and Operations Research, 10, 63-211.
Clark, G., Wright, J. W. (1964). Scheduling of Vehicles from A Central Depot to A Number of Delivery Points, Operations Research, 12, 568-581.
Cordeau, J. F., Larporte, G., and Mercier, A.(2001). A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows, Journal of the Operational Research Society, 52, 928-936.


Czech, Z. J. and Czarnas, P. (2002). A Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows. in Proc. 10th Euromicro Workshop on Parallel, 376-383.
Dantzig, G.B. and Ramser, J.M. (1959). The Truck Dispatching Problem, Management Science, 6, 80-91.
Dorigo, M. (1992). Optimization Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano.
Dueck, G., Scheuer, T. (1990). Threshold accepting: A general purpose optimization algorithm superior to simulated annealing, Journal of Computational Physics, 90, 161-175.
Gambardella, L., Taillard, E. and Agazzi, G. (1999). MACSVRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. IDSIA, Lugano, Switzerland, Tech. Rep. IDSIA-06-99.
Gillett, E. B., Miller, L. R. (1974). A Heuristic Algorithm for The Vehicle Dispatch Problem, Operations Research, 22, 340-349.
Glover, F. (1989). Tabu search-Part I, ORSA Journal on Computing, 13, 190-206.
Glover, F. (1989). Tabu search-Part E, ORSA Journal on Computing, 1, 190-206.
Haibing, L. and Andrew, L. (2003). Local Search with Annealing-Like Restarts to Solve the VRPTW, European Journal of Operational Research, 150, 115-127.
Homberger, J.(2000), Verteilt-parallele Metaheuristiken Zur Tourenplanung. Gaber, Wiesbaden.
Homberger, J. and Gehring, H.(1999). Two Evolutionary Meta-heuristics for the Vehicle Routing Problem with Time Windows, INFOR, 37, 297-318.
Ibaraki, T., Imahori, S., Kubo, M., Masuda, T., Uno, T., and Yagiura, M. (2005). Effective Local Search Algorithms for Routing and Scheduling Problems with General Time Window Constraints, Transportation Science, 39, 206-232.
Jiafu Tang, Zhendong Pan, Richard Y.K. Fung, Henry Lau (2009). Vehicle routing problem with fuzzy time windows, Fuzzy Sets and Systems, 160, 683–695.
Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P. (1983). Optimization by simulated annealing, Science, 200, 4956, 671-680.
Koskosidis, Y., Powell, W., and Solomon, M. (1992). An Optimization-Based Heuristic for Vehicle Routing and Scheduling With Soft Time Window Constraints, Transportation Science, 26, 69-85.
Lin, S. (1965). Computer Solutions of The Traveling Salesman Problem, Bell System Technical Journal, 44, 2245-2269.
Mester, D. (2002). An Evolutionary Strategies Algorithm for Large Scale Vehicle Routing Problem with Capacitate and Time Windows Restrictions. In Conf. Mathematical and Population Genetics, Univ. of Haifa, Israel.
Or, I. (1976). Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. Ph. D. Dissertation, Dept. of Industrial Engineering and Management Sciences, University of Northwestern.
Osman, I.H. (1993). Metastrategy Simulated Annealing and Tabu Search Algorithms for The Vehicle Routing Problem, Annals of Operations Research, 41, 421-451.
Potvin, J. Y., Kervahut, T., Garcia, B. L., and Rousseau, J. M. (1996). The Vehicle Routing Problem With Time Windows Part I: Tabu Search, INFORMS Journal on Computing, 8, 2, 158-164.
Rochat, Y. and Taillard, E.D.(1995). Probabilistic Diversification and Intensification in Local Search for Vehicle Routing, Journal of Heuristics, 1, 147-167.
Rousseau, L.-M., Gendreau, M., and Pesant, G. (2002). Using Constraint-based Operators to Solve the Vehicle Routing Problem with Time Windows, Journal of Heuristics, 8, 43-58.
Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H. and Dueck, G. (2000). Record Breaking Optimization Results Using the Ruin and Recreate Principle, Journal of Computational Physics, 159, 139-171.
Shaw, P. (1997). A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. Department of Computer Sciences, University of Strathclyde, Tech. Rep, APES group.


Shaw, P. (1998). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. in Proc. of the Fourth International Conf. Principles and Practice of Constraint Programming, New York, 417-431.
Solomon, M. M. (1983). Vehicle Routing and Scheduling with Time Window Constraints: Models and Algorithms. Ph. D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania.
Sutcliffe, C. and Board, J. (1990). Optimal Solution of a Vehicle-Routing Problem: Transporting Mentally Handicapped Adults to an Adult Training Centre, Journal of Operational Research Society, 14, 1, 61-67.
Taillard, E., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J. Y. (1997). A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows, Transportation Science, 31, 170-186.
Zadeh, L. A. (1965). Fuzzy Set, Information and Control , 338-353.