經營一個港埠，國家需投入大量的資金、設備與人力，而港埠設立後的各項設施、經營績效良窳，對國家經濟發展影響甚钜。船舶停泊作業為海運過程中首要作業，效率的好壞直接影響到後續作業的運作，而國內目前在停泊作業上，航商、代理行與港口船席調配小組以會議的方式進行，此種方式固然可以解決問題，但是能做出最佳決策，值得商榷。
本研究在模式構建上主要是以參予船席指派決策的航商、港埠當局為主，在考量航商在港時間最小化、港埠當局營運成本最小化來構建多目標模式，並以車輛繞徑的角度解釋船席指派問題。問題的求解則是以C語言自行撰寫類免疫演算法配合模糊理論進行求解。
以自行設計的小型範例配合窮舉法來確認模式的正確性，並利用此結果來進行演算法的證確性測試；演算法參數的選擇的上，則是利用了ANOVA檢定找出較佳的參數。此外，設計了不同規模、不同船舶到達型態範例，以禁忌搜尋法、類免疫演算法進行求解，比較兩者的求解品質。最後利用基隆港民國95年5月22日至5月28日船席指派紀錄作為實証資料、敏感度分析。
本研究將「船席」視為車輛繞徑中的「車輛」，「船舶」視為「需求點」，且假設需求點的作業時間、節線成本會因為車輛、需求點的不同而有所差異，以此方式解釋船席指派問題並構建多目標模式。
窮舉法的結果確認模式的正確性(有解)，而禁忌搜尋法、類免疫演算法都可以找到與窮舉法相同的觧，證實了演算法的正確性。不同類型的範例中，經過統計檢定兩種演算法的求解結果，發現類免疫演算法在大型範例中有較佳的求解品質；以基隆港過去船席指派紀錄與模式求解比較結果，本模式下兩個目標的隸屬函數值，均優於實務指派結果隸屬函數值；敏感度分析方面，經由多次的測試，發現船席服務的船舶數與服務時間、使用成本成反向變動，合乎一般的邏輯性，更可證明本模式正確性，具有應用價值，可以作為實務單位營運決策之參考。

Most of the import and export freights are transported by sea transportation in Taiwan.  Berth Allocation Problem (BAP) is essential problem for the operation of the port authority.  The time and location assignment of the berths to vessels is cricial to the efficiency of the port operation.  In the current practice in Taiwan, this decision is made by port authority and shipowner in the daily berth allocation meeting, which may not be the best policy to be adopted.  A series of academic researchs have devoted on the optimal BAP model for this problem.  However, there is no model address this problem from the point of views of both port authority and shipowners, which is the focus of the model proposed in this study.
In this research, we attempt to explore the application of the VRP (vehicle routing problem) concept on the BAP.  With the focus of the interests of the port authority and shipowner, a multi-objective programming model is formulated in this study.  There are two objectives in this model, i.e., the minimization of the total time in port of the shipowners, and the minimization of the working cost of the port authority.
With the NP-Hard nautrre of the porposed model, it is harder to get the optimal solution when the size of problem increasing.  Therefore, the artificial immune algorithm (IA) and Tabu Search algorithm (TA) are proposed as the main solution procedure of the study for its diversity search ability.  In order to reduce subject judgements in the multiple- objective programming, a series of fuzzy functions for the objectives are developed for this study.  Finally, to evaluate the propsed model and the algorithms developed in the study, a series of case studies include one data from Keelung harbor are tested in this study.  The results of these numerical tests indicate that the IA performs better in large size problem.  The solution of the proposed procedure provides better result than the conclusion of the daily berth meeting approach.

