单一物流中心货物配送之模式(1)cfh.pptx

單一物流中心貨物配送模式之研究1單一物流中心貨物配送模式之研究一、前言n n市場的擴大以及競爭的激烈，管理系統在市場的擴大以及競爭的激烈，管理系統在空間空間特性特性問題上處理能力不足的問題已慢慢浮現，問題上處理能力不足的問題已慢慢浮現，管理者對於地理資訊系統的需求也大幅提高。管理者對於地理資訊系統的需求也大幅提高。n n例如在貨物運送方面，如能結合地理資訊系統例如在貨物運送方面，如能結合地理資訊系統優異的空間展示、處理以及分析的功能，將能優異的空間展示、處理以及分析的功能，將能有效的克服空間阻隔，達到有效的克服空間阻隔，達到節省成本節省成本的目的。的目的。2單一物流中心貨物配送模式之研究一、前言n n物流配送在物流配送在GISGIS實屬於空間分析的問題，以往實屬於空間分析的問題，以往研究則較少考量研究則較少考量空間分佈差異空間分佈差異對配送產生的影對配送產生的影響。故本研究將空間分析中響。故本研究將空間分析中群聚分析方法群聚分析方法（ClusteringAnalysisClusteringAnalysis）引入車輛途程問題引入車輛途程問題(VRP)VRP)模式當中，已改善以往模式當中，已改善以往VRPVRP演算法未加演算法未加入空間考量的問題。並嘗試分析不同的入空間考量的問題。並嘗試分析不同的空間分空間分佈型態佈型態（PatternPattern），），對不同對不同VRPVRP求解模式的影求解模式的影響。響。3單一物流中心貨物配送模式之研究二、物流業特性分析n n美美國國物物流流管管理理協協會會（CLM,CLM,CouncilCouncilofofLogisticsLogisticsManagement,1995Management,1995）之定義如下：之定義如下：舉凡涉及物品、勞務以及相關資訊自原料地至舉凡涉及物品、勞務以及相關資訊自原料地至消費地間，如何有效率（消費地間，如何有效率（efficientefficient）及有效能及有效能（cost-effectivecost-effective）地加以儲存（地加以儲存（storagestorage）與流動與流動（flowflow），），以因應顧客所需之規劃、執行與管理以因應顧客所需之規劃、執行與管理程序，皆屬之。程序，皆屬之。4單一物流中心貨物配送模式之研究二、物流業特性分析n n物流系統的演進，可分為主要的三個階段：物流系統的演進，可分為主要的三個階段：1.1.第一代物流系統：第一代物流系統：又又稱稱為為原原料料物物流流或或是是實實體體供供給給系系統統，主主要要是是屬屬於於物物料料之採購及移動過程。之採購及移動過程。2.2.第二代物流系統：第二代物流系統：又又稱稱為為銷銷售售物物流流或或是是實實體體分分配配系系統統，一一般般狹狹義義的的物物流流及及意意旨旨此此系系統統，本本研研究究所所要要探探討討的的問問題題也也正正是是屬屬於於實實體分配中貨物運輸的範疇。體分配中貨物運輸的範疇。3.3.第三代物流系統：第三代物流系統：又又稱稱為為企企業業物物流流系系統統（BusinessBusinessLogisticsLogisticsSystemSystem），就就是是將將上上述述實實體體供供給給和和實實體體分分配配的的各各項項活活動動，合合成成一一個整體，予以綜合管理。個整體，予以綜合管理。5單一物流中心貨物配送模式之研究二、物流業特性分析n n而物流資訊系統與一般資訊系統不同的地方在而物流資訊系統與一般資訊系統不同的地方在於其對於其對資料蒐集的密集性資料蒐集的密集性，以及，以及資訊的詳細性資訊的詳細性和動態性和動態性，和數學模式的應用和數學模式的應用上皆比一般資訊上皆比一般資訊系統來的高，數學模式的使用則是幫助決策的系統來的高，數學模式的使用則是幫助決策的產生，例如線性規劃、最短路徑分析、系統模產生，例如線性規劃、最短路徑分析、系統模擬等，而這些特性在物流系統營運上所扮演的擬等，而這些特性在物流系統營運上所扮演的角色，主要是以最小的成本來處理訂單以及配角色，主要是以最小的成本來處理訂單以及配送的問題，以達到最佳的服務水準。送的問題，以達到最佳的服務水準。6單一物流中心貨物配送模式之研究三、地理空間分析n n關關於於地地表表空空間間的的特特徵徵，一一般般來來說說屬屬於於空空間間分分析析的的範範疇疇，而而對對於於地地表表空空間間型型態態（patternpattern）的的描描述述，主主要要可可分分為為幾幾種種指指標標，以以點點資資料料來來說說，有有下下列列幾種：幾種：v 頻率頻率(frequency)frequency)v 密度密度(density)density)v 幾何中心幾何中心(geometriccenter)geometriccenter)v 離散離散(dispersion)dispersion)v 排列排列(arrangement)arrangement)Clustered(Clustered(密集型密集型),),Scattered(Scattered(擴散型擴散型),),Random(Random(隨機隨機型型)7單一物流中心貨物配送模式之研究群聚分析n n而若要將空間中不同的點資料予以歸納分類，則而若要將空間中不同的點資料予以歸納分類，則必須要使用空間分析中的必須要使用空間分析中的群聚分析技術群聚分析技術（ClusterClusterAnalysisAnalysis）。）。群聚型隨機型8單一物流中心貨物配送模式之研究群聚分析方法1.UPGMA利用接近值算數平均數2.WPGMA加入了權重值的計算3.SLINK利用最小接近值4.Clink利用最大接近值5.WardsminimumvariancemethodE=(x1-Cmean1)2+(y1-Cmean1)2+.取MIN9單一物流中心貨物配送模式之研究群聚分析方法6.K-meansalgorithms(Macqueen,1967)6.K-meansalgorithms(Macqueen,1967)在一群需求在一群需求(demand)demand)點中找出點中找出k k個供應個供應(supply)supply)中心的位中心的位置置 使得需求點至供應中心的總成本最低使得需求點至供應中心的總成本最低(鄒明城鄒明城，2000)2000)7.7.K-medoidalgorithmsg(Vinod,1969)K-medoidalgorithmsg(Vinod,1969)對於對於K-meansK-means法容易掉入去最佳解的問題加以修正。法容易掉入去最佳解的問題加以修正。8.8.CLARANS(NgandHan,1994)CLARANS(NgandHan,1994)9.DBSCAN(Easter,1996)9.DBSCAN(Easter,1996)以空間分佈的密度為考量發展求解模式。以空間分佈的密度為考量發展求解模式。10.GDBSCAN(SANDERet.al,1998)10.GDBSCAN(SANDERet.al,1998)10單一物流中心貨物配送模式之研究四、VRP求解分析n n陳文瑞（陳文瑞（19901990）曾提到：）曾提到：VRPVRP是車輛在依序的服務地點做收貨是車輛在依序的服務地點做收貨(或，和或，和)送送貨的服務，且必須依照指示依序通過這些服務地貨的服務，且必須依照指示依序通過這些服務地點，開始和結束在同一個出發點點，開始和結束在同一個出發點(depotordepotordomicile)domicile)。n nVRPVRP問題的分類問題的分類 單一場站、多場站單一場站、多場站 本研究屬於單一場站本研究屬於單一場站11單一物流中心貨物配送模式之研究VRP問題探討n n本研究最主要的討論是關於本研究最主要的討論是關於單一場站與多車輛單一場站與多車輛路路線問題之研究，在實務應用上通常都以單一物流線問題之研究，在實務應用上通常都以單一物流中心，同時指派多部車輛，來達到時效性最高的中心，同時指派多部車輛，來達到時效性最高的顧客滿意度。顧客滿意度。n n這樣的問題被定義為：在一廣大的區域散置分佈這樣的問題被定義為：在一廣大的區域散置分佈N N各節點或顧客，每個顧客有其特定的需求量，各節點或顧客，每個顧客有其特定的需求量，這些需求量由某一個特定的中心站來提供，此中這些需求量由某一個特定的中心站來提供，此中心站有多部車輛，每部車輛的裝載量為已知，來心站有多部車輛，每部車輛的裝載量為已知，來求由配送中心到滿足所有求由配送中心到滿足所有N N各點的顧客需求的配各點的顧客需求的配送路線，並使送路線，並使配送成本達到最小配送成本達到最小。12單一物流中心貨物配送模式之研究VRP問題求解模式(1)(1)先分群再排路線先分群再排路線(ClusterFirst-Routesecond)ClusterFirst-Routesecond)掃瞄法掃瞄法(GillettandMiller,1974)-GillettandMiller,1974)-採用及座標角度掃瞄採用及座標角度掃瞄分群。分群。(2)(2)先排路線再分群先排路線再分群(RouteFirst-clusterSecond)RouteFirst-clusterSecond)(BodinandBerman,1979)-(BodinandBerman,1979)-分群結果受先前排列之路進分群結果受先前排列之路進影響。影響。(3)(3)節省法或插入法節省法或插入法(SavingorInsertion)SavingorInsertion)節省法節省法(ClarkeandWright,1964)-ClarkeandWright,1964)-叫無彈性，無法視群叫無彈性，無法視群聚狀況調整聚狀況調整13單一物流中心貨物配送模式之研究VRP問題求解模式n n(4)(4)改善與交換改善與交換(Improvementorexchange)Improvementorexchange)K-optimalK-optimal法法(LinandKernighan,1965)LinandKernighan,1965)n n(5)(5)數學規劃法數學規劃法(MathematicalProgrammingMathematicalProgrammingApproaches)Approaches)n n(6)(6)最佳解法最佳解法(ExactProcedures)ExactProcedures)n n(7)(7)人機互動法人機互動法(InteractiveOptimization)InteractiveOptimization)14單一物流中心貨物配送模式之研究VRP問題求解模式分析n n由於由於VRPVRP屬於非完全多項式屬於非完全多項式(NP-Complete)NP-Complete)問題，問題，(5)(5)數學規劃法、數學規劃法、(6)(6)最佳解法兩種方式求解複最佳解法兩種方式求解複雜度隨問題大小呈指數成長，近年來學者紛紛雜度隨問題大小呈指數成長，近年來學者紛紛致力於啟發式解法的開發。致力於啟發式解法的開發。n n啟發式解法基本步驟（徐吉田，啟發式解法基本步驟（徐吉田，19931993）1.1.指定指定K K車輛（即路線）車輛（即路線）2.2.集結各需求點成一路線集結各需求點成一路線(啟始解啟始解)3.3.路線改善路線改善1.1.重新排列路線中各需求點，以得較好的路線。重新排列路線中各需求點，以得較好的路線。2.2.將某路線的點移到另一路線將某路線的點移到另一路線15單一物流中心貨物配送模式之研究啟發式解法基本概念n n目前學界研究目前學界研究VRPVRP問題通常採用二階段法；問題通常採用二階段法；第一階段第一階段初始解的產生，初始解的產生，例如例如(1)(1)先分群再排路先分群再排路線、線、(2)(2)先排路線再分群、先排路線再分群、(3)(3)節省法或插入法節省法或插入法 第二階段第二階段則為解的改善，則為解的改善，例如例如(4)(4)改善與交換改善與交換n n本研究採用先分群後排路線的方法，但考慮以本研究採用先分群後排路線的方法，但考慮以往相關研究較少將空間因子納入考量，故本研往相關研究較少將空間因子納入考量，故本研究引入空間分析中究引入空間分析中群聚分析群聚分析（ClusteringClusteringAnalysisAnalysis）的相關技術，來作為的相關技術，來作為VRPVRP的分群求解的分群求解（啟始解）模式。（啟始解）模式。16單一物流中心貨物配送模式之研究五、研究架構VRP空間群聚求解模組配送以及物流之空間資料庫車輛及路線的指派物流業特性分析VRP求解模式分析地理空間分析GIS系統比較其他求解策略不同空間Pattern分析歸納結果17單一物流中心貨物配送模式之研究六、研究方法n n將空間分析中群聚分析模組應用於將空間分析中群聚分析模組應用於VRPVRP初始解初始解的求得，以離散的求得，以離散/群聚之空間分析為基礎，並群聚之空間分析為基礎，並以以clusteringclustering分析為核心改進方法，來改進及評分析為核心改進方法，來改進及評量配貨地一解求法。量配貨地一解求法。n n引入引入空間量度參數空間量度參數，以做為空間度量，來評定，以做為空間度量，來評定不同演算法在不同空間度量上的優劣。不同演算法在不同空間度量上的優劣。18單一物流中心貨物配送模式之研究研究假設n n單一場站多部車輛單一場站多部車輛道路的特性道路的特性 初期考慮對稱性路網，日後研究在考量實際路網初期考慮對稱性路網，日後研究在考量實際路網配送點特性限制配送點特性限制 由一部車服務由一部車服務 需求皆不超過一部車容量需求皆不超過一部車容量車輛的限制型態車輛的限制型態 容量的限制容量的限制n n單一車種，多部車輛單一車種，多部車輛 行車距離的限制行車距離的限制19單一物流中心貨物配送模式之研究研究假設時窗時窗(TimeWindow)TimeWindow)的限制的限制 不考慮時窗限制不考慮時窗限制客戶區位特性客戶區位特性 固定已知的需求固定已知的需求產品本身特性產品本身特性 以數量考慮，視為一種商品以數量考慮，視為一種商品20單一物流中心貨物配送模式之研究群聚分析方法n n本研究考慮工具的取得以及符合研究假設需求本研究考慮工具的取得以及符合研究假設需求性，初步採用性，初步採用SPSSSPSS統計軟體，利用其內建之統計軟體，利用其內建之AnalyzeAnalyze模組中的模組中的ClassifyClassify的功能，採用的功能，採用k-k-meansClustermeansCluster以及以及 HierarchicalClusterHierarchicalCluster演算法演算法來做分群，另外分區域配送之來做分群，另外分區域配送之TSPTSP演算法則採演算法則採用最遠內插法，利用用最遠內插法，利用VBVB撰寫求解程式配合撰寫求解程式配合VRPVRP標準例題做測試。標準例題做測試。21單一物流中心貨物配送模式之研究七、初步成果No.Problem NameNodesVehicle CapacitySourceCost and Fleet Data#1E-n51-k550160Christofieds&Eilon(1969)採用Christofieds&Eilon(1969)所提出的測試例題進行測試22單一物流中心貨物配送模式之研究k-meansCluster結果23單一物流中心貨物配送模式之研究HierarchicalCluster結果24單一物流中心貨物配送模式之研究k-meansCluster配送結果25單一物流中心貨物配送模式之研究HierarchicalCluster配送結果26單一物流中心貨物配送模式之研究與過去研究之比較初步結果初步結果已知最佳解已知最佳解KC543KC543HC563HC563521521此結果為尚未進行改善解之初步結果，未來若配合良好都改善模組，應可達到同等水準。但由於SPSS為套裝軟體，並無法另外加入容量限制式，故外來仍可能自行開發演算法分析模組進行分析。27單一物流中心貨物配送模式之研究八、結論n n初期由於受限於套裝軟體限制，群聚分析部份的僅限於現有功能，並且未加入容量限制，未來仍以自行撰寫程式模組，作為實驗驗證的工具。n n目前尚未就不同配送的模式討論其不同空間分佈型態下的結果，未來仍須進一步分析以瞭解群聚分析方法在空間群聚下的配送優勢。28單一物流中心貨物配送模式之研究29單一物流中心貨物配送模式之研究30