以啟發式演算法求解多派車中心之CY貨櫃運輸問題

Heuristic Algorithms for Multi-Depot Container Yard Transportation Problem

王常殷

指導教授 ： 林則孟

國立清華大學/工學院/工業工程與工程管理學系/碩士(2010年)

摘要

在實務上，CY貨櫃運輸是利用貨櫃車以整櫃式的方式，把貨櫃往來運送於貨主倉庫與貨櫃集散站之間。近年由於客製化服務興起，加上台北港建設完成，降低北部貨櫃從高雄港進出口的需求，貨櫃運輸的模式在島內逐漸由長程的南北轉運，轉變成短程的CY貨櫃運輸。然而，CY貨櫃運輸的貨櫃車在行駛路徑規劃上複雜，還必須因應不同的需求，提供客製化的服務。現行的貨櫃車派遣是以人力為主，但隨著CY貨櫃運輸的需求上升，再加上其運輸路徑的複雜，已成為一個棘手的問題。
本研究把CY貨櫃運輸模式建構為多場站且考量時窗限制的多旅行銷售員問題(Multi-Depot m-TSPTW)。在過去文獻中，主要是以貨櫃車總空車行駛時間最小化為目標進行求解，本研究考量了實務上的狀況，加入了最小化駕駛工作差異的目標，欲減少駕駛之間的工作負荷差異。為求解此雙目標問題，本研究先使用文獻上常用的禁忌演算法與基因演算法，求解以總空車行駛時間最小化為目標的CY貨櫃運輸問題，以期能從這兩種啟發式演算法當中，選出適合實務的貨櫃車路徑規劃演算法。根據上述兩種演算法的比較結果，本研究採用以基因演算法為架構的NSGAII發展多目標啟發式演算法，求解最小化總空車行駛時間與最小化駕駛工作差異的雙目標問題。最後再利用實務上的資料，分析此演算法在不同資料量下的求解情形。
分析結果發現，本研究發展的多目標啟發式演算法在滿足時窗限制、駕駛工時限制……等條件下，隨著資料數量的增加，演算法的求解情形依然穩定，足證此演算法能夠求解雙目標的CY貨櫃運輸問題，並適用於各種不同規模的問題。

關鍵字

多目標 ； 基因演算法 ； 禁忌演算法 ； 車輛途程問題

並列摘要

無資料

並列關鍵字

NSGA II

參考文獻

4. 陳百傑，“以啟發式演算法求解時窗限制車輛途程問題”，中原大學工業工程研究所，碩士論文，2002。

5. 張時豪，“貨櫃陸地轉運問題之演算法發展”，元智大學資訊管理研究所，碩士論文，2005。

7. Chung, K. H., Ko, C. S., Shin, J. Y., Hwang, H. and Kim, K. H., “ Development of mathematical models for the container road transportation in Korean trucking industries”, Computers & Industrial Engineering, Vol. 53., pp.252-262., 2007.

8. Deb, K., “Multi-Objective Optimization using Evolutionary Algorithms”, Wiley-Interscience, 2001.

11. Gen, M. and Cheng, R., “Genetic Algorithms & Engineering Design”, Wiley-Interscience, 1997.