中文摘要
英文摘要
誌謝
目錄	I
圖目錄	IV
表目錄	V
第一章  序論	1
1.1  研究背景與動機	1
1.2  研究目的	2
1.3  研究範疇	2
1.4  研究方法與流程	3
第二章  問題描述與相關文獻回顧	5
2.1 船席指派	5
2.1.1 船舶進出港流程與船席指派作業	6
2.1.2 港埠作業相關成本	6
2.1.3 船席指派相關文獻	8
2.1.4  小結	14
2.2  機門指派	18
2.2.1  機門指派因素	18
2.2.2 機門指派相關文獻	19
2.2.3 小結	22
2.3模糊及多目標規劃	23
2.3.1 簡介	23
2.3.2 多目標規劃	23
2.3.3  模糊多目標規劃	26
2.4 車輛繞徑	28
2.4.1 船席指派與車輛繞徑	28
2.4.2 車輛繞徑問題	29
2.4.3 小結	30
2.5  類免疫演算法概述	30
2.5.1 生物免疫系統介紹	30
2.5.2 類免疫演算法	31
2.5.3 類免疫演算法相關研究	35
2.6 禁忌演算法概述	37
2.6.1 禁忌搜尋法簡介	37
2.6.2 禁忌演算法	37
2.6.3 禁忌演算法相關應用文獻	39
第三章  問題定義與模式構建	40
3.1 問題定義	40
3.1.1 問題特性與描述	40
3.1.2 問題定義	43
3.1.3 問題的轉換	43
3.2  前提與假設	45
3.3  問題架構	46
3.4  模式構建	47
3.5 模式修正與求解	49
3.6 小結	50
第四章  求解策略與方法	51
4.1 求解策略概念	51
4.2 問題輸入與輸出	53
4.3  資料結構	53
4.4 求解方法(一)類免疫演算法	56
4.4.1類免疫演算法應用步驟與流程	56
4.4.2 類免疫演算法於船席指派問題求解	58
4.5 求解方法(二)禁忌搜尋法	61
4.5.1 禁忌搜尋法應用步驟與流程：	61
4.5.2 禁忌搜尋法於船席指派問題求解	63
4.6 小結	66
第五章  範例測試與參數設計比較	67
5.1 範例測式	67
5.1.1 窮舉法	67
5.1.2 小型範例測試求解結果	69
5.1.3 小結	71
5.2 啟發式演算法	72
5.2.1 類免疫演算法	72
5.2.2 禁忌搜尋法	73
5.2.3 小結	74
5.3 參數設計比較	76
5.3.1 參數設計內容與比較方式	76
5.3.2 演算法較佳參數	78
5.3.3 小結	78
5.4 演算法求解品質比較	79
5.4.1 比較的方式	79
5.4.2 演算法比較的結果	80
5.4.3不同範例規模的比較	81
5.5 多目標船席指派求解流程	82
5.5.1 案例內容	82
5.5.2 求解過程	82
5.5.3 求解結果	85
5.6 實證研究與參數敏感度分析	87
5.6.1 資料收集與比較方式	87
5.6.2 實證比較的結果	88
5.6.3 參數敏感度分析	88
5.7 小結	90
第六章  結論與建議	91
6.1結論	91
6.2建議	93
參考文獻	94
附錄一、小型範例	98
附錄二、大型例題( 5 , 50 )相關資訊	102
附錄三、類免疫演算法求解求解在港時間參數實驗設計	105
附錄四、禁忌搜尋法求解求解在港時間參數實驗設計	109
附錄五、建議船席指派位置、順序與多目標隸屬函數值	111
附錄六、船舶進出港流程與基隆港船席指派作業	116
附錄七、生物免疫系統介紹	120

