臺灣博碩士論文加值系統

物流中心的物品輸出頻繁，其與一般工廠之差異在於物流中心有高比例
的運輸成本，而路線之規劃傳統上被視為車輛途程問題。所謂車輛途程
問題是指物流中心指派有載重限制的車輛，配送貨物給已知需求、位置
的顧客，然後回物流中心，使得運送成本最小。本研究加入考慮所有車
輛有一全程時間限制並利用最鄰近法、節省法來求得初始解，接著使用
允許系統狀態往高於目前能量的狀態空間移動的模擬退火演算法來得到
較佳的解。以往模擬退火擾動得到一新解便判斷是否接受新解，而本文
從數個新解中找一最佳的，然後判斷接受與否，且隨著鄰近解定義之不
同有3種模擬退火改善初始解。最後，本研究並藉由實驗設計找出最佳
的參數設定。結果顯示，初溫、停止法則、冷卻率對求解品質有顯著影
響。

The transportation rate and cost of the goods for distribution
center(DC) is far more than that of a manufacturing factory.
The planning of the vehicle routing of the DCs is tradionally
treated as a vehicle routing problem(VRP). VRP is defined as a
set of vehicles of limited capacity at a DC serve all customers
exactly one and then return to the DC with minimized total
routing cost. This study considered that all vehicles have a
full time window and nearest and saving methods were employed
to get the initial solutions. Then the procedure utilized the
simulated annealing(SA) method to search for better solutions
by jumping off the trap to improve the initial solution.
Finally, an experimental design for the design parameters was
conducted for statistics analysis. The results show that the
factors of initial temperature, stopping rule and cooling rate
are significant for the solution quality.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii

第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與假設 2
1.4 研究步驟 3
1.5章節概要 4

第二章 文獻探討 5
2.1車輛途程問題之概論 5
2.1.1車輛途程問題之分類 5
2.1.2影響配送車輛途程問題之特性 9
2.1.3車輛途程問題求解方法介紹 10
2.1.4車輛途程之初始解解法 12
2.1.5初始解之改善 16
2.2車輛途程問題文獻探討 16
2.3模擬退火簡介 19
2.3.1 Metropolis演算法 20
2.3.2模擬退火演算法 21

第三章 模式構建與研究方法 24
3.1 符號定義 24
3.2 模式 24
3.3 研究方法 26
3.3.1 初始可行解之求得 26
3.3.2 模擬退火中鄰近解之定義 27
3.3.3模擬退火之步驟及流程 29

第四章 實驗結果分析與討論 36
4.1節點10之實驗結果 36
4.2節點30之實驗結果 40
4.3節點50之實驗結果 42

第五章 實驗設計 44
5.1節點10之實驗設計 44
5.2節點30之實驗設計 47
5.3節點50之實驗設計 50

第六章 結論與建議 54
6.1結論 54
6.2建議 55

參考文獻 56

附錄一 節點10之距離矩陣 60
附錄二 節點30之距離矩陣 61
附錄三 節點50之距離矩陣 62

莊志諒, "配送網路之設計研究", 交通大學運輸研究碩士論文, 1988

陳正元, "節省法與路線間交換改善法在車輛路線問題之研究", 交通大學土木研究碩士論文, 1992

徐吉田, "單一物流中心配送車輛途程問題之研究, 台灣工業技術學院管理技術研究所, 1993

張有恆、陳育祺、沈進成, "企業多目標配送車輛問題之研究", 工業工程學會論文集, 1993

詹弘康、張光華、張添盛, "多重迴圈物流配送路徑之啟發式規劃方法", 工業工程學會論文集, 1995

陳信翰, "自組織映射網路在車輛配送問題之研究", 雲林技術學院工業工程研究所, 1995

廖忠雄, "物流中心運輸服務途程規劃", 台灣大學工業工程研究所, 1996

黃珈昇, "物流體系中貨櫃運送車輛途程規劃問題之探討", 中原大學工業工程研究所, 1996

陳功欽,"一般性車輛途程之探討",元智工學院工業工程研究所,1996

徐明輝, "多部車一般性車輛途程解算法之研究", 元智工學院工業工程研究所, 1997

Bodin, L., B. Golden, A. Assad, and D. Bull, "Routing and Scheduling of Vehicle and Crews," Computers & Operation Research, Vol. l0, No. 2, pp. 79-301, 1983.

Bodin, L. and B. Golden, "Classification in Vehicle Routing and Scheduling," Networks, Vol. 11, pp. 97-108, 1981.

Bonmi, E. and J. Lutton, "The N-city Traveling Salesman Problem: Statistical Mechanics Algorithm and the Metropolis Algorithm," SIAM Review, Vol. 26, No. 4, pp. 551-568, 1984.

Burkard, R. E. and F. Rendle, "A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization," European Journal of Operational Research, Vol. 17, pp. 169-174, 1984.

Christophe D. and J. Y. Potvin, "A Tabu for the Vehicle Routing Problem with Backhauls and Time Windows," Transportation Science, Vol. 31, No. 1, pp.49-59, 1997

Clarke, G. and W. Wright, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operation Research, Vol. 12, pp. 568-581, 1964.

Fred G., and Harvey J. G., "New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence," European Journal of Operation Research, Vol. 39, pp.119-130., 1989.

Gillett B. and L. Miller, "A Heuristic Algorithm for the Vehicle Dispatch Problem," Operation Research, Vol. 22, pp. 340-349, 1974.

Golden B. M. and H. Nguyen, "Implementing Vehicle Routing Algorithm," Networks, Vol. 7, pp. 113-148, 1977.

Golden, B. L. and C. C. Skiscim, "Using Simulated Annealing to Solving Routing and Location Problems," Naval Research Logistics Quarterly, Vol. 33, pp. 261-279, 1986.

Golden, B. L. and A. A. Assad , "Vehicle Routing: Method and Studies," North-Holland, New York, pp.7-45, 1988.

Golden, B. L. and C. C. Skiscim, "Optimization by Simulated Annealing: A Preliminary Computational Study for the TSP," Proceedings of the 1983 winter Simulated Annealing Conference, Washington, D. C.

Jean-Yves P. and B. L. Rousseau, "The Vehicle Routing Problem with Time Windows Part1: Tabu Search," Informs Journal on Computing, Vol. 8, No. 2, pp. 158-164, 1996

Kirkpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi, "Optimization Simulated Annealing," Science, Vol. 220, No. 4598, pp. 671-680, 1983.

Newton R. and W. Thomas, "Design of School Bus Routes by Computer," Socio-Economic Planning Sci., pp. 75-85, 1969.

Panagiotis K., "A Simulated Annealing Procedure for Single Row Layout Problems in Flexible Manufacturing Systems," International Journal of Production. Research, Vol. 30, No. 4, pp. 717-732, 1992.

Sateesh, C. and K. Pradip, "Vehicle Routing in Large Organization: A Case Study", International Journal of Operation & Production Management, Vol. 12,No. 3, pp. 71-78, 1991.