路況條件物流配送途徑完善

1、路況條件物流配送途徑完善 1引言 在物流運輸和配送過程中，會出現(xiàn)由于交通事故、天氣變化、上下班等因素引起車輛行駛速度的改變，進而導(dǎo)致配送時間的變化。此時，各點間的運輸時間不能簡單地將其考慮為常數(shù)，而可以將其考慮為具有某種統(tǒng)計規(guī)律的隨機變量，服從一定的分布函數(shù)或經(jīng)驗概率，這就是帶隨機運輸時間的vrp。如，經(jīng)過長期的觀測，人們可以知道，某條路段是否常發(fā)生擁堵或交通事故，進而對車輛經(jīng)過改路段需要耗費的時間估算其概率；也可以通過配送中的數(shù)據(jù)積累或使用第三方的路況數(shù)據(jù)，得到路段的通行速度的概率相關(guān)信息。 2考慮路況條件的物流配送路徑優(yōu)化模型 本文選擇最短總行駛距離、最小化總的服務(wù)時間、最小化違法客戶時間

2、窗的懲罰值，作為物流配送路徑優(yōu)化問題的三大目標。 21模型前提條件 對于配送車輛路徑優(yōu)化問題，本文建立模型的前提條件假設(shè)如下：（1）所有車輛的行駛路線的開始和結(jié)束點都在配送中心。（2）模型中假定每個客戶的需求量都小于車輛裝載量，且每個客戶所需要貨物只能由一輛車提供；在實際工作中，當客戶需求量大于車輛裝載量時，先將客戶需求量減去除整車的裝載配送量，直至客戶需求量小于車輛裝載量時再參與模型的優(yōu)化。（3）假定所有車輛的最大裝載量為某一定值，且實際裝載率不超過100。（4）模型中假定每輛車只有一條行駛路線，視車輛返回配送中心后重復(fù)發(fā)車的情況為不同車輛；在實際工作中，可以依據(jù)車輛返回配送中心后重復(fù)發(fā)車的

3、情況，對實際所需的車輛數(shù)進行合并。（5）假定每個客戶都有指定的服務(wù)時間窗口，配送須盡可能地在此時間窗口范圍內(nèi)到達。（6）各客戶點的需求量在配送前為已知的定值。（7）配送車輛的行駛距離沒有約束。（8）每個客戶點的卸貨時間為某一定值。（9）假定每個客戶對早到或遲到的不滿意程度都符合相同的線性函數(shù)關(guān)系。（10）假定路況條件服從一定的概率分布，即路段的通行時間在配送前是已知的概率信息。 22模型參數(shù)設(shè)置 （1）決策變量的定義：xijkyikxijk1代表編號為k的車輛從編號為i的需求點行駛至編號為j的需求點；否則，xijk0。yik1代表i需求點由車輛k服務(wù)；否則，yik0。（2）各參數(shù)的定義：v代表

4、配送中心的全部車輛的集合，即vvk，k1，2，m；r代表配送中心與客戶點的集合，即rri，i0，1，2，n，其中r0代表配送中心；qk為車輛k的最大裝載量，本文假定所有的車輛最大轉(zhuǎn)載量都為q0；gi為客戶點i的需求量；dij為客戶點i與客戶點j之間的距離；tij為車輛從客戶點i到客戶點j之間的行駛時間；tk為車輛k從配送中心出發(fā)的時間；ti為車輛在客戶點i的停留時間，包括卸貨、安裝及其他作業(yè)時間，本文假定所有的停留時間都是t0。ti為車輛到達客戶點i的時刻點。ai代表客戶時間窗起點，bi代表客戶時間窗終點，pe代表車輛早到的懲罰系數(shù)，p1代表車輛遲到的懲罰系數(shù)。p（ti）代表車輛在客戶點i處早

5、到或遲到的懲罰值。 23模型建立 （1）目標函數(shù)。本文選取車輛最小化總行駛路程、最小化總配送時間和最小化違反客戶時間要求的懲罰值作為物流配送的三大主要目標，因此本文是一個多目標的vrp問題。最小化車輛總行駛路程的優(yōu)化目標：minf1ninjmkdijxijk最小化總配送耗費時間的優(yōu)化目標：minf2ninjmktijxijknntoxijk在實際的求解過程中，因本文模型中假定每輛車只有一條行駛路線，即ninjt0xijknt0等于一個設(shè)定的常量，在優(yōu)化過程中可以省去。最小化違反客戶時間要求的懲罰值目標：minf3njpemax（0，aiti）p1max（0，tibi）p（ti）代表懲罰值，ti

6、表示車輛實際到達客戶處的時間，ai代表客戶允許的最早到達時間，bi代表客戶允許的最遲到達時間，兩者之間即為客戶的時間窗，pe代表車輛早到的懲罰系數(shù)，p1代表車輛遲到的懲罰系數(shù)。在軟時間窗條件下，允許車輛的到達時間在客戶的時間窗之外，并賦以不同的懲罰程度。這種情況一般更符合實際，企業(yè)可以依據(jù)自身情況的不同，通過設(shè)置不同的懲罰系數(shù)來平衡客戶滿意度與成本控制兩者之間的矛盾。 （2）約束條件。車輛的容量約束：nigiyikq0kv由車輛k完成的配送任務(wù)：njxijkyjki，jr，kvnjxijkyiki，jr，kv一個客戶只能由一輛車來完成配送任務(wù)：mkyik1ir，kv要求所有車輛必須從配送中心出