圖目錄
圖1-1 研究流程	4
圖2-1 連續型船席指派示意圖	10
圖2-2 船席指派後的示意圖	12
圖2-3 時空概念網路流動圖與指派結果展示圖	13
圖2-4 四種航站概念型式	19
圖2-5 單日機門指派作業網路圖	21
圖2-6 類免疫演算流程圖	33
圖2-7 兩兩互換之移步方式	37
圖3-1 單一船席指派示意圖	40
圖3-2 問題描述示意圖	42
圖3-3 節點作業時間說明圖	45
圖3-4 節線成本說明圖	46
圖4-1 求解策略示意圖(一)	52
圖4-2 求解策略示意圖(二)	52
圖4-3 船舶屬性結構體	54
圖4-4 船舶編號二維陣列結構體	54
圖4-5 本研究運用類免疫演算法流程圖	57
圖4-6 株落選擇說明圖	58
圗4-7 輕鏈重組示意圖	59
圗4-8 重鏈重組示意圖	59
圖4-9 船席指派問題求解流程圖	60
圖4-10 本研究應用禁忌搜尋法流程圖	62
圖4-11 最鄰近法流程圖	64
圖4-12 節點(船舶編號)交換示意圖	65
圖4-13 更新禁忌名單示意圖	66
圖5-1 船舶編號二維陣列結構體	67
圖5-2 不同規模範例下演算法求解品質比較	81
圖5-3 第一目標式隸屬函數圖	83
圖5-4 第二目標式隸屬函數圖	84
圖5-5 多目標運算迭代圖	85
圖5-6 實證流程圖	87

表目錄

表2-1 港埠成本分類表	7
表2-2 Lai and Shih (1992)四種指派策略	9
表2-3 Nishimura等待船席的時間	10
表2-4 指泊船舶順序與選定船席方案說明	11
表2-5 船席被同時佔據的長度	12
表2-6 船席指派問題相關文獻整理表	15
表2-7 船席指派與機門指派之比較	22
表2-8 多目標規劃應用文獻整理	24
表2-9 報酬表計算內容	26
表2-10 「船席指派問題」轉換為「車輛繞徑問題」之構想	28
表2-11 生物免疫系統與類免疫演算法特性對照表	32
表2-12 類免疫系統與生物免疫系統之對照表	35
表2-13 類免疫應用相關文獻	36
表3-1 「船席指派問題」轉換為「車輛繞徑問題」之構想	44
表5-1 範例一窮舉求解結果	69
表5-2 範例二窮舉求解結果	70
表5-3 範例三窮舉求解結果	70
表5-4 範例四窮舉求解結果	71
表5-5 類免疫演算法求解小型範例結果	72
表5-6 禁忌搜尋法求解小型範例結果	73
表5-7 禁忌搜尋法、類免疫演算法求解小型範例結果比較	75
表5-8 類免疫演算法參數設計相關內容	76
表5-9 禁忌搜尋法參數設計相關內容	76
表5-10 抗體數目實驗設計運算結果	77
表5-11 演算法較佳參數	78
表5-12 禁忌演算法與類免疫演算法求解結果比較	80
表5-13 不同規模範例下演算法求解品質比較	81
表5-14 第一目標式測試求解值	83
表5-15 第二目標式測試求解值	84
表5-16 不同船舶到達分配下多目標求解結果	86
表5-17 船席會議指派與模式指派結果比較表	88
表5-18 船席指派參數敏感度分析	89

