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

《具时间限制之单一物流中心车辆途程问题之研究 以粒子演算法求解课件.ppt》由会员分享，可在线阅读，更多相关《具时间限制之单一物流中心车辆途程问题之研究 以粒子演算法求解课件.ppt（41页珍藏版）》请在三一办公上搜索。

1、指導教授：丁介人 博士研 究 生：蔡宏林,具時間限制之單一物流中心車輛途程問題之研究-以粒子演算法求解,南台科技大學工業管理研究所,1,目錄,五、研究方法,四、問題定義,三、文獻探討,二、研究流程與範圍,一、研究動機與目的,2,六、小節,一、研究動機與目的,1.研究動機能源日漸短缺，能源日益重要探討物流外包車之計價模式以人工作業處理車輛派送問題,3,一、研究動機與目的,2.研究目的時窗限制下改善多車種車輛路線問題規劃物流管理決策系統，有效率求得較佳輛徑排程,4,二、研究流程與範圍,1.研究流程,5,二、研究流程與範圍,2.研究範圍,需求點位置與需求量的決定,何種運輸方式的決定,車輛路線問題,運

2、具指派決定,車輛路線決定,訂單指派,6,三、文獻探討,1.指派問題的演進(限制：單一物流中心且需求確定),指派問題,旅行推銷員問題,車輛巡迴問題,多車種車輛路線問題,具時間限制之多車種車輛路線問題,破除子巡行,裝載限制,多種車輛限制,時間限制,7,三、文獻探討,2.多車種之車輛路線問題 Fleets size and mixed vehicle routing problem(FSMVRP)車輛容量限制，且同時擁有多種容量、多種固定成本之車輛問題目標：找出旅行成本與固定成本總合最小之路線限制：(1)每個需求點都必須只由一輛車服務(2)每部車所經過的需求點之需求量總和不可超過該車輛(3)每部車必

3、須由場站出發，拜訪若干個需求點後再回到原點,8,三、文獻探討,2.多車種之車輛路線問題 Fleets size and mixed vehicle routing problem(FSMVRP)求解方法,9,三、文獻探討,3.時窗限制之車輛路線問題Vehicle Routing Problems with Time Windows(VRPTW)具有時窗限制的車輛路線問題目標：不違反車輛容量和時窗限制下求出最低車輛營運成本限制：(1)每個需求點的需求量都需被滿足(2)每個需求點只能由一部車服務一次(3)每部車所經過的需求點之需求量總和不可超過該 車輛(4)每部車必須由場站出發，拜訪若干個需求點後

4、再 回到原點(5)必須滿足每個需求點上的時窗限制,10,三、文獻探討,3.時窗限制之車輛路線問題Vehicle Routing Problems with Time Windows(VRPTW),11,三、文獻探討,3.時窗限制之車輛路線問題Vehicle Routing Problems with Time Windows(VRPTW),5.依據最佳化之啟發式演算法,6.通用啟發式演算法,2.途程建構啟發式演算法,3.路線改善啟發式解法,4.混合式啟發式解法,1.分枝界限法求算之精確解法,求解方法,12,三、文獻探討,4.粒子群最佳化演算法 Particle Swarm Optimizati

5、on(PSO)Eberhart and Kennedy(1995)所提出以群體為基礎的最佳化搜尋技術模擬鳥群覓食的社會行為所衍生,13,三、文獻探討,4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)原理：,食物在哪?,同伴找到食物,14,三、文獻探討,4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)特性：分散式搜尋粒子具記憶性廣域搜尋和區域搜尋適合在連續性的範圍內搜尋可以被應用來解決大多數的最佳化問題,15,三、文獻探討,4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)數學架

6、構：,(3-1),(3-2),(3-3),目前的區域最佳解PBest,目前的全域最佳解GBest,過去自身經驗,同伴飛行經驗,16,三、文獻探討,4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)參數說明：i：第i個子。d：第d個空間維。v：粒子速度。w：慣性權重。,：學習因子。：區域最佳解。：全域最佳解。x：粒子位置。Rand()：介於0和1之間的隨機變。,17,三、文獻探討,4.粒子群最佳化演算法 Particle Swarm Optimization(PSO)流程：,以任意的位置和速度來初始化粒子,評估各個粒子的適應值,更新PBest與GBest值,

7、否,是,滿足終止條件,更新各個粒子位置及速度,開始,結束,18,四、問題定義,問題描述：該公司主要運輸範圍為台灣南部地區依客戶所需飼料品名與數量指派車輛運送每日可用車輛數不同，但已知車輛從公司出發，工作結束才回到公司該公司會依訂單數來調整車輛的承載率,19,四、問題定義,散裝車運輸成本結構：車輛運費=需求點離物流中心最遠距離單價不以車輛的總行車距離做為成本計算的依據例：若指派車輛K分別運送，噸物料，到需求點i、i+1、i+2，並假設i+2為三節點中距離場站最遠者，則車輛K巡行所得薪資,20,四、問題定義,契約車裝載方式：每部散裝車的總承載量各異。車輛上的儲槽分隔成3至5個不等的承載單位。每輛散

