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

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

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

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

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

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

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

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

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

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

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

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