考量成本與服務穩定以基因演算法求解多車種之車輛途程問題

Applying the Genetic Algorithm to Solving the Heterogeneous Vehicle Routing Problem Considering Service Costs and Stability

蕭閔哲(Min-Che Hsiao)

指導教授 ： 顏憶茹

國立臺中科技大學/資訊與流通學院/流通管理系碩士班/碩士(2015年)

https://doi.org/10.6826/NUTC.2015.00027

摘要

本研究以基因演算法來探討多車種之車輛途程問題，主要目的是為了建構一套求解軟體以供實務參考，當中除了考量服務成本外，另外提出了服務穩定的概念，將經驗法則融入演算過程以避免配送路徑發生大幅度改變的情況。
　　本研究發展出模糊多目標規劃模型，結合基因演算法，運用隸屬函數進行求解。演算的過程中，延用Chang and Yeh（2007）提出之單性生殖基因演算法，避免染色體進行交配時發生基因重複之情形。而在產生初始族群時，隨機產生初始解會導致求解結果不佳，主要是因為結果受限於服務穩定的目標，因此本研究增加了一個初始穩定率的功能，藉由經驗法則的解來產生新的初始族群。除此之外，在適應函數中加入了模糊多目標來計算兩個不同單位的目標式，並將求解結果轉換成隸屬函數，以判別染色體的優劣。
　　研究採用Golden et al.（1984）所建構之HVRP問題中的8組題型進行測試，透過不同題型來驗證模式的應用範圍。研究結果顯示，在服務成本與服務穩定上皆有良好的表現，另外，藉由初始穩定率的調整能夠影響結果要趨向服務成本或服務穩定度，以供使用者參考。

關鍵字

服務穩定 ； 多車種之車輛途程問題 ； 單性生殖基因演算法 ； 模糊多目標

並列摘要

This study uses the genetic algorithm to explore the heterogeneous vehicle routing problem (HVRP). The main purpose is to construct a problem solving software for the reference of related industries. In addition to service costs, this study also contains the concept of service stability. Furthermore, this study blends rule of thumb into the calculation to avoid dramatic change in the path.
　This study develops a fuzzy multi-objective linear programming model, combining genetic algorithms and membership functions. To avoid gene repeat during chromosome mating, the structure of our genetic algorithm is based on the parthenogenesis genetic algorithm proposed by Chang and Yeh (2007). In view of the fact that using a random approach to generating an initial solution leads to poor results, due to the objective of service stability, this study adds a function of initial stable rate and uses the rule of thumb to generate new initial population. In addition, fuzzy multi-objective is added to the fitness function to calculate the objective functions of two different units. The solutions are then converted into the membership functions to determine the quality of chromosomes.
　This study further tests eight instances of HVRP benchmark instances constructed by Golden et al. (1984) to verify the model’s range of applications. The results show that the model has good performance with regard to service costs and stability. In addition, adjusting the initial stable rate can affect the results tending to the objective of service costs or service stability. The findings provide practical reference to the related industries.

並列關鍵字

Service Stability ； HVRP ； Parthenogenesis Genetic Algorithm ； Fuzzy Multi-objective

參考文獻

胡智維（民102）。粒子群演算法應用於多車種固定車隊之車輛途程問題。元智大學工業工程與管理學系碩士論文，桃園縣。

蔣寬和、鐘秀菊（民96）。模糊多目標線性規劃在地區農業生產決策之應用。修平學報。

簡銓蔚（民102）。粒子群演算法應用於具容量限制的開放式車輛途程問題。元智大學工業工程與管理研究所碩士論文，桃園縣。

Baker, B. M., & Ayechew, M. A. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787-800.

Baldacci, R., Battarra, M., & Vigo, D., (2008), Routing a Heterogeneous Fleet of Vehicles, Operations Research/Computer Science Interfaces, 43, 3-27.