車輛優(yōu)化調(diào)度問題的算法之精確算法2

項目一人工智能算法在配送環(huán)節(jié)應(yīng)用《物流人工智能技術(shù)》任務(wù)八車輛優(yōu)化調(diào)度問題的算法之精確算法2目錄/CONTENTS301分枝定界算法02K度中心樹算法03集分割和列生成算法04動態(tài)規(guī)劃算法4【知識目標(biāo)】1.掌握精確算法的類型、特點。【情感目標(biāo)】1.具有工匠精神、服務(wù)意識、環(huán)保意識、質(zhì)量意識、安全意識；2.培養(yǎng)獨立獲取信息和自學(xué)能力；3.堅定擁護中國共產(chǎn)黨領(lǐng)導(dǎo)和我國社會主義制度?！窘虒W(xué)目標(biāo)】車輛優(yōu)化調(diào)度問題是組合優(yōu)化領(lǐng)域中的典型的NP-hard問題，其求解方法非常復(fù)雜，但究其實質(zhì)，基本上可以分為：啟發(fā)式算法精確算法12精確算法可分為3種類型：01向樹搜索算法動態(tài)規(guī)劃算法整數(shù)線性規(guī)劃算法0203分枝定界法割平面法動態(tài)規(guī)劃法集分割和列生成算法1234分枝定界算法是一種在問題的解空間樹上搜索問題的解的方法，其求解VRP問題的基本思路是：以相應(yīng)的不含整數(shù)約束的VRP問題的最優(yōu)解為出發(fā)點，若此解是整數(shù)解，那么這個解就是原VRP問題的最優(yōu)解，否則以非整數(shù)解的相鄰整數(shù)作附加條件，形成2個分枝，即2個子問題，進行求解。適用于求解小型VRP問題。一、分枝定界算法二、K度中心樹算法先將問題轉(zhuǎn)化為“k度中心樹”后，再進行求解、該方法是對固定m的m-TSP進行k度中心樹松弛。通過拉格朗日松弛法，將其中一個約束條件消去，并進一步將原來的最小化問題轉(zhuǎn)化為3個易于求解的子最小化問題，然后進行求解。K度中心樹算法三、集分割和列生成算法VRP問題的集分割方法的提出者直接考慮可行解集合，并在此基礎(chǔ)上進行優(yōu)化，盡管所建立的VRP模型最為簡單，但該算法和動態(tài)規(guī)劃算法一樣存在狀態(tài)數(shù)過于龐大的問題。集分割和列生成算法三、集分割和列生成算法后來引入了列生成方法進行求解，在該方法中，原問題被轉(zhuǎn)化為簡化問題，考慮的范圍是所有可能的可行解的子集，在此基礎(chǔ)上重復(fù)求解，通過引入優(yōu)化對偶變量向量，對該簡化問題松弛，通過計算列的最小邊際成本，確定最優(yōu)解。其算法本質(zhì)上是最短路徑算法，同時結(jié)合了分枝定界算法。用它可求解有100個客戶的帶時間窗口的VRP問題。集分割和列生成算法四、動態(tài)規(guī)劃算法將VRP問題視為一個n階段的決策問題，進而將其轉(zhuǎn)化為依次求解n個具有遞推關(guān)系的單階段的決策問題，從而簡化計算過程，用這種方法可求得VRP的最優(yōu)解，但僅適用于較小規(guī)模的尋優(yōu)問題。動態(tài)規(guī)劃法求解VRP問題的基本思路：動態(tài)規(guī)劃算法的有效性依賴于待求解問題本身具有的兩個重要性質(zhì)：四、動態(tài)規(guī)劃算法子問題重疊性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)12四、動態(tài)規(guī)劃算法最優(yōu)子結(jié)構(gòu)性質(zhì)1如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，即滿足最優(yōu)化原理。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決問題提供了重要線索。四、動態(tài)規(guī)劃算法子問題重疊性質(zhì)2子問題重疊性質(zhì)是指在用遞歸算法自頂向下對問題進行求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復(fù)計算多次。動態(tài)規(guī)劃算法正是利用子問題的重疊性質(zhì)，對每一個子問題只計算一次，然后將其計算結(jié)果保存在一個表格中，當(dāng)再次需要計算已經(jīng)計算過的子問題時，只是在表格中簡單地查看一下結(jié)果，從而獲得較高的解題效率。四、動態(tài)規(guī)劃算法可以按照以下步驟設(shè)計動態(tài)規(guī)劃算法：第一步：分析問題的最優(yōu)解，找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；第二步：遞歸地定義最優(yōu)值；第三步：采用自底向上的方式計算問題的最優(yōu)值；第四步：根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。在對VRP問題研究的早期，主要從單源點派車，考慮如何通過最短路線或在最短時間內(nèi)一定數(shù)量需求點運輸?shù)恼{(diào)度問題。隨著運輸系統(tǒng)的復(fù)雜化調(diào)度要求的多目標(biāo)化，要想獲得整個系統(tǒng)的精確最優(yōu)解則越來越困難，常常需要花費大量的時間和費用。因此，精確優(yōu)化方法及其簡化算法在實際應(yīng)用中范圍有限，現(xiàn)在常用于運輸調(diào)度的局部優(yōu)化中。車輛優(yōu)化調(diào)度問題的算法之精確算法一、分枝定界算法二、K度中心樹算法三