單一物流中心貨物配送模式之研究課件

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

利用接近值算數(shù)平均數(shù)2.

WPGMA

加入了權(quán)重值的計(jì)算3.

SLINK

利用最小接近值4.

Clink

利用最大接近值5.

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

K-meansalgorithms(Macqueen,1967)

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

K-medoidalgorithmsg(Vinod,1969)

對(duì)於K-means法容易掉入去最佳解的問(wèn)題加以修正。8.

CLARANS(NgandHan,1994)9.

DBSCAN(Easter,1996)

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

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

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

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

利用接近值算數(shù)平均數(shù)2.

WPGMA

加入了權(quán)重值的計(jì)算3.

SLINK

利用最小接近值4.

Clink

利用最大接近值5.

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

K-meansalgorithms(Macqueen,1967)

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

K-medoidalgorithmsg(Vinod,1969)

對(duì)於K-means法容易掉入去最佳解的問(wèn)題加以修正。8.

CLARANS(NgandHan,1994)9.

DBSCAN(Easter,1996)

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

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

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

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