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

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