本站小編為你精心準(zhǔn)備了成品油配送車輛調(diào)度研究參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫(xiě)作靈感。歡迎深入閱讀并收藏。

《物流科技雜志》2015年第一期

1成品油配送車輛調(diào)度數(shù)學(xué)模型

1.1問(wèn)題描述在配送網(wǎng)絡(luò)中，多車型成品油配送VSP可以描述為：配送網(wǎng)絡(luò)中共有K種成品油配送任務(wù)，有N個(gè)加油站，其中第n個(gè)加油站對(duì)k類成油品的需求量為gnkk=1,2,…,K;n=0,1,2,…,,,N配送中心共有S輛不同車型的油罐車可提供配送任務(wù)，共有R種車型，某些車型的油罐車可以進(jìn)行多油品分隔裝載，其中車型為r的油罐車油品k的最大載重量為qrkk=1,2,…,K;r=1,2,…,,,R。假設(shè)所有進(jìn)行配送運(yùn)輸任務(wù)的油罐車都由配送中心出發(fā)，首先到油庫(kù)完成油品裝載，然后完成成品油配送任務(wù)，完成所有任務(wù)后返回至配送中心，按油罐車行駛過(guò)程中的起始節(jié)點(diǎn)來(lái)劃分，可以將運(yùn)輸路線分為以下三類：（1）由配送中心行駛至加油站；（2）由加油站行駛至加油站；（3）由加油站行駛至配送中心。

