隨著科技的進步、消費者生活水準的提高及購物習慣的改變，帶動了物流業的興盛，商用車營運操作(Commercial Vehicle Operations, CVO)已成為智慧型運輸系統(Intelligent Transportation Systems, ITS)的重要課題之一。而企業為了因應顧客更快速及準時的供貨配送要求，考慮客戶服務時間的時窗限制下車輛巡迴路線問題(Vehicle Routing Problem with Time Windows, VRPTW)益受重視。本研究以兩階段群聚法(two-stage clustering approach)，改良的時間切割法(improved time-divided procedure)和巨集啟發式方法(meta-heuristics)求解時窗車輛巡迴路線問題。
研究中，經由空間指標(Nearest Neighbor Index, NNI)的分析，可於不同的客戶分佈情形下選擇適當的求解方式。當客戶分佈位置較集中時，以兩階段的群聚方式結合SOM與K-means配合群聚分析指標(Davies Bouldin index, DB)決定最佳群數，對客戶進行適當的區隔配送。當客戶位置分佈較為分散的情形下，以經過改良的時間切割法，同時考量客戶之距離及時窗兩因素，適當的選擇每台車的起始服務點，而後將時間相近的客戶分配由不同的車輛進行服務，並以成本函數的衡量方式求得較佳的商用車輛巡迴路線初始解。最後再透過巨集啟發式方法中的禁制搜尋法(tabu search)結合路線交換的改善，進而獲得車輛巡迴路線的最佳解。
為驗証本研究方法之可行性，以Solomon題庫與一實際案例進行測試，實驗結果顯示本研究所提出的方法適用於求解軟時窗車輛巡迴路線問題。

Commercial Vehicle Operations (CVO), one of the major Intelligent Transportation Systems (ITS) program, aims at applying advanced technologies to commercial vehicle operations. Vehicle Routing Problem with Time Windows (VRPTW) is an important aspect of Commercial Vehicle Operations. This research focuses on using a two-stage clustering method, improved time-divided procedure, and heuristic approach for improving vehicle routing in VRPTW.
The spatial distribution of the customer locations, such as evenly spaced, random, and clustered distribution, is measured by the Nearest Neighbor Index (NNI) to determine the degree of spatial clustering. If the degree of spatial clustering is small (clustered data), the two-stage clustering method, a combination of the Self-Organizing Map (SOM) and the K-means method, is integrated with Davies-Bouldin index (DB) to determine the best clustering results during the initialization phase of an insertion heuristic for VRPTW. Improved time-divided procedure is applied when the degree of spatial clustering is large (randomly distributed or dispersed data) and the two-stage clustering method cannot efficiently cluster the customers. The customers are sorted according to their service time windows and divided into different groups. An algorithm is then proposed to solve the initialization phase of an insertion heuristic using improved time-divided procedure. Tabu search will be coped to improve the vehicle routing after the initialization phase of an insertion heuristic. The general tabu search explores part of the solution space by moving solutions at each iteration to the best neighbor of the current solution, even if this leads to a deterioration of the objective function.
Experimental examples are selected from the Solomon’s benchmarks and a case study, and the numerical results show the effectiveness of the proposed methods and algorithms to solve VRPTW.

