貨櫃陸地轉運問題之演算法發展

A Heuristic Algorithm for In-land Container Trnasshipment Problem

張時豪(Shih-Hao Chang)

指導教授 ： 申生元

元智大學/資訊學院/資訊管理學系/碩士(2005年)

摘要

無資料

關鍵字

貨櫃運輸 ； 車輛途程問題 ； 啟發式演算法

並列摘要

With the growth of the global marine, the volume of containers are growing up constantly every year. However, the competition of freight transportation market also becomes increasingly more fierce than ever before. In order to earn more profit, every container transportation company does need to work hard to save cost and create more sources of revenue. Traditionally, most freight transportation companies do their vehicle scheduling tasks manually that rely on the intuition and experience of employees. Because the human brain capability in delaing with complex situations has its limit, it is unable to easily consider too many factors at the same time, so that it can’t utilize vehecles with the best way. Therefore, for freight transportation companies, it is helpful to use the powerful computation capability of computer to assist people in assigning vehicles.

In this research, we first transform the container transshipment problem into a mix interger mathematical model. Since it is an NP-hard problem, the corresponding computational time tends to grow exponentially as the problem size increases. Therefore, we develop a heuristic to meet the real world needs. We hope that we can get acceptable solutions in a resonable time. After testing the heuristic through several examples, we find the solution time of the heuristic is quiet efficient, and the quality of the answer is pretty good in contrast to the optimal solutions for small size problems. It shows that the heuristic is effective in solving this problem.

並列關鍵字

Container transshipment ； Vehicle routing ； Heuristic

參考文獻

[1] Algorithms for the Vehicle Routing Problem," Annals of Operations Research, Vol. 41, pp.421-451.

[2] Balas E., “Intersection cuts —A new type of cutting plane for integerprogramming,” Operations Research, 19,19-39, 1971.

[3] Bard, J. F., L. Huang, M. Dror, and P. Jaillet, “A branch and cutalgorithm for the VRP with satellite facilities”, IIE Transaction, 30,pp.821- 834, 1998

[4] Bellman,R., “Dynamic Programming Treatment of the Traveling SalesmanProblem”，Vol.119，pp61-63，1962

[6] Brandao, J. and Mercer, A., "A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem," European Journal of Operational Research, Vol.100, No.1, pp.180-191, 1997.