【文章內(nèi)容簡介】 到達(dá)客戶 i 并且開始服務(wù)的時間是 ti,行駛時間是 ijt , wi 為所需的等待時間 ,Si 為服務(wù)時間 , iit? 表示客戶滿意度 ,I是很大的整數(shù)。定義變量 : ki 1 iky= 0??? 客 戶 由 車 輛 配 送否 則 mkij 1 m k i jx= 0??? 車 場 的 車 從 用 戶 行 駛 到否 則 基于顧客的滿意程度可得求解目標(biāo)有 : 第一步是最大化的平均客戶滿意度 : Niii=11max tN ?? (式 213) 其可以等價轉(zhuǎn)化為最小化的平均客戶不滿意度 Niii= 11min 1 tN ????????? （式 214) 第二步是最小化的車輛數(shù) : KN k0jk=1 j=1min x?? (式 215) 第三步是最小化的車輛行駛距離和等待時間 : 11 / 40 K N N kij ijk=0 i=1 j=1min c x??? (式 216) Niii=1min t?? (式 217) 其有如下的約束條件 : iit i??? i = l,2… N (式 218) 1N ki i ki g y q? ?? (式 219) 1 1K kik y? ?? (式 220) 1N kkij ji xy? ?? (式 221) 1N kkij ij xy? ?? (式 222) , 1n kiji j s s xs?? ??? ? ? 1,2...sN? (式 223) ? ?m ax ,j j i i ijt E t s t? ? ? (式 224) ijtN? (式 225) ? ?( ) m ax 0,i j j jt t E? ?? (式 226) 以上公式中 ,公式 (218)可以保障每個客戶滿意程度不低于 i? 其中 i? 是決策者根據(jù)自身的實際經(jīng)驗給出相應(yīng)的值 ,其中給每個客戶的值可以相同也可以不同 ,其是根據(jù)客戶的重要程度進(jìn)行劃分的。公式 (219)用來保證每輛車的承載能力。公式 (220)用來確保每個客戶都被服務(wù)到。公式 (221)(222)確保每個客戶只被一輛車服務(wù) .公式 (223)用來消除子回路。公式 (224)、 (225)、 (226)用來確保客戶在確定時間窗內(nèi)接受服務(wù)。 模型建立思路總結(jié) 根據(jù)前文介紹的幾種模型 ,總結(jié)出對于物流配送路徑問題建模的大致思路 首先 ,自定義變量。大多是 amp。和 7,對所求變量進(jìn)行初始條件設(shè)置 ,即變量為 1 時則為服務(wù)到 ,變量為 0則為未服務(wù)到。如 : ki 1 iky= 0??? 客 戶 由 車 輛 配 送否 則 12 / 40 mkij 1 m k i jx= 0??? 車 場 的 車 從 用 戶 行 駛 到否 則 第二步 ,設(shè)定最小化目標(biāo)。如最小化的費用、最小化的時間或者最小化的路徑。如 : K N N Kij ijK = 0 i= 1 j= 1m in Z= c x? ? ? 第三步 ,自定義滿足條件。如顧客滿意度、車輛分配總數(shù)或運(yùn)輸時間等。如 : Niii=11max tN ?? 第四步 ,保證每個客戶都被服務(wù)到。如 :1 1K kik y? ?? 第五步 ,保證每個客戶都被服務(wù)一次。有時候第四步和第五步可以合并。如 : 1N kkij ji xy? ?? 第六步 ,保證消除子回路。如 : , 1n kiji j s s xs?? ??? ? ? 1,2...sN? 第七步 ,保證車輛的承載能力。如 : 1N ki i ki g y q? ?? 對于模型思路和每一種約束條件的分析與總結(jié)十分必要 ,利于根據(jù)實際要求建立對應(yīng)的所需模型 ,并根據(jù)自身的要求加入相應(yīng)的約束條件 ,改進(jìn)模型 ,使模型更加貼合實際要求。 基于最短路徑的多車場多車輛配送模型建立 根據(jù)前文對于模型建立的分析與總結(jié) ,運(yùn)用前文的方法 ,建立一種基于最短路徑的多車場多車輛的配送模型 ,并加入新的約束條件。 配送路徑中多個車場多個車輛的優(yōu)化問題可以描述為 :某物流中心一共有 M 個車場 ,各自有 Ki(K1, K2 Km)臺配送車輛 ,每輛車容量都為 q,向 N 個客戶送貨 ,用戶 i 的貨物需求為 gi, (i=l,2,...N)。要求合理安排車輛配送方案 ,使車輛總運(yùn)輸成本最低 ,并滿足以下條件 :(1)每輛車運(yùn)送完后必須返回原車場 。(2)每個客戶的需求必須滿足 。(3)可以由任意一個車場的車輛服務(wù) ,但只能由一臺配送車輛送貨 。(4)對車輛的服務(wù)數(shù)量進(jìn)行限制。 根據(jù)以上條件 ,設(shè)全部用戶的編號分別為 1,2, ......N。車場具有編號為N+l,N+2, ......N+M。定義變量 mkij 1 m k i jx= 0??? 車 場 的 車 從 用 戶 行 駛 到否 則 (式 227) N:表示客戶的總數(shù)目 。 M:表示車場的總數(shù)目 。 dij:表示節(jié)點 i與節(jié)點 j之間的距離 。 km:表示車場 m所擁有的車輛總數(shù) 。 gi:表示客戶 i的要求 。 q:車場 m中車輛 k載重負(fù)荷。 以上可以建立數(shù)學(xué)模型如下 : 13 / 40 1 1 1 1m inN N M K m mkij iji j m kZ d x? ? ? ?? ???? (式 228) 公式 228用來保證最小化的車輛行駛路徑。也是整個問題的核心需求 ,是下 步工作運(yùn)用算法所需要完成的內(nèi)容 ,即適應(yīng)值。接下來就要根據(jù)實際要求對運(yùn)算加以限制 ,列出限制公式 ,以便于計算 ,獲得與實際 相符的可行解。 11N Km mkijikx Km?? ??? ? ?1, 2. ..m N N N M? ? ? ? (式 229) 條件 229限制了從一個車場出發(fā)的車輛總數(shù)目 ,必須小于 !^。此條件用于限制計算時車輛的數(shù)量 ,因為一個車場所含有的車輛數(shù)是固定的 ,因此必須加以限制。 , 1n mkiji j s s xs?? ??? ? ?1,2...sN? ? ?1,2...k Km? (式 230) 公式 230保證了消除子回路。即不能出現(xiàn)路徑反復(fù) ,出現(xiàn)誤差。 1 1 1 1N M Km mkiji m k x? ? ? ???? ? ?1,2...iN? (式 231) 1 1 1 1N M Km mkijj m k x? ? ? ???? ? ?1,2...jN? (式 232) 條件 231和 232保證了每個客戶僅被一輛車服務(wù)一次。該公式的目的是控制每個客戶都被服務(wù)到 ,并且僅被一輛車服務(wù)。 11N N M mki xjijg x q??? ??? ? ?1, 2. ..m N N N M? ? ? ? ? ?1,2...k Km? (式 233) 公式 233表示每輛車的載重量不超過它的載重能力。由于每輛車的承載能力是固定的 ,因此必須對車輛總承載數(shù)加以控制。 同時在前文研究的基礎(chǔ)上發(fā)現(xiàn) ,大部分的約束條件都是從客戶的角度出發(fā) ,要求每個客戶都被服務(wù)到 ,每個客戶都被一輛車服務(wù) ,但是如果車輛所經(jīng)過的客戶過多 ,就會對車輛的行駛里程產(chǎn)生一定要求 ,車輛行駛的距離與車輛狀態(tài)、儲油量和車輛使用年限等都有一系列的關(guān)系 ,對車輛要求很高 ,而車輛本身具有一定的局限性 ,基于以上原因 ,本文從車輛行駛里程考慮 ,對車輛服務(wù)客戶數(shù)量加以限制 ,加入了新的約束條件 ,如公式 234所示 : 11nnmkijijxR?? ??? ? ?1,2...iN? ? ?1,2...jN? (式 234) 對于第 mk車輛 ,它所經(jīng)歷的客戶總數(shù)量控制在 R以下 ,即最多為 R客戶服務(wù) ,這樣可以保證車輛的客戶服務(wù)數(shù) ,同時也能在一定的范圍內(nèi)對車輛行駛里程加以限制 ,確保車輛正常行駛并能將貨物送達(dá)每一個客戶。 根據(jù)本章對物流配送路徑模型定義、分類的研究 ,了解物流配送問題建模的內(nèi)容與意義。本章中選擇三種常見的模型進(jìn)行分析 ,分別是基于行駛距離最短和使用車輛最少的物流配送模型、基于開放式車輛路徑的物流配送模型和基 于顧客滿意度的物流配送模型 ,對模型進(jìn)行深入研究 ,并總結(jié)建立模型的相關(guān)思路。根據(jù)實際情況建立了一種基于最短路徑的多車場多車輛的物流配送模型 ,并從車輛行駛里程角度分析加入了新的約束條件 ,保證車輛的正常行 14 / 40 駛 ,同時也保證車輛能將貨物送達(dá)每一位客戶。 3物流配送路徑問題相關(guān)算法研究 物流配送算法主要的解決方案分為兩大類 :人工智能算法和精確算法。 人工智能算法包括有 :掃描法、旅行商方法、分區(qū)配送算法、節(jié)約法以及一些現(xiàn)代優(yōu)化計算方法 (禁忌搜索算法、遺傳算法、模擬退火算法等 )。人工智能算法雖然比精確算法精度低 ,但在求解大規(guī) 模 VRP 時 ,總可以求解 ,找到滿意的可行解或次優(yōu)解 ,這是精確算法無法做到的。因此 ,人工智能算法更廣泛的運(yùn)用在實際生活中。 精確算法可以這樣劃分 :直接樹搜索算法、割平面法、分枝定界法、網(wǎng)絡(luò)流算法、整數(shù)線性規(guī)劃和動態(tài)規(guī)劃法?？偟膩碚f ,精確算需要十分嚴(yán)格的數(shù)學(xué)手段 ,所以在可以求解的情況下 ,其解要比人工智能算法更加優(yōu)良。但由于需要嚴(yán)格的數(shù)學(xué)方法 ,因而無法避開指數(shù)過多問題 ,所以該類算法有限制性 ,對于小規(guī)模的確定性 VRP才能有效求解。 (1)精確算法 精確算法指可求出最優(yōu)解的算法 ,主要 有分枝定界法、割平面法、網(wǎng)絡(luò)流算法、動態(tài)規(guī)劃法等。精確算法的計算量一般隨著問題規(guī)模的增大而呈指數(shù)增長 ,所以 ,多用于規(guī)模較小的問題。 (2)啟發(fā)式算法 通常情況下 ,通過自身發(fā)展的性質(zhì)和生物系統(tǒng) ,可以使許多復(fù)雜的問題得到令人滿意的解決方案 ,計算機(jī)科學(xué)家從生物系統(tǒng)的研究中得到的靈感 ,、以模仿自然的世界 ,獲取新的方法來解決復(fù)雜的計算問題。在算法的設(shè)計過程中 ,設(shè)計靈感起源于或者是物理現(xiàn)象 ,或者是生物群體現(xiàn)象。如模擬退火算法模擬的固體物質(zhì)從高溫度的不穩(wěn)定狀態(tài)的過程中向低溫度穩(wěn)定狀態(tài)過度 。遺傳算法從大自然的優(yōu)勝劣汰的生存 現(xiàn)象中獲得 。蟻群算法模仿蟻群覓食的費洛蒙應(yīng)用 ,以便找到最短的覓食路徑。這些智能的優(yōu)化算法的出現(xiàn) ,一方面極大地豐富了優(yōu)化技術(shù) ,為那些傳統(tǒng)的優(yōu)化技術(shù)無法處理的組合優(yōu)化問題提供了一個實用的解決方案 ,另一方面 ,他們也從另一個角度來探討生物世界的機(jī)制為實際運(yùn)用提供新的工具和技術(shù)。 雖然這些新的方法進(jìn)行了優(yōu)化 ,并且每個機(jī)制是不一樣的 ,但它們有類似的特征。他們都是迭代算法 ,通過在不斷的迭代計算 ,一步一步從質(zhì)量差的解決方案 ,以更優(yōu)質(zhì)的解決方案逼近。因此 ,這些算法在多篇論文或其他著作被列為一類 ,概括起來 ,即啟發(fā)式算法一一 Heuristic Algorithm。啟發(fā)式算法 ,是一種定義在可以接受的花費 (占用空間、計算時間等 )下解決組合優(yōu)化問題的一個可行的解決方案 ,這種解決方案與最佳方案水平偏差不可預(yù)知。另一種定義指定啟發(fā)式算法是一種技術(shù) ,使尋找最佳的解決方案在一個可接受的計算成本內(nèi) ,但不一定保證得到的解決方案是可行的和最優(yōu)的 ,或者