1.2成品油配送車輛調(diào)度模型整個(gè)動(dòng)態(tài)配送網(wǎng)絡(luò)記為Net，由M表示加油站集合，K表示油品型號(hào)集合，S表示所有油罐車組成的集合，R表示油罐車車型集合，r∈R的車廂分為多個(gè)容量不等的固定艙位，由它們組成的集合記為H,R,；cijk表示由節(jié)點(diǎn)i到節(jié)點(diǎn)j的品種k的成品油運(yùn)輸成本，其含義可以是距離、費(fèi)用、時(shí)間等；記油罐車空載時(shí)的單位距離油耗成本為e1，滿載時(shí)油耗成本為e2；設(shè)油罐車的實(shí)載重量為q，則其載重率為pi=q/Qrk（Qrk為車型為r的油罐車油品k的最大載重量），則該車型油罐車的單位油耗成本為：ei''''=e1+pie2-e1,,。則油罐車的油耗成本為運(yùn)輸距離與ei''''的乘積。由此，建立多車型—多油品—多加油站的成品油配送車輛調(diào)度VSP數(shù)學(xué)模型如下：首先給出決策變量：其中，Z表示調(diào)度任務(wù)的總成本；Frs表示車輛的固定行駛費(fèi)用，包括人力成本、車輛行駛固定成本、油庫(kù)內(nèi)物流附加費(fèi)等，以及在1.1節(jié)中簡(jiǎn)化的從配送中心至油庫(kù)的運(yùn)輸成本；N為加油站個(gè)數(shù)；K為配送區(qū)域內(nèi)油品種類數(shù)量；S為可用油罐車個(gè)數(shù)；R為油罐車車型種類數(shù)量；Qrk表示油罐車車型r的油品k最大載重量；L為加油站配送任務(wù)個(gè)數(shù)，即油罐車需要服務(wù)的加油站個(gè)數(shù)；cijk表示兩節(jié)點(diǎn)間油品k的配送成本；ei''''為油罐車的單位油耗成本；其中編號(hào)為0的加油站表示配送中心。在公式（1）中，表示調(diào)度總成本最小的優(yōu)化目標(biāo)；公式（2）表示車輛s的配送任務(wù)中第k種油的配送總量不能超過(guò)該油罐車對(duì)應(yīng)艙位的載重量；公式（3）表示每個(gè)加油站的每一種油品的配送需求都需要有油罐車對(duì)其進(jìn)行服務(wù)；公式（4）、（5）表示兩個(gè)變量之間的關(guān)系，表示節(jié)點(diǎn)所有油品配送需求總和間的關(guān)系；公式（6）表示車輛由配送中心出發(fā)，并且最終回到配送中心；公式（7）表示油罐車所完成的配送油品總數(shù)大于配送任務(wù)數(shù)，即油罐車對(duì)加油站的一次配送任務(wù)應(yīng)盡可能完成對(duì)多種油品的配送；公式（8）表示從配送中心共發(fā)出S輛油罐車；公式（9）、（10）表示變量的0～1約束；公式（11）用于消除配送路徑中的回路；公式（12）、（13）為變量的取值范圍。

2求解算法

目前，對(duì)車輛調(diào)度問(wèn)題的求解算法，國(guó)內(nèi)外相關(guān)文獻(xiàn)主要分為兩類：精確算法和啟發(fā)式算法，對(duì)于簡(jiǎn)單的小規(guī)模車輛調(diào)度問(wèn)題主要采用精確算法，大規(guī)模的車輛調(diào)度問(wèn)題，由于車輛調(diào)度問(wèn)題的限制條件較多，大多采用啟發(fā)式算法求得次優(yōu)解。成品油配送中的車輛調(diào)度路徑問(wèn)題除了具有一般VSP問(wèn)題求解的復(fù)雜性之外，還具有油品配送過(guò)程中的復(fù)雜性特征，包括多車型、多商品、多艙位、滿艙配載要求、運(yùn)載負(fù)荷量平衡等約束條件，由此，本文通過(guò)啟發(fā)式算法尋求可行解。通過(guò)對(duì)現(xiàn)有文獻(xiàn)的總結(jié)分析，使用較多的啟發(fā)式算法為遺傳算法。文獻(xiàn)[2]、[4-5]建立了車輛調(diào)度問(wèn)題的數(shù)學(xué)模型并利用遺傳算法進(jìn)行了求解；文獻(xiàn)[6]建立車輛調(diào)度動(dòng)態(tài)模型，并利用改進(jìn)的遺傳算法對(duì)問(wèn)題進(jìn)行了求解。本文通過(guò)對(duì)遺傳算法的編碼結(jié)構(gòu)、交叉和變異操作方式進(jìn)行改進(jìn)來(lái)對(duì)所建立的數(shù)據(jù)模型進(jìn)行求解。

（1）染色體的編碼設(shè)計(jì)。由于成品油車輛調(diào)度問(wèn)題解的特殊結(jié)構(gòu)，本文直接用自然數(shù)序列作為染色體的編碼。由N個(gè)加油站構(gòu)成的配送網(wǎng)絡(luò)需要S輛油罐車進(jìn)行配送的問(wèn)題，可以用一條長(zhǎng)為N+S+1的染色體編碼，其中N個(gè)自然數(shù)從1至N進(jìn)行全排列，其數(shù)值表示加油站序號(hào)，在染色體中的位置表示被服務(wù)的次序；同時(shí)，S+1個(gè)0表示S輛車從配送中心出發(fā)最后回到配送中心。0,i1,i2…,ie,0,if…,ik,0,ip,…,iq,,0,，其中ij表示第j個(gè)加油站，0表示配送中心，其中有三條子路，配送中心首先派出第一輛油罐車按i1,i2,…,ie的順序?qū)個(gè)加油站進(jìn)行服務(wù)，完成后回到配送中心，形成第一條回路；第二輛油罐車也由配送中心出發(fā)，按if,…,ik對(duì)加油站完成服務(wù)后回到配送中心形成第二條回路；第三條回路也是同理。所設(shè)計(jì)的染色體具有子路間無(wú)序，子路內(nèi)有序的特點(diǎn)；同時(shí)，為了表示每條子路徑在完成配送任務(wù)時(shí)具體使用的車型和艙位，則引入了一個(gè)輔助隊(duì)列用于存儲(chǔ)配送油罐車的車型、艙位和載重量，并按染色體中子路徑的服務(wù)順序依次存放。這樣的編碼方式可以很方便的得到某個(gè)加油站服務(wù)的油罐車具體信息，同時(shí)在執(zhí)行遺傳算子時(shí)，僅對(duì)染色體本身進(jìn)行遺傳操作，其對(duì)應(yīng)的輔助隊(duì)列只需相應(yīng)調(diào)整即可，能夠有效增強(qiáng)算法的收斂性從而縮短求解時(shí)間[5]。（2）初始化種群。隨機(jī)產(chǎn)生N個(gè)加油站的序列0,i1,i2,…,ie,,0,，并在首尾插入0，表示油罐車由配送中心出發(fā)，最后回到配送中心。如10個(gè)加油站的配送網(wǎng)絡(luò)，,0,3,2,8,5,4,1,6,9,7,10,0,，同時(shí)初始化輔助隊(duì)列，假設(shè)配送中心有5種車型，每個(gè)車型有h個(gè)艙位，以第一個(gè)進(jìn)行配送的3號(hào)加油站為例，則在輔助隊(duì)列中存放如,2,3,,2,3,,,2,3.5,,表示配送中心派出車型為3的2號(hào)油罐車用2號(hào)艙位2噸，3號(hào)艙位3.5噸對(duì)3號(hào)加油站進(jìn)行配送。（3）適應(yīng)度函數(shù)。成品油車輛調(diào)度問(wèn)題是一最小化組合優(yōu)化問(wèn)題，其目標(biāo)是運(yùn)輸總成本費(fèi)用最小，由此，可以直接取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。（4）選擇操作。利用（3）中的適應(yīng)度函數(shù)計(jì)算種群中個(gè)體的適應(yīng)值，根據(jù)適應(yīng)值的大小對(duì)其進(jìn)行排序，則規(guī)模為P的種群，記最小適應(yīng)度值個(gè)體為0，最大適應(yīng)度個(gè)體為P-1。在標(biāo)準(zhǔn)正態(tài)分布中，99.9%的隨機(jī)數(shù)r分布在≤-3,3≤之間，此時(shí)，取r*=r3且-3≤r≤3，則t=r**P-,,1，則選取第t號(hào)染色體進(jìn)入新種群，由此適應(yīng)度值越靠近0的染色體被選取的概率越大，則選取較優(yōu)染色體的可能性越高[6]。（5）交叉算子。由于車輛調(diào)度問(wèn)題解的特殊結(jié)構(gòu)，染色體編碼具有組間無(wú)序、組內(nèi)有序的特點(diǎn)，如果采用傳統(tǒng)的單點(diǎn)交叉、多點(diǎn)交叉等，組內(nèi)的優(yōu)良子串都可能被破壞，并且當(dāng)兩個(gè)父代個(gè)體相同時(shí)，無(wú)法產(chǎn)生新個(gè)體。本文結(jié)合油罐車車輛調(diào)度問(wèn)題編碼的特殊性，交叉點(diǎn)選擇配送中心位置，即編碼中0所在位置，以避免破壞優(yōu)秀子串，同時(shí)，在交叉時(shí)不是直接復(fù)制子串，而是將子串復(fù)制到染色體的首位，這樣可以最大限度對(duì)已生成子串進(jìn)行保護(hù)，同時(shí)也避免了在雙親相同時(shí)不能產(chǎn)生新個(gè)體的問(wèn)題，具體操作如下：①交叉復(fù)制。以概率p隨機(jī)選擇兩個(gè)染色體A和B，隨機(jī)在1,m之間產(chǎn)生兩個(gè)自然數(shù)r1和r2（其中m為染色體中的子線路個(gè)數(shù)），將A中的子路線r1復(fù)制到后代B*最前端，同時(shí)將B中的子路線r2復(fù)制到后代A*最前端，具體過(guò)程如圖2所示：本文在交叉操作過(guò)程中引入了交叉概率自適應(yīng)性的思想，在迭代求解過(guò)程中，不斷修正對(duì)算法性能起著決定作用的交叉概率,從而克服過(guò)早收斂和加快搜索速度。本文采用的自適應(yīng)交叉概率公式。式（1）中pcmax是最大交叉概率（本文取1.0）；pcmin是最小交叉概率（本文取0.2）；t是遺傳代數(shù)；T是最大遺傳代數(shù)。這種自適應(yīng)的生成方法使得在迭代初期，交叉概率較大并且下降緩慢，能夠?qū)θ旧w產(chǎn)生足夠大影響，增強(qiáng)算法的搜索能力，避免算法陷入遲鈍狀態(tài)，加快進(jìn)化速度；同時(shí)在迭代后期，交叉概率較低，并逐步減小，最后為一常量，這種方式避免破壞優(yōu)良基因，加快收斂速度，能夠增加搜索到全局最優(yōu)解的可能性。②逆轉(zhuǎn)操作。對(duì)使用基于路徑表示編碼的基因進(jìn)行交叉操作來(lái)VSP問(wèn)題時(shí)，如果單純使用傳統(tǒng)的交叉算子，則會(huì)使一些較優(yōu)的基因組合被破壞，使子代難以繼承父代的優(yōu)良基因，導(dǎo)致搜索能力降低。由此，本文采用逆轉(zhuǎn)算子代替交叉操作，即對(duì)沒(méi)有進(jìn)行交叉復(fù)制操作的表示車輛路徑的基因串順序進(jìn)行逆轉(zhuǎn)操作，以圖2中進(jìn)行交叉復(fù)制后的染色體為例，其過(guò)程如圖3所示。（6）變異操作。以交叉概率隨機(jī)選擇一個(gè)染色體，在1,N+S間隨機(jī)產(chǎn)生兩個(gè)自然數(shù)n1與n2，若n1與n2都對(duì)應(yīng)非0基因，則交換這兩個(gè)基因，否則重新產(chǎn)生新的自然數(shù)。（7）終止條件。設(shè)置重復(fù)迭代20次種群沒(méi)有變化，終止迭代過(guò)程，若未達(dá)到終止條件，轉(zhuǎn)（3），否則轉(zhuǎn)（8）。（8）輸出結(jié)果。將種群中適應(yīng)度值最優(yōu)的個(gè)體進(jìn)行輸出，并將其轉(zhuǎn)換為問(wèn)題的滿意解或最優(yōu)解。

3應(yīng)用改進(jìn)遺傳算法求解某成品油配送公司車輛調(diào)度問(wèn)題

設(shè)某成品油配送公司共有3種油罐車車型，其運(yùn)力能夠滿足加油站油品的配送需求，某日配送中心接到13個(gè)加油站配送油品配送訂單，共有2種不同的成品油類別，13個(gè)加油站之間的距離如表1所示（其中0號(hào)加油站表示配送中心），油品需求量如表2所示，油罐車油品最大載重量及固定成本如表3所示。表3中，油品種類與倉(cāng)位在一列中進(jìn)行表示，即1號(hào)倉(cāng)位裝載1號(hào)油品，2號(hào)倉(cāng)位裝載2號(hào)油品，油罐車使用的燃料以7.44元/L的柴油計(jì)算，并要求每個(gè)加油站只能進(jìn)行一次配送，應(yīng)用第3節(jié)提出的遺傳算法，使用自然數(shù)編碼，種群大小P設(shè)置為100，最大進(jìn)化代數(shù)T設(shè)置為120，參數(shù)設(shè)置如下：pcmax=1.0，pcmin=0.2，以進(jìn)化代數(shù)和適應(yīng)度為目標(biāo)進(jìn)行雙重判斷，其計(jì)算結(jié)果如表4所示。從表4運(yùn)行結(jié)果可以看出，方案2，3，7需要的油罐車數(shù)量較多，而油罐車固定成本在總成本中占較大比重，因?yàn)椋苯訉⒃撊齻€(gè)方案從備選方案中去除。通過(guò)對(duì)方案的總成本進(jìn)行詳細(xì)分析，如表5所示，以運(yùn)輸總成本為評(píng)選指標(biāo)，方案5為最佳調(diào)度方案，該方案具有最低運(yùn)輸成本，同時(shí)，行駛總距離最小。

4總結(jié)與展望

本文針對(duì)成品油配送中車輛調(diào)度問(wèn)題的約束條件進(jìn)行分析，建立了多車型—多油品—多加油站的成品油配送車輛調(diào)度模型，在模型基礎(chǔ)上設(shè)計(jì)改進(jìn)遺傳算法對(duì)車輛調(diào)度問(wèn)題進(jìn)行求解，其中，對(duì)算法中的染色體結(jié)構(gòu)，選擇操作，交叉操作等進(jìn)行了改進(jìn)。最后，通過(guò)具體案例驗(yàn)證了模型與算法的有效性。

作者：楊渝華李敏單位：西南交通大學(xué)交通運(yùn)輸與物流學(xué)院