具时间限制之单一物流中心车辆途程问题之研究-以粒子演算法求解-课件.ppt

1、指導教授：丁介人指導教授：丁介人 博士博士研研 究究 生：蔡宏林生：蔡宏林具時間限制之單一物流中心具時間限制之單一物流中心車輛途程問題之研究車輛途程問題之研究-以粒子演算法求解以粒子演算法求解南台科技大學工業管理研究所南台科技大學工業管理研究所1南台科技大學工業管理研究所南台科技大學工業管理研究所目錄目錄五、研究方法五、研究方法四、問題定義四、問題定義三、文獻探討三、文獻探討二、研究流程與範圍二、研究流程與範圍一、研究動機與目的一、研究動機與目的2六、小節六、小節南台科技大學工業管理研究所南台科技大學工業管理研究所一、研究動機與目的一、研究動機與目的1.研究動機能源日漸短缺，能源日益重要探討物

2、流外包車之計價模式以人工作業處理車輛派送問題3南台科技大學工業管理研究所南台科技大學工業管理研究所一、研究動機與目的一、研究動機與目的2.研究目的時窗限制下改善多車種車輛路線問題規劃物流管理決策系統，有效率求得較佳車輛路徑排程4南台科技大學工業管理研究所南台科技大學工業管理研究所二、研究流程與範圍二、研究流程與範圍1.研究流程確定問題與界定研究範圍結論與建議文獻探討與回顧模式建立與修正程式撰寫績效分析與評估需要改進資料收集與整理執行測試5南台科技大學工業管理研究所南台科技大學工業管理研究所二、研究流程與範圍二、研究流程與範圍2.研究範圍需求點位置與需求量的決定何種運輸方式的決定車輛路線問題運具

3、指派決定車輛路線決定訂單指派 6南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討1. 指派問題的演進(限制：單一物流中心且需求確定)指派問題旅行推銷員問題車輛巡迴問題多車種車輛路線問題具時間限制之多車種車輛路線問題破除子巡行裝載限制多種車輛限制時間限制7南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討2.多車種之車輛路線問題 Fleets size and mixed vehicle routing problem(FSMVRP)車輛容量限制，且同時擁有多種容量、多種車輛容量限制，且同時擁有多種容量、多種固定成本之車輛問題固定成本之車輛問

4、題目標：找出旅行成本與固定成本總合最小之路線限制：(1)每個需求點都必須只由一輛車服務(2)每部車所經過的需求點之需求量總和不可超過該車輛(3)每部車必須由場站出發，拜訪若干個需求點後再回到原點8南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討2.多車種之車輛路線問題 Fleets size and mixed vehicle routing problem(FSMVRP)p 求解方法求解方法9南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討3.時窗限制之車輛路線問題Vehicle Routing Problems with Time W

5、indows (VRPTW)具有時窗限制的車輛具有時窗限制的車輛路線路線問題問題目標：不違反車輛容量和時窗限制下求出最低車輛營運成本限制：(1)每個需求點的需求量都需被滿足(2)每個需求點只能由一部車服務一次(3)每部車所經過的需求點之需求量總和不可超過該 車輛(4)每部車必須由場站出發，拜訪若干個需求點後再 回到原點(5)必須滿足每個需求點上的時窗限制10南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討3.時窗限制之車輛路線問題Vehicle Routing Problems with Time Windows (VRPTW)2.軟性時窗軟性時窗 車輛可依違反 時

6、窗限制之程 度，在給予適 當的懲罰下接 受該次服務1.硬性時窗硬性時窗 車輛早到需求 點必須等待， 遲到則拒收。時窗分類時窗分類11南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討3.時窗限制之車輛路線問題Vehicle Routing Problems with Time Windows (VRPTW)5.依據最佳化之啟發式演算法6.通用啟發式演算法2.途程建構啟發式演算法3.路線改善啟發式解法4.混合式啟發式解法1.分枝界限法求算之精確解法求解方法求解方法12南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討4.粒子群最佳化演算法 Pa

7、rticle Swarm Optimization(PSO) p Eberhart and Kennedy (1995)所提出p 以群體為基礎的最佳化搜尋技術p 模擬鳥群覓食的社會行為所衍生13南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)原理：原理：食物在哪食物在哪? ?同伴找到食物同伴找到食物14南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)特性：特性：p分

