基因演算法於多目標車輛途程問題之應用

Application of Genetic Algorithm to Multi-Objective Vehicle Routing Problem

林正中(Jeng-Jong Lin)

《智慧科技與應用統計學報》 4卷2期 (2006/12) Pp. 19-48

https://doi.org/10.29807/JTITAS.200612.0002

摘要

本研究主要是利用車隊負載集中度(loading-focus degree)α與車輛空間利用率(space utility)β二參數來評價車隊承載運送貨物的效能，以期車隊能發揮最大的承載效能，使用最少車輛數同時兼顧行駛最短的路線情形下完成配送服務。本文利用基因演算法協助搜尋使α及β值最大化而總路徑最小化的最佳配送策略，以解決物流多目標車輛途程的問題，即由單一物流中心以特定裝載能力及數量的車輛負責進行配送服務，並且遵守每一客戶只能由一輛車進行配送服務且僅接受一次服務的原則下完成配送任務，以滿足各客戶對貨品之不同需求量的要求。實驗結果顯示：本研究藉基因演算法解決此物流基本派車途程的多目標問題，效果相當良好，以位元字串直觀編碼方式所組成之染色體可正確於若干代演化後獲得最佳解，並可依實際上對「車隊的整體空間運用」和「配送路徑」需求比重的不同，彈性調整w1、w2、ρ1及ρ2等係數值之大小而尋得符合實務需求的多目標最佳整合配送策略供物流派車之參考，同時也可計算各車所剩餘的可用載重與空間，以供派車人員彈性調整派車策略。藉由提供搜尋結果供物流業者於每日規劃派車策略時作參考，可有效協助業者提升物流配送之競爭力。

關鍵字

車輛途程 ； 派車策略 ； 基因演算法 ； 負載集中度 ； 空間利用率

並列摘要

This paper mainly focuses on promoting loading performance of vehicle through minimizing fleet size in terms of loading-focus degree α and space utility β under minimizing total travel distance at the same time. A Genetic algorithm (GA) is applied to acquire both the maximum of α and β and the minimum of the transit distance to have the multi-objective decision for transportation problem solved. There are constrains for a basic transportation problem to follow. Each customer can be served by one vehicle and once for all. All the demanded number of commodities must be completely supplied. The results show the performance of using genetic algorithm to solve multi-objective vehicle routing problem is fairly promising. A dispatching strategy of the minimum number of vehicle used and the shortest path for transportation can be acquired using GA with a bit-string coding. An integrated multi-object dispatching strategy can be achieved by flexibly adjusting w1, w2, ρ 1 and ρ 2 based on the practical demands of logistics. In addition, the system can simultaneously calculate the residual loading capacity of weight and volume for each vehicle to provide a dispatcher with more flexible dispatching way. Through the supported vehicle dispatching strategy, the competency of logistics can thus be enhanced.

並列關鍵字

Vehicle routing problem ； Dispatching strategy ； Genetic algorithm ； Loading-focus degree ； Space utility