摘要------------------------------------------I
Abstract--------------------------------------II
誌謝------------------------------------------IV
目錄------------------------------------------V
圖目錄----------------------------------------VII
表目錄----------------------------------------VIII
第一章 前言----------------------------------1
1.1研究背景與動機-----------------------------1
1.2研究目的-----------------------------------3
1.3研究範圍-----------------------------------4
1.4研究流程-----------------------------------5
第二章 文獻探討------------------------------8
2.1群聚分析技術-------------------------------8
2.1.1群聚技術及應用---------------------------14
2.1.2兩階段群聚法-----------------------------18
2.2群聚適切性指標-----------------------------21
2.3空間分析指標-------------------------------24
2.4車輛巡迴路線問題及相關的求解方法-----------27
2.4.1車輛巡迴路線相關問題---------------------27
2.4.2車輛巡迴路線問題的求解方式---------------33
2.5小結---------------------------------------45
第三章 研究架構與方法------------------------46
3.1研究架構-----------------------------------46
3.2 客戶位置分佈之分析------------------------49
3.3 初始解建構方式----------------------------49
3.3.1 以兩階段群聚法分區配送------------------49
3.3.2 改良之時間切割法------------------------55
3.4 路線改善模式------------------------------61
第四章 實驗分析與比較------------------------62
4.1實驗問題-----------------------------------62
4.1.1 Solomon題庫-----------------------------62
4.1.2 實際案例—環緯食品流通公司--------------63
4.2目前公開最佳解-----------------------------64
4.2.1 Solomon題庫--------------------------64
4.2.2 實際案例之目前最佳結果---------------66
4.3本研究之實驗結果---------------------------66
4.3.1 Solomon題庫之實驗結果----------------66
4.3.2 實際案例之實驗結果-------------------78
4.4結果分析與比較-----------------------------79
第五章 結論與建議----------------------------84
5.1結論---------------------------------------84
5.2建議---------------------------------------85
參考文獻--------------------------------------86