1.	Alan S. Perelson and Gerard Weisbuch. Immunology forphysicists. Preprint for Review of Modern Physics, June1995.
2.	Ali Haghani and Min-Ching Chen(1998), “Optimizing Gate Assignments at Airport Terminals ”, Transportation Research-A, Vol.32, No.6, 1998, pp.437-453.
3.	Barbarosoglu, G. and Ozgur, D.(1999), “A tabu search algorithm for the vehicle routingproblem,” Computer & Operations Research, 26, pp.255-270.
4.	Bodin, L., B. Golden, A. Assad & M. Ball (1983), "Routing and Scheduling of Vehicle and Crew: The State of Art," Special Issue of Computers and Operations Research, Vol.10, No.2, pp.63-211
5.	Brandao, J., Mercer, A.(1997), “A tabu search algorithm for the multi-trip vehicle routingand scheduling problem,” European Journal of Operational Research , 100,pp.180-191.
6.	Brown, G. G., K. J. Cormican, S. Lawphongpanich and D. B. Widdis(1997), “Optimizing submarine berthing with a persistence incentive,” Naval Research Logistics, 44, 301-318.
7.	Dasgupta, D. “Artificial Immune Systems and Their Applications”, Springer-Verlag, 1999.
8.	Dasgupta, D., ”Artificial Neural Networks and Artificial Immune Systems：Similarities and Differences,” Proceeding of the IEEE Transaction on Systems, Man and Cybernetics, Vol. 1, pp.873-878, 1997.
9.	Dasgupta, D., and Attoh-Okine, N., ”Immunity-Based Systems：A Survey,”Proceeding of the IEEE Transaction on Systems, Man and Cybernetics, Vol. 1,pp.369-374, 1997.
10.	de Castro, L. N., and Timmis, J., ”Artificial Immune Systems：A New Computational Intelligence Approach,” Springer, 2002.
11.	de Castro, L. N., and von Zuben, F. J., ”Artificial Immune Systems：Part I-Basic Theory and Applications,” Technical Report TR-DCA 01/99, 1999.
12.	de Castro, L. N., and von Zuben, F. J., ”Artificial Immune Systems：Part II-A Survey of Applications,” Technical Report DCA-RT 02/00, 2000.
13.	de Castro, L. N., and von Zuben, F. J., ”The Clonal Selection Algorithm with Engineering Application,” Proceedings of the Genetic and Evolutionary Computation Conference, Vol. 1, pp.36-37, 2000.
14.	Dote, Y., ”Soft Computing (Immune Networks) in Artificial Intelligence,”Proceeding of the IEEE Transaction on Systems, Man and Cybernetics, Vol. 2,pp.1382-1387, 1998.
15.	Forrest, S., & Perelson, A., “Genetic algorithms and the immune system.”, In H. Schwefel, & R. Maenner (Eds.), Parallel Problem Solving from Nature, Berlin. Springer-Verlag (Lecture Notes in Computer Science).,1991
16.	Fukuda, T., Mori, K. & Tsukiama, M., Parallel search for multi-modal function optimization with diversity and learning of immune algorithm, Artificial Immune Systems and Their Application, Springer-Verlag, pp. 210-220,1999..
17.	Fukuda, T., Mori, M., Tsukiyama, M., “Immunnity-Based Management System for a Semiconductor Production Line”, Artificial Immune Systems and Their Applications, pp: 278~288, Springer-Verlag, 1999
18.	Gendreau, M., Hertz, A., Laporte, G.(1994), “A tabu search heuristic for the vehicle routing problem,” Management Science, Vol. 40,No. 10, pp.1276-1290.
19.	Geoffrey W. Hoffmann. A neural network model basedon the analogy with the immune system. Journal of Theoretical Biology, 122:33-67, 1986.
20.	Glenn W. Rowe. The Theoretical Models in Biology. OxfordUniversity Press, first edition, 1994.
21.	Glover, F. & M. Laguna (1997), Tabu Search, Kluwer Academic Publishers, Massachusetts.
22.	Glover, F. (1995), Tabu Search Fundamentals and Uses, Work Report, Graduate School ofBusiness, University of Colorado.
23.	Glover, F.(1986), “Future Paths for Integer Programming and Links to Artificial Intelligence,”Computers & Operations Research, Vol.13, pp.533-549.
24.	Han Shenglian, Ni Meng, and Ge Wancheng, Problems in GA and necessarity of importing immune function, Intelligent Control and Automation, 2000. Proceedings of the 3rd World Congress on, Volume 1, pp.542-544, 2000.
25.	Imai, A., E. Nishimura and S. Papadimitriou (2001), “The dynamic berth allocation problem for a container port,” Transportation Research Part B, 35, 401-417.
26.	Imai, A., E. Nishimura and S. Papadimitriou (2003), “Berth allocation with service priority,” Transportation Research Part B, 37, 437-457.
27.	Imai, A., K. I. Nagaiwa and C. W. Tat(1997), “Efficient planning of berth allocation for container terminals in Asia,” Journal of Advanced Transportation, 31, 75-94.
28.	Ishida, Y., Hirayama, H., Fujita, H., Ishiguro, A. and Mori, K. “Immunity-Based Systems—Intelligent Systems by Artificial Immune Systems”, Corona Pub. Co. Japan(in Japanese),1998.
29.	Ivan Roitt, Jonathan Brostoff, and David Male (1998) “Immunilogy,5/e”, Original English edition Copyright Mosby International Ltd.
30.	Jiao Licheng and Wang Lei, A novel genetic algorithm based on immunity, Systems, Man and Cybernetics, Part A, IEEE Transactions on, Volume 30 Issue 5, pp.552-561, Sept. 2000.
31.	John E. Hunt and Denise E. Cooke, Learning using an artificial immune system, Journal of Network and Computer Applications, pp. 189-212, 1996.
32.	Jones, D.F., Mirrazavi, S.K. and Tamiz, M.(2002), “Multi-objective meta-heuristics: An overview of the current state-of-the-art ”, European Journal of operational Research, Vol. 137, pp.1-9.
33.	Kim, K. H. and K. C. Moon(2003), “Berth scheduling by simulated annealing,” Transportation Research Part B, 37, 541-560.
34.	Lai, K. K. and K. Shih (1992), “A study of container berth allocation,” Journal of Advanced Transportation, 26, 45-60.
35.	Lei Wang and Licheng Jiao, A novel genetic algorithm based on immunity, Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. The 2000 IEEE International Symposium on, Volume 5, pp.385-388, 2000.
36.	Lim, A.(1998), “The berth planning problem,” Operations Research Letters, 22, 105-110.
37.	Mori, K., Tsukiyama, M., and Fukuda, T., ”Adaptive Scheduling System Inspired by Immune System,” Proceeding of the IEEE Transaction on Systems, Man and Cybernetics, Vol. 4, pp.3833-3837, 1998.
38.	Mori, M., Tsukiyama, M., Fukuda, T., “Immune Algorithm with searching Diversity and Its Application to Resource Allocation Problem”, Trans. IEE Japan, 113-C(10):872~878, 1993
39.	N. K. Jerne (1984) “Idiotypic networks and other preconceived ideas”, Immunological Rev., Vol.79, 5-24.
40.	Nishimura, E., A. Imai and S. Papadimitriou(2001), “Berth allocation planning in the public berth system by genetic algorithms,” European Journal of Operational Research, 131, 282-292.
41.	Nishimura, E., 1998. Public use e ects on the performance of container berth. Master Thesis, Kobe University of Mercantile Marine, Japan (in Japanese).
42.	Renaud, J., Laporte, G., F. Boctor, F.F.(1996), “A tabu search heuristic for the multi-depotvehicle routing problem,” Computer & Operations Research, Vol. 23, No. 3, pp.229-235.
43.	S. Forrest, A. S. Perelson, L. Allen, and R. Cherukuri. Self-Nonself Discrimination in a Computer. In Proceedingsof IEEE Symposium on Research in Security and Privacy, pages 202-212, Oakland, CA, 16-18 May 1994.
44.	S.Bandara and S.C Wirasinghe, “Airport Gate Position Estimation Under Uncertainty”, TRR 1199, 1988, pp.41-48.
45.	S.C Wirasinghe and S.Bandara, “Airport Gate Position Estimation For Minimum Total Costs-Approximate Closed Form Solution”, Transportation Research-B, Vol.24B, No.4, 1990, pp.287-297.
46.	Steven A. Frank. The Design of Natural and ArtificialAdaptive Systems. Academic Press, New York, M. R.Rose and G. V. Lauder edition, 1996.
47.	Gioia Tauro ,”Modelli ed Algoritmi per un Terminale Marittimo Container:” 
48.	卓裕仁，以巨集啟發式方法求解多車種與週期性車輛路線問題之研究，國立交通大學運輸工程與管理系碩士論文，2001
49.	廖子銘，類免疫演算法於多目標最佳化問題之研究與應用，大同大學機械工程研究所碩士論文，2001
50.	張世峰，即時訂貨資訊下物流配送作業規劃之研究，淡江大學運輸科學研究所碩士論文，2002
51.	張企宏 ，貨櫃碼頭分派問題之研究，元智大學工業工程與管理學系碩士論文，2004
52.	張家銘，機門指派最佳化之研究，國立中央大學土木工程研究所碩士論文，1995
53.	張束珍，機場機門指派模擬模式之研究 ，國立交通大學交通運輸研究所碩士論文，1993
54.	張立偉，災後工程緊急搶修作業排程之研究，淡江大學運輸科學研究所碩士論文，2001
55.	徐玉琦，基隆港貨櫃裝卸作業費率之研究-作業基礎成本制度(ABC)之應用，國立交通大學交通運輸研究所碩士論文，1998
56.	朱橋榮，最小化機場機門數量之研究，國立中央大學土木工程研究所碩士論文，2001
57.	李育達 ，基隆港貨櫃船席調配電腦化之分析，國立海洋大學航運技術研究所碩士論文，1998
58.	杜世文，多目標與模糊時窗貨物配送啟發式解法之研究，國立交通大學交通運輸工程研究所碩士論文，1991
59.	林明俊，隨機環境下多車種車派車問題之研究，中原大學工業工程研究所碩士論文，1998
60.	林秀璘，應用模糊多目標規劃法於公車營運計畫之研究，國立成功大學交通管理(科學)學研究所碩士論文，1992
61.	楊博文，配合大眾捷運系統之接運公車營運計劃整合之研究--分析數學法與多目標規劃法之應用，國立成功大學交通管理(科學)研究所碩士論文，1990
62.	沈進成，公車系統營運計劃最佳化模式之研究，國立成功大學交通管理(科學)研究所碩士論文，1988
63.	洪子盛，以模糊多目標規劃法求解消防站配置問題之最佳化，國立成功大學工業管理科學系博士論文，2003
64.	游守田，停機坪即時性調度之研究，國立成功大學交通管理科學研究所碩士論文，2004
65.	遊建堂，應用塔布搜尋法於多目標最佳化問題，淡江大學電機工程學系碩士在職專班碩士論文，2004
66.	游文松，公路客運人員與車輛排班之研究，中華大學科技管理研究所碩士論文，2004
67.	王丘明，港埠管理，2003，華泰
68.	王文貞，圖書配送車輛排程問題之研究，成功大學交通管理研究所碩士論文，1997
69.	羅意茹，應用免疫演算法於可控退化率存貨問題之研究，嘉義大學運輸與物流工程研究所碩士論文，2004
70.	許志義，多目標決策增訂版，2003
71.	謝東緯，大專學生參與專題研究計畫成果報告之「船席調派問題之研究-以基隆港為例」，國立成功大學交通管理學系，1997
72.	謝致遠，「靜態機門指派與即時營運擾動間相關性之研究，國立中央大學土木工程學系碩士論文，1998
73.	鄧宏安，整合CFDRC及類免疫演算法於散熱片之最佳化設計，大同大學機械工程研究所碩士論文，2003
74.	陳勝男，禁忌搜尋法應用於車輛路線問題之研究，大葉大學工業工程研究所碩士論文，1996
75.	陳春益、李宇欣、盧華安，民國八十六年，「時空網路應用於機門指派問題之研究」，運輸學刊，第10卷，第3期，頁1-20
76.	陳朝文，基隆港貨櫃船舶優先靠泊制度之研究，國立海洋大學航運管理研究所碩士論文，2002
77.	霍俊明，機門指派最佳化模式暨變數產生法之研究，國立中央大學土木工程學系碩士論文，1983
78.	黃明居，知識庫系統應用於基隆港貨櫃船席調配作業之研究，國立海洋大學航運技術研究所碩士論文，1990
79.	黃木才，貨櫃運輸公司車輛排程問題之研究-模糊多目標遺傳演算法之應用，國立交通大學交通運輸研究所碩士論文，1995
80.	黃金智，隨機型車輛途程問題解法之研究，大葉大學工業工程研究所碩士論文，1999