8、散式搜尋p粒子具記憶性p廣域搜尋和區域搜尋p適合在連續性的範圍內搜尋p可以被應用來解決大多數的最佳化問題15南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)數學架構：數學架構：) -)( rand(*+) -)( rand(*+*W=XPCXPCVVoldidgd2oldidid1oldidnewidVXXnewidoldidnewid+=rand()/2+0.5=W(3-1)(3-2)(3-3)目前的區域最佳目前的區域最佳解解PBest目前的全域最佳解目前的全域最佳解GBest

9、運動向量運動向量過去自身經驗過去自身經驗同伴飛行經驗同伴飛行經驗Vnewid新位置新位置Xnewid新速度新速度16南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)參數說明：參數說明： i：第i個粒子。 d：第d個空間維度。 v：粒子速度。 w：慣性權重。 , ：學習因子。 ：區域最佳解。 ：全域最佳解。 x：粒子位置。 Rand( )：介於0和1之間的隨機變數。PidPgdC1C217南台科技大學工業管理研究所南台科技大學工業管理研究所三、文獻探討三、文獻探討4.粒子群最佳化演

10、算法 Particle Swarm Optimization(PSO)流程：流程：以任意的位置和速度來初始化粒子評估各個粒子的適應值更新PBest與GBest值否是滿足終止條件更新各個粒子位置及速度開始結束18南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義問題描述問題描述：p該公司主要運輸範圍為台灣南部地區p依客戶所需飼料品名與數量指派車輛運送p每日可用車輛數不同，但已知p車輛從公司出發，工作結束才回到公司p該公司會依訂單數來調整車輛的承載率19南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義散裝車運輸成本結構散裝車運輸成本結構：p車輛

11、運費=需求點離物流中心最遠距離單價p不以車輛的總行車距離做為成本計算的依據例：若指派車輛K分別運送， 噸物料，到需求點i、i+1、i+2，並假設i+2為三節點中距離場站最遠者，則車輛K巡行所得薪資 qqq2i1ii 、) 2iqq(qc2i1ii20南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義契約車裝載方式契約車裝載方式：p每部散裝車的總承載量各異。p車輛上的儲槽分隔成3至5個不等的承載單位。p每輛散裝車內儲槽分隔方式不具統一規格。p不同種類飼料不能混合放置。21南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義合理行車距離指標合理行車

12、距離指標：定義 做為衡量飼料車司機巡行中行車距離的合理性 時表示車輛無浪費， 值越大代表車輛浪費比例越高， 值越小表示行車距離越合理 )的需求點車輛巡行中離場站最遠(2總行車距離=122南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義合理行車距離指標合理行車距離指標：除了考慮契約車司機發車意願，還須制定車輛承載率來做為是否派車考量因素 車輛最大承載量限制車輛總承載=車輛承載率23南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義問題假設：問題假設：p物流中心位置確定且唯一。p需求點與需求點之間距離已知且確定。p車輛至需求點只有卸貨而無裝貨，

13、貨物送完後則 空車回到物流中心。p物流中心有K輛外包契約散裝裝車，且每輛車程最大承載量都不相同。p每一輛車皆被分隔成數個不同大小的承載單元。p運輸成本=(車輛巡行中的總承載量)(車輛服務的需求點離場站最遠點)。p所有需求點的位置已知且需求量與時窗均已確定。 24南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義問題限制式：問題限制式：p每輛車均由物流中心出發，且服務完需求點後必空車返回原物流中心。p每個需求點只能被一輛車服務一次。p每輛車所服務的巡行路線上的總需求量不能高於車輛裝載容量限制。p每一個需求點都必須被滿足。p每一個承載單元只能裝一個需求點的一種物料。p每一

14、輛車必須符合行車距離的合理性限制。p車輛服務需求點必須遵守時窗限制。 25南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義參數說明：參數說明：pN ：需求點集合，N=0,1,2,.,n，其中0代表物流中心。pE ：支線集合。pK ：車輛集合，K=1,2,.,k，K代表車輛總數。pG ：公司訂定的合理行車距離指標值。pZ ：付給契約車司機的總運費成本。p ：車輛k在需求點i所需完成工作的時間。p ：車輛提早到達需求點的單位等待成本。p ：車輛晚到達需求點的單位延遲成本。p ：需求點i上所有種類的物料集合。p ：車輛k所有承載單位之集合， 。p ：需求點i上所有物料的總

15、需求量， 。p ：運送一單位成本到需求點i，要付給司機的薪水，kiPEPLMiFkKkQiNiNiCiNi26南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義參數說明：參數說明：p ：車輛k之容量限制， 。p ：需求點i上第m種物料之需求量， ， 。p ：需求點i到需求點j之間的距離， 。p ：車輛從需求點i到達需求點j所需時間。p ：車輛k之承單元f的容量限制， ，且 。p ：需求點i最早開始作業時間。p ：需求點i最晚開始作業時間。p ：車輛k在需求點i的等候時間。WkKkqimNiMmrijNj，iSijVkfFkf KkETiLTiWTki27南台科技大學工

16、業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義決策變數：決策變數：1，車輛k經由需求點i到需求點j，且i j時， ， ；0，otherwise。1，如果需求點i由k車輛服務時， ，且 ；0，otherwise。1，如果需求點i由車輛k服務時，且車輛k的承載單位f中是裝載著需求點i的需求物料m， ， ， ， ；0，otherwise。 xkijKkNj，iykiKkNiukfimKkFkf NiMimk , MF=MAXykfimmN,i ,fkiik28南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義數學模式：數學模式：Minimize：Subjec

17、t to： LiiiLLiiiEimKkNiMmETSPSETPqMaxMaxMaxZi11kii)0 ,()0 ,() (yc(4-1)(4-2)(4-3)(4-4)29南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義數學模式：數學模式： (4-5)(4-6)(4-7)(4-8)(4-9)(4-10)(4-11)30南台科技大學工業管理研究所南台科技大學工業管理研究所四、問題定義四、問題定義數學模式：數學模式： (4-12)(4-13)(4-14)31南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法利用利用PSO求解流程：求解流程： 隨

18、機產生每個粒子中每個維度的初始速度與初始位置訂單分配法則計算適合度求得最佳近似值更新目前粒子最佳值與群體最佳值更新目前粒子中每個維度和目前的數度與位置是否達到終止條件產生下一代開始32南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法粒子編碼方式粒子編碼方式： 需求點隨機亂數總路徑457031602684912571038123645708012333南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法訂單分派法則：訂單分派法則： 處理需求點順序與車輛路線以及車輛裝載方式之間的轉換過程。 需求點處理程序訂單分派法則所有車輛的巡行路線與裝載方式3

19、4南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法訂單分派法則：訂單分派法則：需求點依噸數處理順序為2-5-4-1-3-8-7-6，需求點5訂購3種不同飼料，需求點3訂購2種不同飼料，其他需求點都只訂購同一種飼料。 需求點處理順序需求點訂單處理順序35南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法訂單分派法則步驟：訂單分派法則步驟：1.建立每張訂單相關資料，給定車輛排列順序選擇運送車輛。2.若運送車輛中，未滿足承載限制或未滿足可發車的最低標準等條件。則必須放棄在步驟1所選取之車輛。依照排列順序改選下一部車，接著重複本步驟，直到滿足條件進

20、入步驟3。3.檢查訂單需求噸數是否會和車輛上未用承載單元的任意組合噸數相等，若噸數相等，將本訂單置入該車中噸數相等的承載單位組合，進入步驟5。 36南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法訂單分派法則步驟：訂單分派法則步驟：4.尋找最接近大於訂單需求噸數之未用承載單元的組合噸數並將訂單置入該組合承載單元中。5.檢查同一需求點上訂單是否被同一輛車服務，如果不是將需求點上訂單全數從車中取出，並依照需求點訂單處理順序重新選取該需求點上的第一張訂單，並放棄原本服務第一張訂單之所使用車輛，而改用下一部車。接著再回步驟2重新作業。6.重複以上步驟，直到所有訂單都分配到車

21、輛服務或所有可用車輛用完為止。 37南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法訂單分派法則步驟：訂單分派法則步驟：7.根據每一部車所分配到的需求點從事車輛線規劃。首先從該車應該服務的所有需求點中，搜尋離物流中心最近之需求點，將此需求點設為車輛巡行路線的第一站，接著從剩餘需求點找尋離需求點第一站最近者，設為第二站。重複以上動作以決定車輛服務需求點的順序，直到所有需求點都已分配完畢。 38南台科技大學工業管理研究所南台科技大學工業管理研究所五、研究方法五、研究方法粒子適合函數粒子適合函數：此限制式為保證每一需求點的需求量都能被滿足 uM0G),(MaxMZFit懲罰變數適合度目標函數車輛巡行的合理指標需求點的個數39南台科技大學工業管理研究所南台科技大學工業管理研究所六、小節六、小節p發展一派車模式考慮廠商契約散裝車路線與與 飼料裝載問題，使運輸成本最小化p以實際範例來驗證本研究所提出的模式與求解品質p隨機抽取飼料廠某一日訂單紀錄為例，以本研究設計方式排程進行作業p進行排程績效比較與分析4041南台科技大學工業管理研究所南台科技大學工業管理研究所