本研究乃針對不定期船運(Tramp Shipping)之船舶排程問題(Ship Routing problems)加以探討，並以台灣一家不定期船運航商(以下簡稱航商A)為實例研究對象。該航商以自有船舶及論時傭船所取得的船舶經營不定期船運業務。不定期船運航商經常需要面對與船舶調度相關的營運問題，這些問題若以短、中、長期來區分，短期的營運船舶數量通常維持不變，主要的營運問題為貨運訂單的處理及船舶排程，中期主要是在處理船舶短期租賃問題，長期則以船隊規模(船舶長期租賃契約的規劃)為主。本研究先針對航商A 之短期營運問題加以探討，並解決航商A之貨運訂單與船舶排程問題。
本研究利用多元商品時空網路(multicommodity time-space network)構建數學模式，此模式可以同時處理航商A之船舶調度(ship allocation)、貨物指派(cargos assignment)、與航線安排(shipping routing)等問題，亦可作為篩選貨運訂單之工具。因所構建的數學模式亦可視為線性混合整數規劃問題，本研究逕利用套裝軟體CPLEX之分枝界限法加以求解。由實例研究結果顯示，本研究所構建之模式不僅可以合理的解釋問題並求得最佳解，針對小規模問題其求解效率亦在可接受範圍，足以協助航商A擬定短期營運策略。

惟若問題的規模增加大時(例如貨運訂單數增加到40筆以上)，本研究模式的求解效率較差，就實用性而言，本研究建議後續研究可以另外設計啟發式演算法，啟發式演算法的求解結果雖然大部分無法得知真正的最佳解，但是快速的求解效率將可以協助航商A更有效率的制定短期經營策略。
本研究以實例研究的方式探討不定期船運的短期營運問題，提出一有效求解船舶調度、貨物指派、航線安排與篩選貨運訂單之數學模式。惟模式並未考慮航商A之中、長期船舶調度問題，以及貨物需求與成本函數關係，建議後續研究可以詳加探討。

This study focuses on tramp shipping ship routing problems to be discussed, and a tramp shipping carrier of Taiwan (hereinafter referred to as carriers A) as an example to study. Carriers A to own ships and the time charterer ships to made for tramp shipping services. Irregular tramp ship carriers often have to face related to the operation of the ship allocation problems if the short, medium and long term to distinguish, the number of short-term operation of ships usually remain unchanged, the main operational issues for freight orders and ship routing problem, mainly in the mid-ship short-term leasing deal, long-term fleet scale (ships of planning long-term lease contracts) based. This research aims to be Carriers A of the operational issues and resolve the freight orders and ship routing problems.
In this study, multicommodity time-space network build mathematical models, this model can handle Carriers A of the ship allocation, the cargos assignment, and shipping routing and so on, can also order the freight as a screening tool. Because of the mathematical model can be constructed as a linear mixed integer programming problem, this study tracks the use of the software package CPLEX branch and bound method to solve. Results from the case studies, this study will not only reasonable mode of interpretation and find the optimal solution, Its solution for the efficiency of small-scale problems are within the acceptable range, enough to help Carriers A develop short-term business strategy.
However, if a large increase in the scale of the problem (such as cargos rose more than 40 pen), that the model's computational efficiency is poor, for practical purposes, the study suggests that future research could design another heuristic algorithms. Test results of heuristic algorithms, though not the true optimal solution. However, the efficiency will be solved quickly Carriers A can help to develop more efficient short-term business strategy.
The case study approach to explore the short-term operation problems of the tramp shipping, to propose an effective solving ship allocation and cargos assignment, shipping routing and the freight orders of the mathematical model. However, models did not consider the medium and long -term ship allocation problem, and freight demand and cost function, suggested that future studies can explore in detail.

