单一物流中心货物配送之模式课件

1單一物流中心貨物配送模式之研究1單一物流中心貨物配送模式之研究2一、前言市場的擴大以及競爭的激烈，管理系統在空間特性問題上處理能力不足的問題已慢慢浮現，管理者對於地理資訊系統的需求也大幅提高。例如在貨物運送方面，如能結合地理資訊系統優異的空間展示、處理以及分析的功能，將能有效的克服空間阻隔，達到節省成本的目的。2一、前言3一、前言物流配送在GIS實屬於空間分析的問題，以往研究則較少考量空間分佈差異對配送產生的影響。故本研究將空間分析中群聚分析方法（ClusteringAnalysis）引入車輛途程問題(VRP)模式當中，已改善以往VRP演算法未加入空間考量的問題。並嘗試分析不同的空間分佈型態（Pattern），對不同VRP求解模式的影響。3一、前言物流配送在GIS實屬於空間分析的問題，以往研究則較4二、物流業特性分析美國物流管理協會（CLM,CouncilofLogisticsManagement,1995）之定義如下：「舉凡涉及物品、勞務以及相關資訊自原料地至消費地間，如何有效率（efficient）及有效能（cost-effective）地加以儲存（storage）與流動（flow），以因應顧客所需之規劃、執行與管理程序，皆屬之。」4二、物流業特性分析美國物流管理協會（CLM,Counci5二、物流業特性分析物流系統的演進，可分為主要的三個階段：1.第一代物流系統：又稱為原料物流或是實體供給系統，主要是屬於物料之採購及移動過程。2.第二代物流系統：又稱為銷售物流或是實體分配系統，一般狹義的物流及意旨此系統，本研究所要探討的問題也正是屬於實體分配中貨物運輸的範疇。3.第三代物流系統：又稱為企業物流系統（BusinessLogisticsSystem），就是將上述實體供給和實體分配的各項活動，合成一個整體，予以綜合管理。5二、物流業特性分析物流系統的演進，可分為主要的三個階段：6二、物流業特性分析而物流資訊系統與一般資訊系統不同的地方在於其對資料蒐集的密集性，以及資訊的詳細性和動態性，和數學模式的應用上皆比一般資訊系統來的高，數學模式的使用則是幫助決策的產生，例如線性規劃、最短路徑分析、系統模擬等，而這些特性在物流系統營運上所扮演的角色，主要是以最小的成本來處理訂單以及配送的問題，以達到最佳的服務水準。6二、物流業特性分析而物流資訊系統與一般資訊系統不同的地方在7三、地理空間分析關於地表空間的特徵，一般來說屬於空間分析的範疇，而對於地表空間型態（pattern）的描述，主要可分為幾種指標，以點資料來說，有下列幾種：–頻率(frequency)–密度(density)–幾何中心(geometriccenter)–離散(dispersion)–排列(arrangement)Clustered(密集型),Scattered(擴散型),Random(隨機型)7三、地理空間分析關於地表空間的特徵，一般來說屬於空間分析的8群聚分析而若要將空間中不同的點資料予以歸納分類，則必須要使用空間分析中的群聚分析技術（ClusterAnalysis）。群聚型隨機型8群聚分析而若要將空間中不同的點資料予以歸納分類，則必須要使9群聚分析方法1.UPGMA

利用接近值算數平均數2.

WPGMA

加入了權重值的計算3.

SLINK

利用最小接近值4.

Clink

利用最大接近值5.

Ward’sminimumvariancemethodE=(x1-Cmean1)^2+(y1-Cmean1)^2+……..取MIN9群聚分析方法1.UPGMA10群聚分析方法6.

K-meansalgorithms(Macqueen,1967)

在一群需求(demand)點中找出k個供應(supply)中心的位置﹐使得需求點至供應中心的總成本最低(鄒明城，2000)7.

K-medoidalgorithmsg(Vinod,1969)

對於K-means法容易掉入去最佳解的問題加以修正。8.

CLARANS(NgandHan,1994)9.

DBSCAN(Easter,1996)

以空間分佈的密度為考量發展求解模式。10.GDBSCAN(SANDERet.al,1998)10群聚分析方法6.

