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

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

1成品油配送車輛調度數學模型

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

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

2求解算法

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

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

3應用改進遺傳算法求解某成品油配送公司車輛調度問題

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

4總結與展望

本文針對成品油配送中車輛調度問題的約束條件進行分析，建立了多車型—多油品—多加油站的成品油配送車輛調度模型，在模型基礎上設計改進遺傳算法對車輛調度問題進行求解，其中，對算法中的染色體結構，選擇操作，交叉操作等進行了改進。最后，通過具體案例驗證了模型與算法的有效性。

作者：楊渝華李敏單位：西南交通大學交通運輸與物流學院