車(chē)輛調(diào)度之車(chē)輛調(diào)度問(wèn)題

物流人工智能技術(shù)技能培訓(xùn)項(xiàng)目三人工智能算法在配送環(huán)節(jié)應(yīng)用任務(wù)七車(chē)輛調(diào)度之車(chē)輛調(diào)度問(wèn)題目錄CONTENTS車(chē)輛調(diào)度的優(yōu)化目標(biāo)PART1配送車(chē)輛優(yōu)化調(diào)度的模型PART2車(chē)輛調(diào)度問(wèn)題算法的分類(lèi)PART3智能算法在物流配送車(chē)輛路徑問(wèn)題中的應(yīng)用PART4【教學(xué)目標(biāo)】過(guò)程與方法：知識(shí)與技能：1.掌握車(chē)輛調(diào)度的優(yōu)化目標(biāo)；2.了解配送車(chē)輛優(yōu)化調(diào)度的模型；3.熟悉車(chē)輛調(diào)度問(wèn)題算法的分類(lèi)。在學(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ì)主義制度。車(chē)輛調(diào)度問(wèn)題：根據(jù)發(fā)貨點(diǎn)以及接收點(diǎn)，組織適當(dāng)?shù)倪\(yùn)輸路線，當(dāng)車(chē)輛到達(dá)目的地時(shí)，它可以滿(mǎn)足規(guī)定的限制，又能達(dá)到最終目標(biāo)（如最短的配送距離、最少的配送車(chē)輛數(shù)量、最低的配送價(jià)格、最低的勞動(dòng)消耗、最短的花費(fèi)時(shí)間等）。車(chē)輛調(diào)度問(wèn)題（VRP）由Dantzig和Ramser首次提出后，便引起了運(yùn)籌學(xué)、數(shù)學(xué)、計(jì)算機(jī)等各大領(lǐng)域?qū)W者的極大重視。建立合理的配送方案可以有效縮短物流配送過(guò)程中的交貨時(shí)間，大大提高配送效率以及經(jīng)濟(jì)效益，因此，車(chē)輛調(diào)度問(wèn)題的研究對(duì)降低物流配送成本、實(shí)現(xiàn)合理的物流管理具有重要作用。一、車(chē)輛調(diào)度的優(yōu)化目標(biāo)車(chē)輛調(diào)度問(wèn)題是在滿(mǎn)足一定約束條件下，選擇某種目標(biāo)作為優(yōu)化目標(biāo)，實(shí)現(xiàn)總配送成本（廣義的配送成本，如配送時(shí)間、總費(fèi)用、需要車(chē)輛等）最優(yōu)。其中總配送成本一般表現(xiàn)為最小化總費(fèi)用，即車(chē)輛完成配送任務(wù)的各項(xiàng)費(fèi)用之和最小，如車(chē)輛啟用固定費(fèi)用、車(chē)輛行駛費(fèi)用、車(chē)輛等待費(fèi)用、車(chē)輛服務(wù)費(fèi)用、車(chē)輛懲罰費(fèi)用等；最小所需車(chē)輛數(shù)即完成全部配送任務(wù)所需總車(chē)輛數(shù)最??；最小總距離即完成全部配送任務(wù)車(chē)輛路徑總長(zhǎng)度最小；最短服務(wù)時(shí)間即完成全部配送任務(wù)總配送時(shí)間最小，配送時(shí)間一般包括車(chē)輛行駛時(shí)間、等待時(shí)間、服務(wù)時(shí)間和延誤時(shí)間等。二、配送車(chē)輛優(yōu)化調(diào)度的模型通過(guò)建立數(shù)學(xué)模型來(lái)定量研究物流配送成本的方法，目前可以歸納為三類(lèi)：物流配送車(chē)輛調(diào)度問(wèn)題數(shù)學(xué)模型可描述為：車(chē)輛由配送中心發(fā)出，對(duì)每一個(gè)客戶(hù)按照時(shí)間或其它要求配送到，車(chē)輛完成配送后返回配送中心，規(guī)定每個(gè)客戶(hù)只能由一輛車(chē)對(duì)其進(jìn)行服務(wù)且只服務(wù)一次，要求在滿(mǎn)足約束條件（如載重約束、時(shí)間約束、里程約束等）下對(duì)車(chē)輛行駛路徑進(jìn)行優(yōu)化，使完成配送的優(yōu)化目標(biāo)（成本、路程、車(chē)輛數(shù)等）最小。物流車(chē)輛調(diào)度問(wèn)題的數(shù)學(xué)模型是目標(biāo)規(guī)劃模型，其結(jié)構(gòu)特征一般為：minormaxz=f(x)物資流模型集覆蓋模型車(chē)輛流模型2.1有載重約束的車(chē)輛調(diào)度模型車(chē)輛調(diào)度問(wèn)題根據(jù)載貨任務(wù)情況可分為非滿(mǎn)載車(chē)輛調(diào)度問(wèn)題以及滿(mǎn)載車(chē)輛調(diào)度問(wèn)題。非滿(mǎn)載車(chē)輛調(diào)度問(wèn)題要求每個(gè)客戶(hù)需求量少于車(chē)輛載重量，一輛車(chē)能夠同時(shí)給一個(gè)或多個(gè)客戶(hù)運(yùn)送貨物。大多數(shù)時(shí)候一次任務(wù)不能恰好裝滿(mǎn)整車(chē)，這往往造成車(chē)輛裝載率不高。滿(mǎn)載車(chē)輛調(diào)度問(wèn)題中，客戶(hù)需求不小于車(chē)輛載重量，完成每次任務(wù)都需要滿(mǎn)載行駛，配送過(guò)程需要多輛車(chē)滿(mǎn)載，存在著最后一輛車(chē)非滿(mǎn)載的情況。目前，對(duì)于車(chē)輛調(diào)度問(wèn)題的研究以非滿(mǎn)載車(chē)輛調(diào)度問(wèn)題為主。首先，給出決策變量：二、配送車(chē)輛優(yōu)化調(diào)度的模型下面對(duì)非滿(mǎn)載車(chē)輛調(diào)度問(wèn)題建立車(chē)輛調(diào)度模型。其中：F為車(chē)輛固定費(fèi)用，m為車(chē)輛數(shù)，cijk為單位里程成本，dij為客戶(hù)i到客戶(hù)j的距離，qi為客戶(hù)需求量，Q為車(chē)輛載重量，Lk為車(chē)輛最大行駛距離；式（2）是載重約束，式（3）是每個(gè)需求客戶(hù)由一輛車(chē)來(lái)完成，式（4）是車(chē)輛最大行駛距離限制，式（5）表示每個(gè)客戶(hù)都能得到車(chē)輛的配送任務(wù)，式（6）、式（7）表示兩個(gè)變量之間的關(guān)系，式（8）、式（9）表示決策變量為0-1約束。（1）（2）（3）（4）（5）（6）（7）（8）（9）二、配送車(chē)輛優(yōu)化調(diào)度的模型2.2有時(shí)間約束的車(chē)輛調(diào)度模型時(shí)間約束問(wèn)題可分為硬時(shí)間窗約束、軟時(shí)間窗約束、混合時(shí)間窗約束三種。硬時(shí)間窗問(wèn)題懲罰函數(shù)設(shè)置：車(chē)輛必須在[ei，li]時(shí)間內(nèi)到達(dá)，否則給予其較大懲罰值M。下面建立帶硬時(shí)間窗約束的車(chē)輛調(diào)度模型需添加時(shí)間窗約束方程式：其中：ti為配送車(chē)輛到達(dá)客戶(hù)i的時(shí)間，Ti為在客戶(hù)i處裝卸貨所耗費(fèi)的時(shí)間，tij表示車(chē)輛從i到j(luò)所用的時(shí)間，T為一足夠大的常數(shù)。（10）（11）（12）二、配送車(chē)輛優(yōu)化調(diào)度的模型三、車(chē)輛調(diào)度問(wèn)題算法的分類(lèi)依據(jù)求解VRP問(wèn)題方法的不同，將算法分為兩大類(lèi)，分別是：?jiǎn)l(fā)式算法精確算法分枝定界法割平面法網(wǎng)絡(luò)流算法動(dòng)態(tài)規(guī)劃法啟發(fā)式算法三大類(lèi)經(jīng)典算法構(gòu)造型啟發(fā)算法插入算法節(jié)約算法改進(jìn)型啟發(fā)算法Petal算法Sweep算法人工智能算法遺傳算法GA蟻群優(yōu)化算法表1啟發(fā)式算法分類(lèi)四、智能算法在物流配送車(chē)輛路徑問(wèn)題中的應(yīng)用（1）混合遺傳算法1)量子遺傳算法2)遺傳算法與模擬退火算法結(jié)合（2）混合粒子群算法1)量子粒子群混合算法2)粒子群算法與模擬退火算法（3）混和蟻群算法1）量子蟻群算法2）蟻群算法與粒子群算法結(jié)合【課后小結(jié)】車(chē)輛調(diào)度問(wèn)題車(chē)輛調(diào)度的優(yōu)化目標(biāo)車(chē)輛調(diào)度問(wèn)題是在滿(mǎn)足一定約束條件下，選擇某種目標(biāo)作為優(yōu)化目標(biāo)，實(shí)現(xiàn)總配送成本最優(yōu)。配送車(chē)輛優(yōu)化調(diào)度的模型1.有載重約束的車(chē)輛調(diào)度模型2