324-单一物流中心货物配送模式之研究

1報告人：陳致元指導教授：朱子豪老師評閱老師：孫志鴻老師評閱同學：鐘新南同學單一物流中心貨物配送模式之研究21.研究動機配送問題與物流業VRP（車輛途程問題）之發展物流配送在GIS實屬於空間分析的問題，以往研究則較少考量空間分佈差異對配送產生的影響。32.研究目的將空間分析中群聚分析方法（ClusteringAnalysis）引入車輛途程問題(VRP)模式當中，已改善以往VRP演算法未加入空間考量的問題。分析不同的空間分佈型態（Pattern），對不同VRP求解模式的影響。4研究流程研究流程修正與回饋研究問題界定結論與建議測試結果與比較例題測試發展研究架構演算功能文獻回顧研究動機和目的53.文獻回顧陳文瑞（1990）曾提到：VRP是車輛在依序的服務地點做收貨(或，和)送貨的服務，且必須依照指示依序通過這些服務地點，開始和結束在同一個出發點(depotordomicile)。63.1VRP問題探討VRP問題的分類–單一場站、多場站–本研究屬於單一場站VRP規劃目標函式–Minimizedistance距離最小化–Minimizetraveltime運送時程最小化–Minimizeno.ofvehicles車輛數目最小化–Minimizeoftotalcost總成本最小化73.2VRP問題求解模式分析(1)VRP問題求解模式的類型與代表(1)先分群再排路線(ClusterFirst-Routesecond)–掃瞄法(GillettandMiller,1974)-採用及座標角度掃瞄分群(2)先排路線再分群(RouteFirst-clusterSecond)–(BodinandBerman,1979)-分群結果受先前排列之路進影響(3)節省法或插入法(SavingorInsertion)–節省法(ClarkeandWright,1964)-叫無彈性，無法視群聚狀況調整(4)改善與交換(Improvementorexchange)–K-optimal法(LinandKernighan,1965)(5)數學規劃法(MathematicalProgrammingApproaches)(6)最佳解法(ExactProcedures)(7)人機互動法(InteractiveOptimization)83.2VRP問題求解模式分析(2)由於VRP屬於非完全多項式(NP-Complete)問題，(5)數學規劃法、(6)最佳解法兩種方式求解複雜度隨問題大小呈指數成長，近年來學者紛紛致力於啟發式解法的開發。目前學界研究VRP問題通常採用二階段法，–第一階段初始解的產生，例如(1)先分群再排路線、(2)先排路線再分群、(3)節省法或插入法–第二階段則為解的改善，例如(4)改善與交換93.3啟發式解法基本概念啟發式解法基本步驟（徐吉田，1993）–1.指定K車輛（即路線）–2.集結各需求點成一路線(啟始解)–3.路線改善1.重新排列路線中各需求點，以得較好的路線。2.將某路線的點移到另一路線本研究採用先分群後排路線的方法，但考慮以往相關研究較少將空間因子納入考量，故本研究引入空間分析中集群分析（ClusteringAnalysis）的相關技術，來作為VRP的分群求解（啟始解）模式。103.4空間分析關於地表空間的特徵，一般來說屬於空間分析的範疇，而對於地表空間型態（pattern）的描述，主要可分為幾種指標，以點資料來說，有下列幾種：–頻率(frequency)–密度(density)–幾何中心(geometriccenter)–離散(dispersion)–排列(arrangement)–Clustered(密集型),Scattered(擴散型),Random(隨機型)113.4.1群聚分析而若要將空間中不同的點資料予以歸納分類，則必須要使用空間分析中的群聚分析技術（ClusterAnalysis）。Cluster分析方法主要可以用兩種方式來討論，第一種方式可以從分裂或是聚集來描述，分裂法強調群體的差異性，聚集法強調區域的相似性，第二種方式是以階層和非階層來描述123.5空間分佈型態Y806040200X706050403020100121110987654321222120191817161413121110987654321X706050403020100Y706050403020100CLUSTER543210群聚型隨機型133.4.1群聚分析1.UPGMA(unweighedpair-groupmethodusingarithmeticaverages)利用接近值算數平均數2.WPGMA(weighedpair-groupmethodusingarithmeticaverages)加入了權重值的計算3.SLINK(singlelinkageclusteringmethod)利用最小接近值4.Clink(completelinkageclusteringmethod)利用最大接近值5.Ward’sminimumvariancemethodE=(x1-Cmean1)^2+(y1-Cmean1)^2+……..取MIN6.K-meansalgorithms(Macqueen,1967)在一群需求(demand)點中找出k個供應(supply)中心的位置﹐使得需求點至供應中心的總成本最低(鄒明城，2000)7.K-medoidalgorithmsg(Vinod,1969)對於K-means法容易掉入去最佳解的問題加以修正。8.CLARANS(clusteringlargeapplicationsbaseonrandomizesearch)(NgandHan,1994)9.DBSCAN(density-basedclusteringalgorithm)(Easter,1996)以空間分佈的密度為考量發展求解模10.GDBSCAN(generalizeddensity-basedspatialclusteringofapplicationwithnoise)(SANDERet.al,1998)14研究架構VRP空間群聚求解模組配送以及物流之空間資料庫車輛及路線的指派物流業特性分析VRP求解模式分析地理空間分析GIS系統比較其他求解策略不同空間Pattern分析歸納結果154.研究方法將空間分析中群聚分析模組應用於VRP初始解的求得，以離散/群聚之空間分析為基礎，並以clustering分析為核心改進方法，來改進及評量配貨地一解求法。引入空間量度參數，以做為空間度量，來評定不同演算法在不同空間度量上的優劣。164.1研究假設(1)單一場站多部車輛–道路的特性»初期考慮對稱性路網，日後研究在考量實際路網–配送點特性限制»由一部車服務»需求皆不超過一部車容量–車輛的限制型態»容量的限制單一車種，多部車輛»行車距離的限制174.2研究假設(2)–時窗(TimeWindow)的限制»不考慮時窗限制–客戶區位特性»固定已知的需求–產品本身特性»以數量考慮，視為一種商品184.3群聚分析本研究考慮工具的取得以及符合研究假設需求性，初步採用SPSS統計軟體，利用其內建之Analyze模組中的Classify的功能，採用k-meansCluster以及HierarchicalCluster演算法來做分群，另外區域配送之TSP演算法則採用最遠內插法，利用VB撰寫求解程式配合VRP標準例題做測試。195初步成果No.ProblemNameNodesVehicleCapacitySourceCostandFleetData#1E-n51-k550160Christofieds&Eilon(1969)採用Christofieds&Eilon(1969)所提出的測試例題進行測試20k-meansCluster結果21HierarchicalCluster結果22k-meansCluster配送結果23HierarchicalCluster配送結果24與過去研究之比較初步結果已知最佳解KC→543HC→563521此結果為尚未進行改善解之初步結果，未來若配合良好都改善模組，應可達到同等水準。但由於SPSS為套裝軟體，並無法另外加入容量限制式，故外來仍可能自行開發演算法分析模組進行分析。256.未來研究方向進一步將撰寫群聚分析演算法加入容量限制式，以符合實際配送問題需求。對於空間pattern的描述以及其與配送結果的關連，需要進一步分析研究。