路線規(guī)劃之車(chē)輛路徑規(guī)劃問(wèn)題

物流人工智能技術(shù)技能培訓(xùn)項(xiàng)目三人工智能算法在配送環(huán)節(jié)應(yīng)用任務(wù)一路線規(guī)劃之車(chē)輛路徑規(guī)劃問(wèn)題目錄CONTENTS收發(fā)貨車(chē)輛路徑規(guī)劃模型PART1車(chē)輛路徑問(wèn)題求解方法PART2【教學(xué)目標(biāo)】過(guò)程與方法：知識(shí)與技能：1.掌握收發(fā)貨車(chē)輛路徑規(guī)劃模型；2.掌握車(chē)輛路徑問(wèn)題求解方法。在學(xué)習(xí)動(dòng)畫(huà)視頻的過(guò)程中，理解其基本工作原理，了解其實(shí)際應(yīng)用價(jià)值。情感、態(tài)度與價(jià)值觀：1.提升對(duì)人工智能的認(rèn)識(shí)，發(fā)展辯證思維，客觀認(rèn)識(shí)人工智能技術(shù)對(duì)社會(huì)的影響，培養(yǎng)正確的科學(xué)技術(shù)應(yīng)用觀。2.堅(jiān)定擁護(hù)中國(guó)共產(chǎn)黨領(lǐng)導(dǎo)和我國(guó)社會(huì)主義制度。一、收發(fā)貨車(chē)輛路徑規(guī)劃模型收發(fā)貨車(chē)輛路徑規(guī)劃可以劃分為需求可拆分問(wèn)題、?對(duì)多對(duì)?的收發(fā)貨問(wèn)題、一對(duì)一的收發(fā)貨問(wèn)題、多對(duì)多的收發(fā)貨問(wèn)題等多種變體。收發(fā)貨車(chē)輛路徑規(guī)劃需求可拆分問(wèn)題?對(duì)多對(duì)?的收發(fā)貨問(wèn)題一對(duì)一的收發(fā)貨問(wèn)題多對(duì)多的收發(fā)貨問(wèn)題設(shè)有頂點(diǎn)集合V={v0,v1,...,vn}，其中v0表示倉(cāng)庫(kù)，其他頂點(diǎn)為客戶；車(chē)輛可以定義為K={1,2,...,m}，pi為第i個(gè)客戶的需求，Qk表示第k輛車(chē)的容量，cijk表示第k輛車(chē)的路徑rk上頂點(diǎn)vi和vj之間的距離。兩個(gè)頂點(diǎn)之間如果連接起來(lái)，則表示車(chē)輛可以行走。故兩點(diǎn)間的路徑可以定義為：一、收發(fā)貨車(chē)輛路徑規(guī)劃模型其中約束條件為：公式(2.1)為模型的目標(biāo)函數(shù)，表示車(chē)輛行駛的最小路徑長(zhǎng)度。約束式(2.2)和(2.3)確保每個(gè)客戶點(diǎn)只能由一輛車(chē)進(jìn)行一次服務(wù)，公式(2.4)表示路線通路是雙向的即表示形成的圖為強(qiáng)連通圖，公式(2.5)則表示車(chē)輛的容量約束，公式(2.6)表示每條路徑只能有一個(gè)起點(diǎn)，也表示車(chē)輛只能使用一次。一般的收發(fā)貨車(chē)輛路徑規(guī)劃問(wèn)題模型為：（2.1）（2.2）（2.3）（2.4）（2.5）（2.6）一、收發(fā)貨車(chē)輛路徑規(guī)劃模型二、車(chē)輛路徑問(wèn)題求解方法帶容量約束的車(chē)輛路徑規(guī)劃（CVRP）帶收發(fā)貨的車(chē)輛路徑規(guī)劃（PDVRP）帶時(shí)間窗的路徑規(guī)劃問(wèn)題（VRPTW）多路徑車(chē)輛規(guī)劃問(wèn)題（VRPMT）1.2.3.4.龐大的問(wèn)題族，包括：精確求解法是基于嚴(yán)格的數(shù)學(xué)理論進(jìn)行求解的，所得的結(jié)果為理論上的最優(yōu)解。其中精確求解法主要包括分支界限、整數(shù)線性規(guī)劃和動(dòng)態(tài)規(guī)劃方法?；谥庇^或經(jīng)驗(yàn)構(gòu)造，在可接受的花費(fèi)（指計(jì)算時(shí)間和空間）下給出待求解的組合優(yōu)化問(wèn)題的解，雖然不能保證?定得到最優(yōu)解，但是可以保證在有限的時(shí)間內(nèi)獲得良好的折中解。A精確求解法B啟發(fā)式求解法二、車(chē)輛路徑問(wèn)題求解方法【課后小結(jié)】車(chē)輛路徑規(guī)劃問(wèn)題收發(fā)貨車(chē)輛路徑規(guī)劃模型收發(fā)貨車(chē)輛路徑規(guī)劃可以劃分為需求可拆分問(wèn)題、?對(duì)多對(duì)?的收發(fā)貨問(wèn)題、一對(duì)一的收發(fā)貨問(wèn)題、多對(duì)