[1]王浩永(2004)，群聚參數與群聚適切性的分析與應用，碩士論文，朝陽科技大學資訊管理研究所，台中。
[2]吳沛儒(2004)，任務型共乘接駁計程車之規劃與設計，碩士論文，逢甲大學交通工程與管理學研究所，台中。
[3]李洪鑫(2000)，含時間窗車輛途程問題各演算法適用範圍之探討，碩士論文，東海大學工業工程研究所，台中。
[4]沈介文(2001)，「綠色招募之研究—潛在員工企業環境倫理認知與其求職傾向之關係」，人力資源管理學報，第一卷，第一期，第121-141頁。
[5]卓裕仁(2001)，以巨集啟發式方法求解多車種與週期性車輛路線問題之研究，碩士論文，交通大學運輸工程與管理系，新竹。
[6]周淑蓉(2004)，以群聚及禁制搜尋法求解含時窗限制之車輛巡迴路線問題，碩士論文，朝陽科技大學資訊管理研究所，台中。
[7]易德華(1998)，軟時窗車輛巡迴問題之研究，碩士論文，中央大學土木工程學系，桃園。
[8]林育臣(2002)，群聚技術之研究，碩士論文，朝陽科技大學資訊管理研究所，台中。
[9]林書銘(1998)，禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究，碩士論文，元智大學工業工程研究所，桃園。
[10]柯景文(2002)，禁制搜尋法於動態車輛巡迴路線問題之研究，碩士論文，逢甲大學交通工程與管理學系，台中。
[11]除守道(1994)，應用非監督性類神經網路於SPOT衛星影像分類最佳化之研究，碩士論文，中原大學太空科學研究所，中壢。
[12]張廷吉(1999)，考慮派車時段與載重均衡之車輛途程規劃問題，碩士論文，逢甲大學工業工程系，台中。
[13]敖君瑋(1998)，禁制搜尋法於軟性時窗限制之車輛途程問題研究，碩士論文，元智大學工業工程研究所，桃園。
[14]陳百傑(2002)，以啟發式演算法求解時窗限制車輛途程問題，碩士論文，中原大學工業工程學系，中壢。
[15]陳契伸(2001)，硬性/軟性時窗限制之車輛途程問題研究，碩士論文，中原大學工業工程學系，中壢。
[16]陳彥良、許昌齡，資料群聚性之研究，http://www.mgt.ncu.edu.tw/~ylchen/。
[17]陳致元(2001)，單一物流中心車輛途程問題求解模式之空間分析研究，碩士論文，台灣大學地理環境資源研究所，台北。
[18]葉怡成(2002)，類神經網路模式應用與實作，儒林圖書有限公司，第一版。
[19]廖建倫(2002)，「整合自適應共振理論Ⅱ神經網路與遺傳演算法為輔之K-Means於資料採礦之研究」，工業工程學刊，第十九卷，第四期，第64-70頁。
[20]蔡玉晶(2004)，以複合啟發式演算法求解硬式時窗限制下車輛途程問題，碩士論文，中原大學工業工程學系，中壢。
[21]蔡宛妮，(2001)，應用自我組織網路於直接負載控制績效評估之研究，碩士論文，中原大學電機工程研究所，中壢。
[22]鍾文杰(2000)，整合自組織映射圖網路與遺傳演算法為輔之K-Means於顧客關係管理中，碩士論文，台北科技大學生產系統工程與管理研究所，台北。
[23]簡順源(2001)，整合自組織映射圖網路與遺傳演算法為基礎之資料採礦技術於市場區隔之應用，碩士論文，台北科技大學生產系統工程與管理研究所，台北。
[24]Abidi, S. S. R. and Ong, J. (2000), “A Data Mining Strategy for Inductive Data Clustering: A Synergy Between Self-Organizing Neural Networks and K-Means Clustering Techniques,” TENCON Proceedings, Vol. 2, pp. 568-573.
[25]Anderberg, M. R. (1973), Cluster Analysis for Application, Academic, Inc.
[26]Ankerst, M., Breunig, M., Kriegel, H. P., and Sander, J. (1999), “OPTICS: Ordering Points to Identify the Clustering Structure,” In Proceedings ACM SIGMOD Conference on Management of Data, Philadelphia, pp. 49-60.
[27]Balakrishnam, P. V., Cooper, M. C., Jacob, V. S., and Lewis, P. A. (1994), “A Study of the Classification Capabilities of Neural Networks Using Unsupervised Learning－A Comparison K-means Clustering,” Psychomertrika, Vol. 59, No. 4, pp. 509-525.
[28]Bandyopadhyay, S. and Maulik, U. (2001), “Nonparametric Genetic Clustering: Comparison of Validity Indices,” IEEE Transactions on System, Man, and Cybernetics-Part C: Applications and Reviews, Vol. 31, No. 1, pp. 120-125.
[29]Bezdek, J. C. (1981), Pattern Recognition With Fuzzy Object Function Algorithms, Plenum, Inc., pp. 65-70.
[30]Bezdek, J. C. and Pal, N. R. (1998), “Some New Indexes of Cluster Validity,” IEEE Transactions on System, Man, and Cybernetics-Part B: Cybernetics, Vol. 28, pp. 301-315.
[31]Bodin, L. and Golden, B. (1981), “Classification in Vehicle Routing and Scheduling,” Networks, Vol. 11, pp. 97-108.
[32]Bodin, L., Golden, B., Assad, A., and Ball, M. (1983), “Routing and Scheduling of Vehicle and Crews: The State of the Art,” Computer & Operations Research, Vol. 10, No. 2, pp. 63-211.
[33]Bradley, P. S. and Fayyad, U. M. (1998), “Refining Initial Points for K-means Clustering,” Proceedings of the Fifteenth International Conference on Machine Learning, San Francisco, pp. 91-99.
[34]Chen, G. and Dai, Y. (2004), “A New Distance Measurement for Clustering Tim-Course Gene Expression Data,” 26th Annual International Conference of the IEEE EMBS, San Francisco.
[35]Clark, P. J. and Evans, F. C. (1954), “Distance to Nearest Neighbor as a Measure of Spatial Relationships in Populations,” Ecology, Vol. 35, pp. 445-453.
[36]Clarke, G. and Wright, J. W. (1964), “Scheduling of Vehicles From a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, pp. 568-581.
[37]Cramer, B. E. and Armstrong, M. P. (1997), “Interpolation of Spatially Inhomogeneous Data Sets: An Evaluation of Parallel Computation Approaches,” GIS/LIS ‘97 Annual Conference and Exposition Proceedings, Ohio, pp. 643-652.
[38]Davies, D. L. and Bouldin, D. W. (1979), “A Cluster Separation Measure, ” IEEE Transactions on Pattern Anaysis and Machine Intelligence, Vol. 1, pp. 224-227.
[39]Dubes, R. and Jain, A. K. (1988), “Validity Studies in Clustering Methodologies,” Pattern Recognition, Vol. 11, pp. 235-245.
[40]Ester, M., kriegel, H. P., Sander, J., and Xu, X. (1996), “Density-Based A1gorithm for Discovering C1usters in Large Spatial Databases With Noise,” In Proceedings Conference on Knowledge Discovery and Data Mining, Portland, pp. 226-231.
[41]Forgy, E. (1965), “Cluster Analysis of Multivariate Data: Efficiency Versus Interpretability of Classifications,” Biometrics, Vol. 21, p. 768.
[42]Gillett, B. and Miller, L. (1974), “A Heuristic for the Vehicle Dispatching Problem,” Operations Research, Vol. 22, pp. 340-349.
[43]Glover, F. and Laguna, M. (1997), Tabu search, Kluwer Academic, Inc.
[44]Guha, S., Rastogi, R., and Shim, K. (1998), “CURE: An Efficient Clustering Algorithm for Large Databases,” In ACM SIGMOD International Conference on Management of Data, Seattle, pp. 73-84.
[45]Guha, S., Rastogi, R., and Shim, K., (1999) “ROCK: A Robust Clustering Algorithm for Categorical Attribute,” In 15th Interational Conference on Data Engineering, Sydney, pp. 512-521.
[46]Han, J. and Kamber, M. (2000), Data Mining: Concepts and Techniques, Morgan Kaufmann, Inc.
[47]Homberger, J. and Gehring, H. (2005), “A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem With Time Windows,” European Journal of Operational Researh, Vol. 162, pp. 220-238.
[48]Karypis, G., Han, E. H., and Kumar, V. (1999), “CHAMELEON: Hierarchical Clustering Using Dynamic Modeling,” IEEE Computer, Vol. 32, No. 8, pp. 68 –75.
[49]Kaufman, L. and Rousseeuw, P. J. (1990), Finding Groups in Data: An Introduction to Clustering Analysis, John Wiley & Sons, Inc.
[50]Kint, V., Meirvenne, M., Nachtergale, L., Geudens, G., and Lust, N. (2003), “Spatial Methods for Quantifying Forest Stand Structure Development: A Comparison Between Nearest-Neighbor Indices and Variogram Analysis,” Forest Science, Vol. 49, No. 1, pp. 36-49.
[51]Kohonen, T. (1990), “The Self-Organizing Map,”Proceedings of the IEEE, Vol. 78, No. 9, pp. 1481-1480.
[52]Koskosidis, Y., Powell, W., and Solomon, M. (1992), “An Optimization-Based Heuristic for Vehicle Routing and Scheduling With Soft Time Window Constraints,” Transportation Science, Vol. 26, pp. 69-85.
[53]Kuo, R. J., Ho L. M., and Hu, C. M. (2002), “Integration of Self-Organizing Feature Map and K-means Algorithm for Market Segmentation,” Computer & Operations Research, Vol. 29, pp. 1475-1493.
[54]Lau, H. C., Sim, M., and Tec, K. M. (2003), “Vehicle Routing Problem With Time Windows and A Limited Number of Vehicles,” European Journal of Operational Research, Vol. 148, pp. 559-569.
[55]Li, H. and Lim, A. (2003), “Local Search With Annealing-Like Restarts to Solve the VRPTW,” European Journal of Operational Research, Vol. 150, pp. 115-127.
[56]Lin, S. and Kernighan, B. (1973), “An Effective Heuristic Algorithm for the Traveling Salesmen Problem,” Operations Research, Vol. 44, pp. 498-516.
[57]MacQueen, J. (1967), “Some Methods for Classification and Analysis of Multivariate Observations,” Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, pp. 281-297.
[58]Maulik, U. (2002), “Performance Evaluation of Some Clustering Algorithms and Validity Indices,” IEEE Transactions on Pattern analysis and machine intelligence, Vol. 24, No. 12, pp. 1650-1654.
[59]Michael, J. A. and Gordon, L. (1996), Data Mining Techniques for Marketing Sales and Customer Support, John Wiley & Sons, Inc.
[60]Ng, R. and Han, J. (1994), “Efficient and Effective Clustering Method for Spatial Data Mining,” In Proceedings of the 20th VLDB Conference, Santiago, pp. 144-155.
[61]Nocera, F. D., Capponi, C., and Ferlazzo, F. (2004), “Finding Geometrical Associations Betwween Meaningful Objects in the Web: A Geostatistical Approach,” PsychNology Journal, Vol. 2, No. 1, pp. 84-98.
[62]Osman, I. H., and Laporte, G. (1996), “Metaheuristics: A Bibliography,” Annals of Operations Research, Vol. 63, pp. 513–623.
[63]Pena, J. M., Lozano, J. A., and Larranaga, P. (1999), “An Empirical Comparisons of Four Initialization Methods for the K-means Algorithm,” Pattern Recognition Letters, Vol. 20, pp. 1027-1040.
[64]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, Vol. 8, No. 2, pp. 158-164.
[65]Prakash, D. G., Prasanna, L., and Regener, B. D. (2005), “Computational Microstructure Analyzing Technique for Quantitative Characterization of Shrinkage and Gas Pores in Pressure Die Cast AZ91 Magnesium Alloys,” Computation Materials Science, Vol. 32, pp. 480-488.
[66]Punj, G. and Steward, D. W. (1983), “Cluster Analysis in Marketing Research: Review and Suggestions for Applications,” Journal of Marketing Research, Vol. 20, pp. 34-48.
[67]Sgarma, S. (1996), Applied Multivariate Techniques, John Wiley & Sons, Inc., pp. 212-216.
[68]Sheikholeslami, G., Chatterjee, S., and Zhang, A. (1998), “WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases,” In Proceedings of the 24th VLDB Conference, New York, pp. 428-439.
[69]Smith, K. A. (1999), “Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research,” INFORMS Journal on Computing, Vol. 11, No. 1, pp. 15-34.
[70]Solomon, M. M. (1987), “Algorithms for The Vehicle Routing and Scheduling Problems With Time Window Constraints,” Operations Research, Vol. 35, No. 2, pp. 254-265.
[71]Solomon, M. M. (2005), “Best Known Solutions Identified by Heuristics,” http://web.cba.neu.edu/~msolomon/heuristi.htm.
[72]Sun, Y., Zhu, Q., and Chen, Z. (2002), “An Iterative Initial-Points Refinement Algorithm for Categorical Data Clustering,” Pattern Recognition Letters, Vol. 23, pp. 875-884.
[73]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, Vol. 14, No. 1, pp. 61-67.
[74]Thompson, P. M. and Psaraftis, H. (1993), “Cyclic Transfer Algorithms for Multi-Vehicle Routing and Scheduling Problems,” Operations Researc, Vol. 41, pp. 935-946.
[75]Vesanto, J. and Alhoniemi, E. (2000), “Clustering of the Self-Organizing Map,” IEEE transactions on Neural Networks, Vol. 11, No. 3, pp. 586-600.
[76]Wang, W., Yang, J. and Muntz, R. (1997), “STING: A Statistical Information Grid Approach to Spatial Data Mining,” In Proceedings of the 23th VLDB Conference, Athens, pp. 186-195.
[77]Waters, C. D. J. (1984), “Interactive Vehicle Routing,” Journal of Operational Research Society, Vol. 35, No. 9, pp. 821-826.
[78]Willard, J. A. G. (1989), Vehicle Routing Using R-Optimal Tabu Search, MSc Thesis, Management School, Imperial College.