物流配送實務之路徑規劃分析- 採用基因遺傳演算法

Using Genetic Algorithm for Better Route Arrangement

陳昱錕(Yu-Kun Chen)

指導教授 ： 楊承亮

大同大學/經營設計學院/資訊經營學系所/碩士(2006年)

摘要

近年來Internet的盛行，帶動了商業電子化的潮流，許多經營傳統店面的廠商也開始將商品擺設在網路商店上供消費者選購，於是將貨物由銷售者手中直接配送到府的服務漸漸興起，到府專送的物流複雜度以及數量皆不斷提高。
放眼國內外的物流運送公司， 對於下游司機的實際運送路徑規劃缺乏全盤性的考量，仍舊完全仰賴司機的經驗來決定何為較有效率的運送路徑。而在錯綜複雜的運送路徑以及與日俱增的送貨需求之下，此作法已不合時宜。基於國內外運送路徑的研究大部分偏重理論層面，有效的實務規劃較為缺乏，故將進行此項研究。
本研究將採用基因遺傳演算法(Genetic Algorithm ，簡稱GA) ，並結合地理資訊系統軟體(如Mobuy PowerMap)，計算相關送貨路徑之距離進行路徑安排規劃。由於過往關於車輛路徑規劃分析方法所建立的距離考量，幾乎都僅為地圖上的直線距離，本研究將實際導入地理資訊的協助，建立切合實際的路徑距離矩陣，研究結果的實用性將大幅提高。本研究提出運送目標之規劃策略，將運送區域進行分群，因此路徑分析結果可以重複使用於該區域，十分具有經濟效益。本研究同時進行針對GA的參數設定環境進行探討，驗證了一套有效的先行實驗分析方法，同時探討不同的參數設定概念之下，對於分析過程的影響與分析結果的優劣。研究結果指出，未來進行GA分析路徑規劃時，可採用本先行實驗方法挑選出較有效率的參數組合，讓分析的效率更為良好。本研究分析結果的新送貨路徑長度較舊有的路徑最多可節省約17%的距離，運送效率大幅提升。

關鍵字

運輸路線問題 ； 銷售員旅行問題 ； 基因演算法

並列摘要

The problem of a real case of route arrangement caused by the needs of delivering goods directly to home is discussed in this paper. Normally the route is arranged by a driver according to his experience. However, such arrangement may not be appropriate. As a matter of fact, an accurate distance matrix is established by performing geographical information software, PowerMap. An efficient delivering spot planning strategy is proposed in this paper to make the analysis more practical and reasonable. The problem is solved by adopting a Genetic Algorithm (GA), which is carried out by using commercial software, Evolver. We also discuss the parameter setting effect on GA simulation performance. We adopt both the classic parameter settings suggested by past articles and the software default setting concept, and also observe the difference between two parameter setting concepts. The result shows that the best route given by GA is much better than that arranged from the driver’s experience, and can shorten the original distance for about 17% every day.

並列關鍵字

Traveling Salesman Problem ； Genetic Algorighms ； Vehicle Routing Problem

參考文獻

[11] 謝欣宏, 民國九十年, ”台鐵司機員排班與輪班問題之研究-以基因演算法求解 “,國立成功大學交通管理學系碩士論文。

[13] Belgin Turkay and Taylan Artac , 2005, "Optimal Distribution Network Design Using Genetic Algorithms" , Electric Power Components and Systems, 33:513–524.

[14] Bo K. Wong and T. A. Bodnovich, May 1998 , “A Bibliography of Genetic Algorithm Business Application Research: 1988 – June 1996”, Expert Systems, vol. 15, no. 2, pp. 185-195.

[15] Bodin, D Lawrence and L Bruce . Golden, 1981, “Classification in Vehicle Routing and Scheduling”, Networks, Vol. 11, p. 97-108.

[17] Davis, Lawrence, 1991, “Handbook of Genetic Algorithms”, copyright by Van Nostrand Reinhold , ISBN:0-442-00173-8