7、發(fā)：x（xijk）ss（xijk）irjrxijkr1，rr，kv該式可以消除不與配送中心連接的支路，防止出現(xiàn)不與配送中心相連的路徑。任意客戶點都在路線之中：xijk0，1i，jr，kv任意的車輛都只有一條行駛路線：yik0，1i，jr，kv車輛k到達客戶點j的時間：tjninjtijxijkninjt0xijkt0tki，jr，kv針對可以預(yù)測的隨機性路況問題，可以將勻速狀態(tài)下的配送車輛的行駛時間通過一定的計算，換算成道路狀況異常時的期望的車輛行駛時間。如果車輛行駛時間服從正態(tài)分布、泊松分布等，可以計算出相應(yīng)的車輛行駛時間的期望值。更實際的情況是，在配送工作中，難以知道確切的行駛時間分布，但

8、可以根據(jù)一些因素定性地分析和估算出以不同時間通過的概率，或依據(jù)先前的運輸經(jīng)驗獲得以各種時間通過的概率（或稱為頻率）值，即經(jīng)驗分布。如以1小時通過的概率為08，以45分鐘和1小時15分鐘通過的概率分別為01等。即，通過將原路徑可能的通過時間tij乘以一個路況條件概率系數(shù)ij，得到新的路徑通過時間。tijtijij。 3案例分析 本文采用r公司在n城市的配送中心的某日上午的配送需求樣本數(shù)據(jù)，對模型求解。該日，r公司在n城市有8個客戶需求點，將客戶需求量進行重量化，分別需要240kg、120kg、150kg、150kg、200kg、50kg、230kg、160kg，總需求量為1300kg。雖然配送車

9、輛的載重能力為1200kg，但由于貨物形態(tài)大多是不規(guī)則的，配送車輛不可能實現(xiàn)滿載，依據(jù)實際經(jīng)驗，將配送車輛的最大載重設(shè)定為580kg，經(jīng)簡單計算約需要3輛車來完成配送作業(yè)。各客戶點與配送中心的兩兩間距如表1所示。3輛車的開始出發(fā)時間均為08：00，在優(yōu)化模型時均處理為0時刻出發(fā)，即“車輛9：30到達某客戶點1”的表示方法為“到達客戶點1的時刻為90時刻”。通過收集歷史數(shù)據(jù)，假定配送中心到各個需求點及需求點之間的行駛時間服從一定的概率分布，經(jīng)過概率的計算，各點之間的行駛時間為表2所示。各客戶點及配送中心的時間窗要求如表33所示。為了簡化處理，各點的開始時間窗假定為初始時間，即僅結(jié)束時間窗有效。如

10、配送中心0的結(jié)束時間窗為300，代表車輛離開配送中心送貨后300分鐘之內(nèi)需要返回配送中心，否則將接受一定的懲罰。編寫matlab程序，采用改進的遺傳算法求解“最優(yōu)”的路徑，要求該路徑的總長度較短，總配送時間較少，且盡量不違背客戶的時間要求。在遺傳算法的程序設(shè)計方面，考慮到存在8個客戶點，1個配送中心，需要3輛車，matlab自動生成的路徑的大體結(jié)構(gòu)類似于：（0，1，2，3，4，5，6，7，8，0，0，0）這樣的結(jié)構(gòu)；此處為了減少程序計算的復(fù)雜性，可以將路徑編碼設(shè)定為不重復(fù)的自然數(shù)，即將上條路徑結(jié)構(gòu)對應(yīng)為（1，2，3，4，5，6，7，8，9，10，11，12）在算子的設(shè)計方面，選擇初始種群為10

11、0，遺傳代數(shù)為200，交叉概率為02，變異概率為01，在microsoftwindowsxpsp3操作系統(tǒng)、173ghz的genuineintel（r）處理器、1g內(nèi)存的計算機上求出最優(yōu)解。最優(yōu)解如下：目標函數(shù)值：0001。該函數(shù)值實際為最優(yōu)解的適應(yīng)值大小，因為本文構(gòu)建的函數(shù)適應(yīng)值經(jīng)過求導(dǎo)處理，故該結(jié)果的數(shù)值較小。最優(yōu)路徑：196810472113512。轉(zhuǎn)化為易理解的路徑結(jié)構(gòu)，即為（0，8，5，7，0，3，6，1，0，2，4，0）。它的含義是：第1輛車從配送中心出發(fā)，經(jīng)由客戶點8，到客戶點5，再到客戶點7，之后返回配送中心；第2輛車出配送中心出發(fā)，經(jīng)由客戶點3，到客戶點6，再到客戶點1，之后返回配送中心；第3輛車從配送中心出發(fā)，經(jīng)由客戶點2，到客戶點4，再返回配送中心。在本文中，由于正反向的路徑長度、行駛時間相同，所以3條路徑組內(nèi)的行駛順序是無差異的。此時，總路徑長度：9500；總的行駛時間為：260min；總違背客戶時間窗的懲罰值為0，程序運行時間：22438000s?？梢钥闯?，在本文的案例中，能夠滿足不違背客戶時間要求的情況下，求解較短的路徑和較少的行駛時間。值得說明的是，若不考慮總行駛時間約束和違背客戶時間窗約束，可計算出的最短路徑為（0，3，1，6，4，0，8，5，7，0，2，0），最短路長度為