《324-單一物流中心貨物配送模式之研究.ppt》由会员分享，可在线阅读，更多相关《324-單一物流中心貨物配送模式之研究.ppt（25页珍藏版）》请在三一文库上搜索。
1、1,報告人：陳致元 指導教授：朱子豪 老師 評閱老師：孫志鴻 老師 評閱同學：鐘新南 同學,單一物流中心貨物配送模式之研究,2,1.研究動機,配送問題與物流業 VRP（車輛途程問題）之發展 物流配送在GIS實屬於空間分析的問題，以往研究則較少考量空間分佈差異對配送產生的影響。,3,2.研究目的,將空間分析中群聚分析方法（Clustering Analysis ）引入車輛途程問題(VRP)模式當中，已改善以往VRP演算法未加入空間考量的問題。 分析不同的空間分佈型態（Pattern），對不同VRP求解模式的影響。,4,研究流程,5,3.文獻回顧,陳文瑞（1990）曾提到： VRP是車輛在依序的服
2、務地點做收貨 (或，和)送貨的服務，且必須依照指示依序通過這些服務地點，開始和結束在同一個出發點 (depot or domicile)。,6,3.1 VRP 問題探討,VRP問題的分類 單一場站、多場站 本研究屬於單一場站 VRP規劃目標函式 Minimize distance距離最小化 Minimize travel time運送時程最小化 Minimize no. of vehicles車輛數目最小化 Minimize of total cost總成本最小化,7,3.2 VRP問題求解模式分析(1),VRP問題求解模式的類型與代表 (1)先分群再排路線(Cluster First-Rou
3、te second) 掃瞄法(Gillett and Miller,1974)-採用及座標角度掃瞄分群 (2)先排路線再分群(Route First-cluster Second) (Bodin and Berman,1979)-分群結果受先前排列之路進影響 (3)節省法或插入法(Saving or Insertion) 節省法(Clarke and Wright,1964)-叫無彈性，無法視群聚狀況調整 (4)改善與交換(Improvement or exchange) K-optimal法(Lin and Kernighan,1965) (5)數學規劃法(Mathematical Prog
4、ramming Approaches) (6)最佳解法(Exact Procedures) (7)人機互動法(Interactive Optimization),8,3.2 VRP問題求解模式分析(2),由於VRP屬於非完全多項式(NP-Complete)問題，(5)數學規劃法、(6)最佳解法兩種方式求解複雜度隨問題大小呈指數成長，近年來學者紛紛致力於啟發式解法的開發。 目前學界研究VRP問題通常採用二階段法， 第一階段初始解的產生，例如 (1)先分群再排路線、(2)先排路線再分群、(3)節省法或插入法 第二階段則為解的改善，例如(4)改善與交換,9,3.3 啟發式解法基本概念,啟發式解法基本
5、步驟（徐吉田，1993） 1.指定K車輛（即路線） 2.集結各需求點成一路線(啟始解) 3.路線改善 重新排列路線中各需求點，以得較好的路線。 將某路線的點移到另一路線 本研究採用先分群後排路線的方法，但考慮以往相關研究較少將空間因子納入考量，故本研究引入空間分析中集群分析（Clustering Analysis）的相關技術，來作為VRP的分群求解（啟始解）模式。,10,3.4 空間分析,關於地表空間的特徵，一般來說屬於空間分析的範疇，而對於地表空間型態（pattern）的描述，主要可分為幾種指標，以點資料來說，有下列幾種： 頻率(frequency ) 密度(density) 幾何中心(ge
6、ometric center) 離散(dispersion) 排列(arrangement) Clustered (密集型),Scattered (擴散型), Random (隨機型),11,3.4.1群聚分析,而若要將空間中不同的點資料予以歸納分類，則必須要使用空間分析中的群聚分析技術（Cluster Analysis）。 Cluster分析方法主要可以用兩種方式來討論，第一種方式可以從分裂或是聚集來描述，分裂法強調群體的差異性，聚集法強調區域的相似性，第二種方式是以階層和非階層來描述,12,3.5 空間分佈型態,群聚型,隨機型,13,3.4.1群聚分析,1. UPGMA (unweighe
7、d pair-group method using arithmetic averages) 利用接近值算數平均數 2. WPGMA (weighed pair-group method using arithmetic averages) 加入了權重值的計算 3. SLINK (single linkage clustering method) 利用最小接近值 4. Clink (complete linkage clustering method ) 利用最大接近值 5. Wards minimum variance method E=(x1-Cmean1)2+(y1-Cmean1)2+取
8、MIN 6. K-means algorithms(Macqueen,1967) 在一群需求(demand)點中找出k個供應(supply)中心的位置使得需求點至供應中心的總成本最 低(鄒明城 ，2000) 7. K-medoid algorithmsg (Vinod,1969) 對於K-means法容易掉入去最佳解的問題加以修正。 8. CLARANS(clustering large applications base on randomize search)(Ng and Han,1994) 9. DBSCAN (density-based clustering algorithm )(
9、Easter,1996) 以空間分佈的密度為考量發展求解模 10. GDBSCAN(generalized density-based spatial clustering of application with noise)(SANDER et. al,1998),14,研究架構,VRP空間群聚求解模組,配送以及物流之空間資料庫,車輛及路線的指派,物流業特性分析,VRP求解模式分析,地理空間分析,GIS系統,比較,其他求解策略,不同空間Pattern,分析,歸納結果,15,4.研究方法,將空間分析中群聚分析模組應用於VRP初始解的求得，以離散/群聚之空間分析為基礎，並以clustering
10、分析為核心改進方法，來改進及評量配貨地一解求法。 引入空間量度參數，以做為空間度量，來評定不同演算法在不同空間度量上的優劣。,16,4.1研究假設(1),單一場站多部車輛 道路的特性 初期考慮對稱性路網，日後研究在考量實際路網 配送點特性限制 由一部車服務 需求皆不超過一部車容量 車輛的限制型態 容量的限制 單一車種，多部車輛 行車距離的限制,17,4.2研究假設(2),時窗(Time Window)的限制 不考慮時窗限制 客戶區位特性 固定已知的需求 產品本身特性 以數量考慮，視為一種商品,18,4.3 群聚分析,本研究考慮工具的取得以及符合研究假設需求性，初步採用SPSS統計軟體，利用其內
11、建之Analyze 模組中的Classify 的功能，採用k-means Cluster 以及 Hierarchical Cluster 演算法來做分群，另外區域配送之TSP演算法則採用最遠內插法，利用VB撰寫求解程式配合VRP標準例題做測試。,19,5初步成果,採用Christofieds & Eilon(1969)所提出的測試例題進行測試,20,k-means Cluster結果,21,Hierarchical Cluster結果,22,k-means Cluster 配送結果,23,Hierarchical Cluster配送結果,24,與過去研究之比較,此結果為尚未進行改善解之初步結果，未來若配合良好都改善模組，應可達到同等水準。 但由於SPSS為套裝軟體，並無法另外加入容量限制式，故外來仍可能自行開發演算法分析模組進行分析。,25,6.未來研究方向,進一步將撰寫群聚分析演算法加入容量限制式，以符合實際配送問題需求。 對於空間pattern的描述以及其與配送結果的關連，需要進一步分析研究。,