參考文獻
1. Baldacci, R., Maniezzo, V. and Mingozzi, A., “An Exact Method for the Car Pooling Problem Based on Lagrangean Column Generation”, Operations Research, Vol. 52, No. 3, pp. 422-439, 2004.
2. Cho, S.C. and Perakis, A.N., “Optimal Liner Fleet Routing Strategies”, Maritime Policy and Management, Vol. 23, No. 3, pp. 249-259, 1996.
3. Cho, S.C. and Perakis, A.N., “An Improved Formulation for Bulk Cargo Ship Scheduling with a Single Loading Port”, Maritime Policy and Management, Vol. 28, No. 4, pp. 339-345, 2001.
4. Cordeau, J.F., Desaulniers, G., Desrosiers J., Solomon M.M., Soumis, F., “VRP with Time Windows”, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, pp. 157-193, 2002.
5. Chen, C.-Y. and Liu, H.-Y., “A Multicommodity Network Design Model for Optimal Routing of Hand-size Bulk Ships”, The International Association of Maritime Economists Annual Conference, Izmir, Turkey, 2004.
6. Christiansen, M., Fagerholt, K. and Ronen, D., “Ship Routing and Scheduling: Status and Perspectives”, Transportation Science, Vol. 38, No. 1, pp. 1-18, 2004.
7. Cunha, C. B. and Silva, M. R., ”A Genetic Algorithm for the Problem of Configuring a Hub-and-Spoke Network for a LTL Trucking Company in Brazil”, European Journal of Operational Research, Vol. 179, pp. 747-758, 2007.
8. Desaulniers G., Desrosiers J., Erdnabb A., Solomon, M.M., Soumis, F., “VRP with Pickup and Delivery”, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, pp. 225-242, 2002.
9. Fagerholt, K., “A Simulation Study on the Design of Flexible Cargo Holds in Small-sized Bulk Ships”, Maritime Policy and Management, Vol. 26, No. 2, pp. 105-109, 1999.
10. Fagerholt, K. and Christiansen, M., “A Combined Ship Scheduling and Allocation Problem”, Journal of the Operational Research Society, Vol. 51, pp. 834-842, 2000a.
11. Fagerholt, K. and Christiansen, M., ”A Traveling Salesman Problem with Allocation, Time Windows and Precedence Constraints-an Application to Ship Scheduling”, International Transactions in Operational Research, Vol. 7, pp. 231-244, 2000b.
12. Fagerholt, K., “Ship Scheduling with Soft Time Windows: An Optimization Based Approach”, European Journal of Operational Research, Vol. 131, pp. 559-571, 2001.
13. Gen, M. and Cheng, R., Genetic algorithms and engineering optimization, John Wiley & Sons, 2000.
14. Jula, H., Dessouky, M., Ioannou, P. and Chassiakos, A., “Container Movement by Trucks in Metropolitan Networks : Modeling and Optimization”, Transportation Research Part E, Vol. 41, pp. 235-259, 2005.
15. Kendall, L.C. and Buckley, J.J., The Business of Shipping (7th edition), Cornell Maritime Press, 2001.
16. Laporte, G., “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms”, European Journal of Operational Research, Vol. 59, pp. 345-358, 1992.
17. Lin, C.-C., “The Freight Routing Problem of Time Definite Freight Delivery Common Carriers”, Transportation Research B, Vol. 35, No. 6, pp. 525-547, 2001.
18. Liu, H.-Y. and Chen, C.-Y., “Optimal Routing of Voyage-charter, Handy-size Bulk Ships”, The International Scientific Annual Conference: Operations Research, Bremen, Germany, 2005.
19. Pankratz, G., ”A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows”, OR Spectrum, Vol. 27, pp. 21-41, 2005.
20. Ronen, D., “Cargo Ship Routing and Scheduling: Survey of Models and Problems”, European Journal of Operational Research, Vol. 12, pp. 119-126, 1983.
21. Ronen, D., “Short-term Scheduling of Vessels for Shipping Bulk or Semi-bulk Commodities Originating in a Single Area”, Operations Research, Vol. 34, No. 1, pp. 64-173, 1986.
22. Snezana, M.M., Krishnamurti, R. and Laporte, G., “Double-horizon based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows”, Transportation Research Part B, Vol. 38, pp. 669-685, 2004.
23. Schönberger, J., “Operational Freight Carrier Planning-Investigations on Basic Concepts, Optimization Models and Advanced Memetic Algorithms”, Springer, 2005.
24. Shintani, K., Imai, A.,”Nishimura, E. and Papadimitriou, S., “The Container Shipping Network Design Problem with Empty Container Repositioning”, Transportation Research Part E, Vol. 43, pp. 39-59, 2007.
25. Toth, P. and Vigo, D., “ An Overview of Vehicle Routing Problems”, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, pp. 1-26, 2002.
26. 林光，海運學，華泰書局，民國88年。
27. 韓復華、卓裕仁，「網路節點服務TSP與VRP問題回顧」，第四屆中華民國運輸網路研討會，頁203~223，民國88年。