K-meansalgorithms(11四、VRP求解分析陳文瑞（1990）曾提到：

VRP是車輛在依序的服務地點做收貨(或，和)送貨的服務，且必須依照指示依序通過這些服務地點，開始和結束在同一個出發點(depotordomicile)。VRP問題的分類單一場站、多場站本研究屬於單一場站11四、VRP求解分析陳文瑞（1990）曾提到：12VRP問題探討本研究最主要的討論是關於單一場站與多車輛路線問題之研究，在實務應用上通常都以單一物流中心，同時指派多部車輛，來達到時效性最高的顧客滿意度。這樣的問題被定義為：在一廣大的區域散置分佈N各節點或顧客，每個顧客有其特定的需求量，這些需求量由某一個特定的中心站來提供，此中心站有多部車輛，每部車輛的裝載量為已知，來求由配送中心到滿足所有N各點的顧客需求的配送路線，並使配送成本達到最小。

12VRP問題探討本研究最主要的討論是關於單一場站與多車輛13VRP問題求解模式(1)先分群再排路線(ClusterFirst-Routesecond)掃瞄法(GillettandMiller,1974)-採用及座標角度掃瞄分群。(2)先排路線再分群(RouteFirst-clusterSecond)(BodinandBerman,1979)-分群結果受先前排列之路進影響。(3)節省法或插入法(SavingorInsertion)節省法(ClarkeandWright,1964)-叫無彈性，無法視群聚狀況調整13VRP問題求解模式(1)先分群再排路線(Cluster14VRP問題求解模式(4)改善與交換(Improvementorexchange)K-optimal法(LinandKernighan,1965)(5)數學規劃法(MathematicalProgrammingApproaches)(6)最佳解法(ExactProcedures)(7)人機互動法(InteractiveOptimization)14VRP問題求解模式(4)改善與交換(Improvemen15VRP問題求解模式分析由於VRP屬於非完全多項式(NP-Complete)問題，(5)數學規劃法、(6)最佳解法兩種方式求解複雜度隨問題大小呈指數成長，近年來學者紛紛致力於啟發式解法的開發。啟發式解法基本步驟（徐吉田，1993）1.指定K車輛（即路線）2.集結各需求點成一路線(啟始解)3.路線改善重新排列路線中各需求點，以得較好的路線。將某路線的點移到另一路線15VRP問題求解模式分析由於VRP屬於非完全多項式(NP-16啟發式解法基本概念目前學界研究VRP問題通常採用二階段法；第一階段初始解的產生，例如(1)先分群再排路線、(2)先排路線再分群、(3)節省法或插入法第二階段則為解的改善，例如(4)改善與交換本研究採用先分群後排路線的方法，但考慮以往相關研究較少將空間因子納入考量，故本研究引入空間分析中群聚分析（ClusteringAnalysis）的相關技術，來作為VRP的分群求解（啟始解）模式。16啟發式解法基本概念目前學界研究VRP問題通常採用二階段法17五、研究架構VRP空間群聚求解模組配送以及物流之空間資料庫車輛及路線的指派物流業特性分析VRP求解模式分析地理空間分析GIS系統比較其他求解策略不同空間Pattern分析歸納結果17五、研究架構VRP空間群聚求解模組配送以及物流之空間資料18六、研究方法將空間分析中群聚分析模組應用於VRP初始解的求得，以離散/群聚之空間分析為基礎，並以clustering分析為核心改進方法，來改進及評量配貨地一解求法。引入空間量度參數，以做為空間度量，來評定不同演算法在不同空間度量上的優劣。18六、研究方法將空間分析中群聚分析模組應用於VRP初始解的19研究假設單一場站多部車輛道路的特性初期考慮對稱性路網，日後研究在考量實際路網配送點特性限制由一部車服務需求皆不超過一部車容量車輛的限制型態容量的限制單一車種，多部車輛行車距離的限制19研究假設單一場站多部車輛20研究假設時窗(TimeWindow)的限制不考慮時窗限制客戶區位特性固定已知的需求產品本身特性以數量考慮，視為一種商品20研究假設時窗(TimeWindow)的限制21群聚分析方法本研究考慮工具的取得以及符合研究假設需求性，初步採用SPSS統計軟體，利用其內建之Analyze模組中的Classify的功能，採用k-meansCluster以及HierarchicalCluster演算法來做分群，另外分區域配送之TSP演算法則採用最遠內插法，利用VB撰寫求解程式配合VRP標準例題做測試。21群聚分析方法本研究考慮工具的取得以及符合研究假設需求性，22七、初步成果No.ProblemNameNodesVehicleCapacitySourceCostandFleetData#1E-n51-k550160Christofieds&Eilon(1969)採用Christofieds&Eilon(1969)所提出的測試例題進行測試22七、初步成果No.ProblemNameNodesVe23k-meansCluster結果23k-meansCluster結果24HierarchicalCluster結果24HierarchicalCluster結果25k-meansCluster配送結果25k-meansCluster配送結果26HierarchicalCluster配送結果26HierarchicalCluster配送結果27與過去研究之比較初步結果已知最佳解KC→543HC→563521此結果為尚未進行改善解之初步結果，未來若配合良好都改善模組，應可達到同等水準。但由於SPSS為套裝軟體，並無法另外加入容量限制式，故外來仍可能自行開發演算法分析模組進行分析。27與過去研究之比較初步結果已知最佳解KC→543521此結28八、結論初期由於受限於套裝軟體限制，群聚分析部份的僅限於現有功能，並且未加入容量限制，未來仍以自行撰寫程式模組，作為實驗驗證的工具。目前尚未就不同配送的模式討論其不同空間分佈型態下的結果，未來仍須進一步分析以瞭解群聚分析方法在空間群聚下的配送優勢。28八、結論初期由於受限於套裝軟體限制，群聚分析部份的僅限於29單一物流中心貨物配送模式之研究1單一物流中心貨物配送模式之研究30一、前言市場的擴大以及競爭的激烈，管理系統在空間特性問題上處理能力不足的問題已慢慢浮現，管理者對於地理資訊系統的需求也大幅提高。例如在貨物運送方面，如能結合地理資訊系統優異的空間展示、處理以及分析的功能，將能有效的克服空間阻隔，達到節省成本的目的。2一、前言31一、前言物流配送在GIS實屬於空間分析的問題，以往研究則較少考量空間分佈差異對配送產生的影響。故本研究將空間分析中群聚分析方法（ClusteringAnalysis）引入車輛途程問題(VRP)模式當中，已改善以往VRP演算法未加入空間考量的問題。並嘗試分析不同的空間分佈型態（Pattern），對不同VRP求解模式的影響。3一、前言物流配送在GIS實屬於空間分析的問題，以往研究則較32二、物流業特性分析美國物流管理協會（CLM,CouncilofLogisticsManagement,1995）之定義如下：「舉凡涉及物品、勞務以及相關資訊自原料地至消費地間，如何有效率（efficient）及有效能（cost-effective）地加以儲存（storage）與流動（flow），以因應顧客所需之規劃、執行與管理程序，皆屬之。」4二、物流業特性分析美國物流管理協會（CLM,Counci33二、物流業特性分析物流系統的演進，可分為主要的三個階段：1.第一代物流系統：又稱為原料物流或是實體供給系統，主要是屬於物料之採購及移動過程。2.第二代物流系統：又稱為銷售物流或是實體分配系統，一般狹義的物流及意旨此系統，本研究所要探討的問題也正是屬於實體分配中貨物運輸的範疇。3.第三代物流系統：又稱為企業物流系統（BusinessLogisticsSystem），就是將上述實體供給和實體分配的各項活動，合成一個整體，予以綜合管理。5二、物流業特性分析物流系統的演進，可分為主要的三個階段：34二、物流業特性分析而物流資訊系統與一般資訊系統不同的地方在於其對資料蒐集的密集性，以及資訊的詳細性和動態性，和數學模式的應用上皆比一般資訊系統來的高，數學模式的使用則是幫助決策的產生，例如線性規劃、最短路徑分析、系統模擬等，而這些特性在物流系統營運上所扮演的角色，主要是以最小的成本來處理訂單以及配送的問題，以達到最佳的服務水準。6二、物流業特性分析而物流資訊系統與一般資訊系統不同的地方在35三、地理空間分析關於地表空間的特徵，一般來說屬於空間分析的範疇，而對於地表空間型態（pattern）的描述，主要可分為幾種指標，以點資料來說，有下列幾種：–頻率(frequency)–密度(density)–幾何中心(geometriccenter)–離散(dispersion)–排列(arrangement)Clustered(密集型),Scattered(擴散型),Random(隨機型)7三、地理空間分析關於地表空間的特徵，一般來說屬於空間分析的36群聚分析而若要將空間中不同的點資料予以歸納分類，則必須要使用空間分析中的群聚分析技術（ClusterAnalysis）。群聚型隨機型8群聚分析而若要將空間中不同的點資料予以歸納分類，則必須要使37群聚分析方法1.UPGMA

利用接近值算數平均數2.

WPGMA

加入了權重值的計算3.

SLINK

利用最小接近值4.

Clink

利用最大接近值5.

Ward’sminimumvariancemethodE=(x1-Cmean1)^2+(y1-Cmean1)^2+……..取MIN9群聚分析方法1.UPGMA38群聚分析方法6.

K-meansalgorithms(Macqueen,1967)

在一群需求(demand)點中找出k個供應(supply)中心的位置﹐使得需求點至供應中心的總成本最低(鄒明城，2000)7.

K-medoidalgorithmsg(Vinod,1969)

對於K-means法容易掉入去最佳解的問題加以修正。8.

CLARANS(NgandHan,1994)9.

DBSCAN(Easter,1996)

以空間分佈的密度為考量發展求解模式。10.GDBSCAN(SANDERet.al,1998)10群聚分析方法6.

K-meansalgorithms(39四、VRP求解分析陳文瑞（1990）曾提到：

VRP是車輛在依序的服務地點做收貨(或，和)送貨的服務，且必須依照指示依序通過這些服務地點，開始和結束在同一個出發點(depotordomicile)。VRP問題的分類單一場站、多場站本研究屬於單一場站11四、VRP求解分析陳文瑞（1990）曾提到：40VRP問題探討本研究最主要的討論是關於單一場站與多車輛路線問題之研究，在實務應用上通常都以單一物流中心，同時指派多部車輛，來達到時效性最高的顧客滿意度。這樣的問題被定義為：在一廣大的區域散置分佈N各節點或顧客，每個顧客有其特定的需求量，這些需求量由某一個特定的中心站來提供，此中心站有多部車輛，每部車輛的裝載量為已知，來求由配送中心到滿足所有N各點的顧客需求的配送路線，並使配送成本達到最小。

12VRP問題探討本研究最主要的討論是關於單一場站與多車輛41VRP問題求解模式(1)先分群再排路線(ClusterFirst-Routesecond)掃瞄法(GillettandMiller,1974)-採用及座標角度掃瞄分群。(2)先排路線再分群(RouteFirst-clusterSecond)(BodinandBerman,1979)-分群結果受先前排列之路進影響。(3)節省法或插入法(SavingorInsertion)節省法(ClarkeandWright,1964)-叫無彈性，無法視群聚狀況調整13VRP問題求解模式(1)先分群再排路線(Cluster42VRP問題求解模式(4)改善與交換(Improvementorexchange)K-optimal法(LinandKernighan,1965)(5)數學規劃法(MathematicalProgrammingApproaches)(6)最佳解法(ExactProcedures)(7)人機互動法(InteractiveOptimization)14VRP問題求解模式(4)改善與交換(Improvemen43VRP問題求解模式分析由於VRP屬於非完全多項式(NP-Complete)問題，(5)數學規劃法、(6)最佳解法兩種方式求解複雜度隨問題大小呈指數成長，近年來學者紛紛致力於啟發式解法的開發。啟發式解法基本步驟（徐吉田，1993）1.指定K車輛（即路線）2.集結各需求點成一路線(啟始解)3.路線改善重新排列路線中各需求點，以得較好的路線。將某路線的點移到另一路線15VRP問題求解模式分析由於VRP屬於非完全多項式(NP-44啟發式解法基本概念目前學界研究VRP問題通常採用二階段法；第一階段初始解的產生，例如(1)先分群再排路線、(2)先排路線再分群、(3)節省法或插入法第二階段則為解的改善，例如(4)改善與交換本研究採用先分群後排路線的方法，但考慮以往相關研究較少將空間因子納入考量，故本研究引入空間分析中群聚分析（ClusteringAnalysis）的相關技術，來作為VRP的分群求解（啟始解）模式。16啟發式解法基本概念目前學界研究VRP問題通常採用二階段法45五、研究架構VRP空間群聚求解模組配送以及物流之空間資料庫車輛及路線的指派物流業特性分析VRP求解模式分析地理空間分析GIS系統比較其他求解策略不同空間Pattern分析歸納結果17五、研究架構VRP空間群聚求解模組配送以及物流之空間資料46六、研究方法將空間分析中群聚分析模組應用於VRP初始解的求得，以離散/群聚之空間分析為基礎，並以clustering分析為核心改進方法，來改進及評量配貨地一解求法。引入空間量度參數，以做為空間度量，來評定不同演算法在不同空間度量上的優劣。18六、研究方法將空間分析中群聚分析模組應用於VRP初始解的47研究假設單一場站多部車輛道路的特性初期考慮對稱性路網，日後研究在考量實際路網配送點特性限制由一部車服務需求皆不超過一部車容量車輛的限制型態容量的限制單一車種，多部車輛行車距離的限制19研究假設單一場站多部車輛48研究假設時窗(TimeWindow)的限制不考慮時窗限制客戶區位特性固定已知的需求產品本身特性