8、裝車內儲槽分隔方式不具統一規格。不同種類飼料不能混合放置。,21,四、問題定義,合理行車距離指標：定義 做為衡量飼料車司機巡行中行車距離的合理性 時表示車輛無浪費，值越大代表車輛浪費比例越高，值越小表示行車距離越合理,22,四、問題定義,合理行車距離指標：除了考慮契約車司機發車意願，還須制定車輛承載率來做為是否派車考量因素,23,四、問題定義,問題假設：物流中心位置確定且唯一。需求點與需求點之間距離已知且確定。車輛至需求點只有卸貨而無裝貨，貨物送完後則 空車回到物流中心。物流中心有K輛外包契約散裝裝車，且每輛車程最大承載量都不相同。每一輛車皆被分隔成數個不同大小的承載單元。運輸成本=(車輛巡行

9、中的總承載量)(車輛服務的需求點離場站最遠點)。所有需求點的位置已知且需求量與時窗均已確定。,24,四、問題定義,問題限制式：每輛車均由物流中心出發，且服務完需求點後必空車返回原物流中心。每個需求點只能被一輛車服務一次。每輛車所服務的巡行路線上的總需求量不能高於車輛裝載容量限制。每一個需求點都必須被滿足。每一個承載單元只能裝一個需求點的一種物料。每一輛車必須符合行車距離的合理性限制。車輛服務需求點必須遵守時窗限制。,25,四、問題定義,參數說明：N：需求點集合，N=0,1,2,.,n，其中0代表物流中心。E：支線集合。K：車輛集合，K=1,2,.,k，K代表車輛總數。G：公司訂定的合理行車距離

10、指標值。Z：付給契約車司機的總運費成本。：車輛k在需求點i所需完成工作的時間。：車輛提早到達需求點的單位等待成本。：車輛晚到達需求點的單位延遲成本。：需求點i上所有種類的物料集合。：車輛k所有承載單位之集合，。：需求點i上所有物料的總需求量，。：運送一單位成本到需求點i，要付給司機的薪水，,26,四、問題定義,參數說明：車輛k之容量限制，。：需求點i上第m種物料之需求量，。：需求點i到需求點j之間的距離，。：車輛從需求點i到達需求點j所需時間。：車輛k之承單元f的容量限制，且。：需求點i最早開始作業時間。：需求點i最晚開始作業時間。：車輛k在需求點i的等候時間。,27,四、問題定義,決策變數：

11、1，車輛k經由需求點i到需求點j，且i j時，；0，otherwise。1，如果需求點i由k車輛服務時，且；0，otherwise。1，如果需求點i由車輛k服務時，且車輛k的承載單位f中是裝載著需求點i的需求物料m，；0，otherwise。,28,四、問題定義,數學模式：Minimize：Subject to：,(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求解流程：,

12、32,五、研究方法,粒子編碼方式：,需求點,隨機亂數,總路徑,4,5,7,0,3,1,6,0,2,6,8,4,9,1,2,5,7,10,3,8,1,2,3,6,4,5,7,0,8,0,1,2,3,33,五、研究方法,訂單分派法則：處理需求點順序與車輛路線以及車輛裝載方式之間的轉換過程。,34,五、研究方法,訂單分派法則：需求點依噸數處理順序為2-5-4-1-3-8-7-6，需求點5訂購3種不同飼料，需求點3訂購2種不同飼料，其他需求點都只訂購同一種飼料。,需求點處理順序,需求點訂單處理順序,35,五、研究方法,訂單分派法則步驟：建立每張訂單相關資料，給定車輛排列順序選擇運送車輛。若運送車輛中，

13、未滿足承載限制或未滿足可發車的最低標準等條件。則必須放棄在步驟1所選取之車輛。依照排列順序改選下一部車，接著重複本步驟，直到滿足條件進入步驟3。檢查訂單需求噸數是否會和車輛上未用承載單元的任意組合噸數相等，若噸數相等，將本訂單置入該車中噸數相等的承載單位組合，進入步驟5。,36,五、研究方法,訂單分派法則步驟：尋找最接近大於訂單需求噸數之未用承載單元的組合噸數並將訂單置入該組合承載單元中。檢查同一需求點上訂單是否被同一輛車服務，如果不是將需求點上訂單全數從車中取出，並依照需求點訂單處理順序重新選取該需求點上的第一張訂單，並放棄原本服務第一張訂單之所使用車輛，而改用下一部車。接著再回步驟2重新作

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