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

《具时间限制之单一物流中心车辆途程问题之研究以粒子演算法求解-ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、具時間限制之單一物流中心車輛途程問題之研究-以粒子演算法求解南台科技大學工業管理研究所1目錄五、研究方法四、問題定義三、文獻探討二、研究流程與範圍一、研究動機與目的六、小節2一、研究動機與目的1.研究動機能源日漸短缺，能源日益重要探討物流外包車之計價模式以人工作業處理車輛派送問題3一、研究動機與目的2.研究目的時窗限制下改善多車種車輛路線問題規劃物流管理決策系統，有效率求得較佳車輛路徑排程4二、研究流程與範圍1.研究流程確定問題與界定研究範圍結論與建議文獻探討與回顧模式建立與修正程式撰寫績效分析與評估

2、需要改進資料收集與整理執行測試5二、研究流程與範圍2.研究範圍需求點位置與需求量的決定何種運輸方式的決定車輛路線問題運具指派決定車輛路線決定訂單指派6三、文獻探討1.指派問題的演進(限制：單一物流中心且需求確定)指派問題旅行推銷員問題車輛巡迴問題多車種車輛路線問題具時間限制之多車種車輛路線問題破除子巡行裝載限制多種車輛限制時間限制7三、文獻探討2.多車種之車輛路線問題Fleetssizeandmixedvehicleroutingproblem(FSMVRP)車輛容量限制，且同時擁有多種容量、多種固定

3、成本之車輛問題目標：找出旅行成本與固定成本總合最小之路線限制：(1)每個需求點都必須只由一輛車服務(2)每部車所經過的需求點之需求量總和不可超過該車輛(3)每部車必須由場站出發，拜訪若干個需求點後再回到原點8三、文獻探討2.多車種之車輛路線問題Fleetssizeandmixedvehicleroutingproblem(FSMVRP)求解方法9三、文獻探討3.時窗限制之車輛路線問題VehicleRoutingProblemswithTimeWindows(VRPTW)具有時窗限制的車輛路線問題目標：

4、不違反車輛容量和時窗限制下求出最低車輛營運成本限制：(1)每個需求點的需求量都需被滿足(2)每個需求點只能由一部車服務一次(3)每部車所經過的需求點之需求量總和不可超過該車輛(4)每部車必須由場站出發，拜訪若干個需求點後再回到原點(5)必須滿足每個需求點上的時窗限制10三、文獻探討3.時窗限制之車輛路線問題VehicleRoutingProblemswithTimeWindows(VRPTW)2.軟性時窗車輛可依違反時窗限制之程度，在給予適當的懲罰下接受該次服務1.硬性時窗車輛早到需求點必須等待，遲到

5、則拒收。時窗分類11三、文獻探討3.時窗限制之車輛路線問題VehicleRoutingProblemswithTimeWindows(VRPTW)5.依據最佳化之啟發式演算法6.通用啟發式演算法2.途程建構啟發式演算法3.路線改善啟發式解法4.混合式啟發式解法1.分枝界限法求算之精確解法求解方法12三、文獻探討4.粒子群最佳化演算法ParticleSwarmOptimization(PSO)EberhartandKennedy(1995)所提出以群體為基礎的最佳化搜尋技術模擬鳥群覓食的社會行為所衍生1

6、3三、文獻探討4.粒子群最佳化演算法ParticleSwarmOptimization(PSO)原理：食物在哪?同伴找到食物14三、文獻探討4.粒子群最佳化演算法ParticleSwarmOptimization(PSO)特性：分散式搜尋粒子具記憶性廣域搜尋和區域搜尋適合在連續性的範圍內搜尋可以被應用來解決大多數的最佳化問題15三、文獻探討4.粒子群最佳化演算法ParticleSwarmOptimization(PSO)數學架構：(3-1)(3-2)(3-3)目前的區域最佳解PBest目前的全域最佳解

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

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