国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于改進(jìn)節(jié)約算法的計(jì)量表計(jì)運(yùn)送車輛調(diào)度

2015-04-25 09:59方彥軍
制造業(yè)自動(dòng)化 2015年3期
關(guān)鍵詞:節(jié)約路線計(jì)量

孫 勇,方彥軍,肖 勇

SUN Yong1, FANG Yan-jun1, XIAO Yong2

(1.武漢大學(xué) 自動(dòng)化系,武漢 430072;2.廣東電網(wǎng)有限責(zé)任公司 電力科學(xué)研究院,廣州 510080)

0 引言

省級(jí)電能計(jì)量中心的設(shè)立改變了原有的計(jì)量設(shè)備檢定模式,新的業(yè)務(wù)流程下電能計(jì)量中心承擔(dān)向地市級(jí)二級(jí)庫(kù)進(jìn)行設(shè)備配送的任務(wù),因此有必要對(duì)計(jì)量表計(jì)運(yùn)送車輛路徑規(guī)劃進(jìn)行研究。

計(jì)量表計(jì)運(yùn)送車輛的路徑規(guī)劃問題屬于VRP問題[1~3],相關(guān)研究較多,一般可分為啟發(fā)式算法和智能優(yōu)化算法,啟發(fā)式算法中的節(jié)約算法[4,5]相對(duì)簡(jiǎn)單,便于理解,在具體問題中應(yīng)用較為廣泛[6]。文獻(xiàn)[7]討論了有時(shí)間窗約束的非滿載車輛的調(diào)度問題,文獻(xiàn)[8]討論了目標(biāo)函數(shù)總費(fèi)用具有區(qū)間數(shù)特性的改進(jìn)節(jié)約算法,文獻(xiàn)[9]提出了允許訂貨量分割的改進(jìn)節(jié)約算法。

本文結(jié)合電能計(jì)量中心業(yè)務(wù)流程特點(diǎn),根據(jù)現(xiàn)有工作模式與時(shí)間安排方式,提出基于多目標(biāo)優(yōu)化、綜合考慮配送回收策略的改進(jìn)節(jié)約算法。該方法能夠更好的實(shí)現(xiàn)計(jì)量車輛路徑規(guī)劃需求,實(shí)現(xiàn)路徑規(guī)劃的高效節(jié)能,通過相關(guān)實(shí)例進(jìn)行對(duì)比分析,表明此方法確定的運(yùn)送方案能夠滿足相關(guān)業(yè)務(wù)需求,最大限度節(jié)約時(shí)間、經(jīng)濟(jì)成本。

1 問題描述及模型建立

省級(jí)電能計(jì)量中心服務(wù)全省所有地市區(qū)二級(jí)庫(kù),需要根據(jù)各地市區(qū)業(yè)務(wù)需求的不同進(jìn)行運(yùn)送車輛調(diào)配?;诠?jié)約資源的原則,部分箱體需要進(jìn)行回收再利用,因此運(yùn)送車輛需要綜合考慮箱體的回收操作。同時(shí),由于每個(gè)階段的配送方案即配送業(yè)務(wù)需求是變化的,最優(yōu)配送路徑也隨之改變,這就需要根據(jù)當(dāng)次業(yè)務(wù)需求來制定配送任務(wù)和車輛最優(yōu)運(yùn)送路徑,進(jìn)而確定回收任務(wù),以此提高整個(gè)運(yùn)送過程的效率。

在車輛實(shí)際運(yùn)作中,影響目標(biāo)優(yōu)化的因素較多,需要考慮的情況較復(fù)雜,因此為了方便建模,需要對(duì)問題進(jìn)行簡(jiǎn)化和假定,以便在一定的限制條件內(nèi)進(jìn)行運(yùn)送路徑優(yōu)化問題研究。本文在遵循現(xiàn)有工作模式與時(shí)間安排制度的基礎(chǔ)上,對(duì)計(jì)量表計(jì)運(yùn)送車輛路徑規(guī)劃問題進(jìn)行如下假設(shè):

1)省級(jí)電能計(jì)量中心只有一個(gè),負(fù)責(zé)向全省地市二級(jí)庫(kù)進(jìn)行配送,計(jì)量中心和二級(jí)庫(kù)位置固定且兩兩之間行駛路徑指定。

2)計(jì)量中心車輛單一,載重限制要求固定,不允許超載;運(yùn)送車輛按照規(guī)劃路線從計(jì)量中心出發(fā),依次到達(dá)所負(fù)責(zé)的地市庫(kù),完成配送與回收任務(wù)后進(jìn)行下一節(jié)點(diǎn)運(yùn)送,最終返回計(jì)量中心。運(yùn)送車輛需在12小時(shí)內(nèi)完成整個(gè)運(yùn)送作業(yè)并返回計(jì)量中心。

3)各個(gè)二級(jí)庫(kù)配送物資可以混裝,即可以同時(shí)裝載于一輛運(yùn)送車輛;同時(shí)某一二級(jí)庫(kù)所需的計(jì)量表計(jì)允許分裝,由不同運(yùn)送車輛進(jìn)行配送。

4)運(yùn)送車輛以配送任務(wù)為主,先根據(jù)配送需求進(jìn)行路徑選擇,再根據(jù)已定路徑,進(jìn)行回收方案制定,并保證在整個(gè)運(yùn)送中任意時(shí)刻車輛不超載。

5)通過營(yíng)銷業(yè)務(wù)系統(tǒng),計(jì)量中心可以實(shí)時(shí)獲取各個(gè)二級(jí)庫(kù)的相關(guān)數(shù)據(jù),即表計(jì)需求量、待回收表箱數(shù),其中需求量為剛性需求,待回收表箱數(shù)為區(qū)間數(shù)表示。

6)配送的計(jì)量表計(jì)和回收的周轉(zhuǎn)箱可以混裝,同時(shí)根據(jù)運(yùn)送車輛的載重載容限制,滿裝周轉(zhuǎn)箱與空周轉(zhuǎn)箱的占據(jù)容積比為1∶1.2,即運(yùn)送車輛相同空間可以放置更多的空周轉(zhuǎn)箱。

7)路線規(guī)劃是基于多目標(biāo)優(yōu)化,即從單純考慮空間距離到考慮速度、成本、天氣因素等多目標(biāo)。

根據(jù)上述描述和相關(guān)假定,以綜合優(yōu)化指標(biāo)最小為目標(biāo),建立以智能計(jì)量設(shè)備配送為主、兼顧空周轉(zhuǎn)箱回收需求的車輛路徑規(guī)劃模型。

2 求解算法的設(shè)計(jì)

2.1 基本節(jié)約算法

節(jié)約算法是路徑優(yōu)化中的一種啟發(fā)式算法,根據(jù)優(yōu)化目標(biāo)的不同有具體的表現(xiàn)形式。下面以空間距離為優(yōu)化目標(biāo)來說明節(jié)約算法的基本思想。設(shè)配送中心為M0,N個(gè)二級(jí)地市級(jí)配送庫(kù)分別為已知任意兩個(gè)節(jié)點(diǎn)之間的距離為則對(duì)于任意兩個(gè)二級(jí)地市級(jí)配送庫(kù),計(jì)量中心配送方案可分為單獨(dú)配送和合并配送兩種模式,后者比前者的節(jié)約量為:此即為節(jié)約算法進(jìn)行運(yùn)算的基礎(chǔ)。

通過計(jì)算任意兩個(gè)地市區(qū)二級(jí)庫(kù)的節(jié)約量,可以構(gòu)造出所有配送點(diǎn)的節(jié)約量表,按照節(jié)約量從大到小的順序進(jìn)行配送路徑的確定。先選取節(jié)約量最大的兩個(gè)配送點(diǎn)作為某條配送線路的兩個(gè)端點(diǎn),同時(shí)檢查兩個(gè)配送點(diǎn)的貨運(yùn)量之和是否超過車輛限制條件;再?gòu)墓?jié)約量表中選擇包含這兩個(gè)配送端點(diǎn)之一的最大節(jié)約量,將有關(guān)二級(jí)庫(kù)點(diǎn)加入配送路線,計(jì)算是否超過限制條件并確定配送端點(diǎn);依次進(jìn)行這種操作,直至配送線路載貨量超過車輛限制條件,再尋找節(jié)約量表中包含兩個(gè)配送端點(diǎn)之一的較小節(jié)約量,看是否不超過限制條件。直到所有可能的連接都連接完成,則得到一條配送路線。

依次循環(huán)上述操作,可確定計(jì)量中心配送方案。

2.2 改進(jìn)節(jié)約算法

改進(jìn)節(jié)約算法是在節(jié)約算法的基礎(chǔ)上,進(jìn)行必要的改進(jìn),使之更加適應(yīng)具體問題和應(yīng)用實(shí)例。相關(guān)研究提出了基于貨物分割、單位距離載重的選擇性滿載等思想的改進(jìn)節(jié)約算法,較好的解決了相關(guān)實(shí)際問題。

本文結(jié)合實(shí)際運(yùn)行情況,提出改進(jìn)的節(jié)約算法,首先以綜合指標(biāo)系數(shù)作為節(jié)約算法的優(yōu)化目標(biāo),而不再是單一的空間距離。綜合指標(biāo)系數(shù)根據(jù)城市間實(shí)際路程公里數(shù)、汽車實(shí)際行駛速度概率、行駛經(jīng)濟(jì)費(fèi)用、突發(fā)事件等情況進(jìn)行綜合得出,最終反映到節(jié)點(diǎn)運(yùn)行時(shí)間,節(jié)點(diǎn)運(yùn)行時(shí)間是動(dòng)態(tài)調(diào)整變化的。以空間距離為優(yōu)化目標(biāo)的基本節(jié)約算法是假定空間距離為唯一決定車輛運(yùn)行狀況的因素,而實(shí)際情況下,相關(guān)因素對(duì)運(yùn)行狀況影響也較大,如局部地區(qū)天氣狀況、路面維修及突發(fā)事故交通受阻狀況、運(yùn)送車性能狀態(tài)、車輛行駛正常速度與非正常速度概率,這些因素都會(huì)影響優(yōu)化結(jié)果,因此改進(jìn)節(jié)約算法對(duì)基本節(jié)約算法的第一個(gè)改進(jìn)即為引進(jìn)綜合指標(biāo)系數(shù),系數(shù)構(gòu)成如下式:

式中:S為綜合指標(biāo)系數(shù);

N為天氣狀況指數(shù);

P為路面維修、突發(fā)事故指數(shù);

Q為運(yùn)送車車體狀況指數(shù);

T為速度概率;

a、b、c、d為權(quán)重系數(shù)。

建立科學(xué)可行的綜合性能指數(shù)模型對(duì)于真實(shí)反映優(yōu)化目標(biāo),以及優(yōu)化結(jié)果的真實(shí)性和可操作性有很大幫助。而綜合性能指數(shù)最終以節(jié)點(diǎn)運(yùn)行時(shí)間作為衡量參考,節(jié)點(diǎn)運(yùn)行時(shí)間與簡(jiǎn)單的用空間距離除以車輛行駛速度有很大區(qū)別,綜合性能指數(shù)是在綜合相關(guān)因素的基礎(chǔ)上得到的節(jié)點(diǎn)運(yùn)行時(shí)間,更能真實(shí)反映運(yùn)行中的各種因素,優(yōu)化結(jié)果更具真實(shí)性。

改進(jìn)節(jié)約算法在采用綜合指標(biāo)系數(shù)為優(yōu)化目標(biāo)后,其運(yùn)算流程如圖1所示,可以看出和基本節(jié)約算法相似,同樣是得出節(jié)約量表,依次尋找節(jié)約量最大的節(jié)點(diǎn)進(jìn)行線路規(guī)劃。本文提出的改進(jìn)節(jié)約算法并不對(duì)運(yùn)送車輛滿載作進(jìn)一步要求,主要是考慮回收策略的制定。實(shí)際操作過程中,二級(jí)庫(kù)需要回收的空周轉(zhuǎn)箱數(shù)并不是一個(gè)定數(shù),而是在一定范圍內(nèi)變化,因此采用區(qū)間數(shù)的表達(dá)方式,回收策略的回收量必須在區(qū)間數(shù)表達(dá)的范圍內(nèi),這樣更符合業(yè)務(wù)需求。

改進(jìn)節(jié)約算法和傳統(tǒng)的節(jié)約算法在綜合指標(biāo)系數(shù)、回收策略制定方面有所不同,整個(gè)算法的優(yōu)化目標(biāo)為在節(jié)約量最大的前提下,盡可能實(shí)現(xiàn)回收量的最大化。

3 算例分析

3.1 基本情況

根據(jù)第1節(jié)對(duì)運(yùn)送車輛路徑規(guī)劃問題做的分析,選取廣東中東部地區(qū)11個(gè)地級(jí)城市作為假定算例進(jìn)行分析。表1列出了省級(jí)計(jì)量中心(配送中心)、各地市區(qū)二級(jí)庫(kù)之間的距離,其中城市序號(hào)1代表計(jì)量中心。表中數(shù)值為指定行駛線路下的空間距離。同時(shí)假定計(jì)量中心運(yùn)送車能夠載重300個(gè)滿載計(jì)量箱體,則根據(jù)第1節(jié)假設(shè)6,運(yùn)送車可裝360個(gè)空箱體。某次運(yùn)送策略制定前,根據(jù)相關(guān)業(yè)務(wù)系統(tǒng)獲取各二級(jí)庫(kù)有關(guān)信息,并依照運(yùn)送車載貨情況進(jìn)行歸一化處理,則各二級(jí)庫(kù)箱體需求量及回收量如表2所示。

圖1 改進(jìn)節(jié)約算法的計(jì)算流程圖

表1 配送中心與各二級(jí)庫(kù)之間的空間距離

表2 各配送點(diǎn)需求量及回收量

根據(jù)改進(jìn)節(jié)約算法對(duì)綜合指標(biāo)系數(shù)的定義,將二級(jí)庫(kù)之間的空間距離轉(zhuǎn)換為二級(jí)庫(kù)之間的節(jié)點(diǎn)運(yùn)行時(shí)間,如表3所示。改進(jìn)方法的配送方案采用綜合指標(biāo)系數(shù),可以大幅度綜合實(shí)際運(yùn)行中可能出現(xiàn)的影響運(yùn)送的因素。

表3 配送中心與二級(jí)庫(kù)之間的綜合指標(biāo)系數(shù)

3.2 配送路線的確定

根據(jù)表1和表3中的數(shù)據(jù),進(jìn)行節(jié)約算法及改進(jìn)節(jié)約算法的運(yùn)算,可以得到配送路線如表4、表5所示。兩種方法得出的配送方案有所不同,路線1和路線2相同,路線3和4的結(jié)果不同。對(duì)比路線3和路線4的總耗時(shí)和總行駛路程,改進(jìn)節(jié)約算法的結(jié)果更加省時(shí),同時(shí)總路程也較短。更有利的是以綜合指標(biāo)系數(shù)為優(yōu)化目標(biāo)的方法得出的配載率也相對(duì)均衡,這樣為后續(xù)回收方案的制定提供了更大的可操作空間。

表4 配送方案-空間距離

表5 配送方案-綜合指標(biāo)系數(shù)

3.3 回收方案的確定

根據(jù)確定的運(yùn)送路線和回收需求,可以制定每條配送線路的回收策略。本方法不要求分割訂單實(shí)現(xiàn)滿載,主要是考慮回收任務(wù),其相關(guān)空間可以最大限度滿足各二級(jí)庫(kù)對(duì)空周轉(zhuǎn)箱回收的需求。回收時(shí)必須首先滿足各二級(jí)庫(kù)回收區(qū)間的下限要求,同時(shí)盡可能滿足優(yōu)先級(jí)較高的二級(jí)庫(kù)的上限需求。

以第1條配送線路為例說明回收方案的制定,如果三個(gè)城市沒有優(yōu)先級(jí)的區(qū)別,只是根據(jù)行駛路線上的順序按照最大的可能性進(jìn)行操作,則序號(hào)9、11、10這三個(gè)二級(jí)庫(kù)的回收量依次為0.5、0.4、0.15,即二級(jí)庫(kù)11不能實(shí)現(xiàn)最大量的回收,其余兩個(gè)二級(jí)庫(kù)可以實(shí)現(xiàn)最大回收量;如果二級(jí)庫(kù)11優(yōu)先級(jí)高于線路上其他二級(jí)庫(kù),則回收策略變化為0.4、0.6、0.15,即為保證序號(hào)11的二級(jí)庫(kù)的回收需求,在9號(hào)二級(jí)庫(kù)時(shí)預(yù)留空間為11號(hào)做準(zhǔn)備;如果序號(hào)9、11的優(yōu)先級(jí)相同,則回收策略變化為0.45、0.55、0.15,即兩者同時(shí)受到了影響。一般情況下,優(yōu)先級(jí)的設(shè)置是為了保證二級(jí)庫(kù)庫(kù)存管理的靈活性,結(jié)合相關(guān)業(yè)務(wù)系統(tǒng)的優(yōu)化調(diào)度,一般不會(huì)存在一條線路上多個(gè)高優(yōu)先級(jí)二級(jí)庫(kù)的情況,因此高優(yōu)先級(jí)二級(jí)庫(kù)的需求都能得到滿足。

因此,以綜合指標(biāo)系數(shù)為優(yōu)化目標(biāo)制定的配送方案下,不考慮二級(jí)庫(kù)優(yōu)先級(jí)區(qū)分的最終回收方案結(jié)果為,除二級(jí)庫(kù)3、11之外,其余二級(jí)庫(kù)均可實(shí)現(xiàn)需求量上限的回收,而二級(jí)庫(kù)3、11只能回收需求量中的0.4。整體回收方案基本滿足需求。

4 結(jié)束語

本文提出的改進(jìn)節(jié)約算法能夠根據(jù)實(shí)際情況進(jìn)行改善,更加符合配送需求。依照空間距離的方式,并不能直接將相關(guān)因素考慮在內(nèi),而通過綜合指標(biāo)系數(shù),可以將道路信息進(jìn)行整合,更加完善的反映相關(guān)情況。通過算例分析,得出兩者的規(guī)劃路徑不同,對(duì)比配載率、時(shí)間消耗、總行駛路程等指標(biāo),可以看出本文的配送策略更為有效。同時(shí),在更加可靠的配送任務(wù)解決后,再進(jìn)行回收路徑規(guī)劃,完成配送-回收任務(wù),實(shí)現(xiàn)業(yè)務(wù)需求。

[1] 劉家利,馬祖軍.存在車輛租賃及共享且有時(shí)間窗的多配送中心開環(huán)V R P[J].系統(tǒng)工程理論與實(shí)踐,2013,33(3)∶666-675.

[2] Yiyo Kuo. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J].Computers & Industrial Engineering, 2010,59(2010)∶157-165.

[3] 謝桂芩,楊玉華,涂井先.帶有時(shí)間窗的虛擬場(chǎng)站接駁補(bǔ)貨車輛路徑問題[J].廣東工業(yè)大學(xué)學(xué)報(bào),2013,30(1)∶61-67,72.

[4] 張建勇,郭耀煌,李軍.一種具有模糊費(fèi)用系數(shù)的VSP的修正C-W節(jié)約算法[J].西南交通大學(xué)學(xué)報(bào),2004,39(3)∶281-284,310.

[5] 付連寧,崔文,曾華.并行節(jié)約算法的自適應(yīng)鄰域選擇策略[J]. 山東大學(xué)學(xué)報(bào)(工學(xué)版),2012,42(1)∶72-80.

[6] 張學(xué)志,陳功玉.車輛路線安排的改進(jìn)節(jié)約算法[J].系統(tǒng)工程,2008,26(11)∶67-70.

[7] 宋偉剛,張宏霞,佟玲.有時(shí)間窗約束非滿載車輛調(diào)度問題的節(jié)約算法[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2006,27(1)∶65-68.

[8] 劉誠(chéng),顧坤坤.具有區(qū)間參數(shù)的VRP及其改進(jìn)的C-W節(jié)約算法[J].武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版),2010,32(2)∶182-185.

[9] 范潔,曹俊琴.改進(jìn)節(jié)約算法在電表配送路線選擇中的應(yīng)用[J].物流工程與管理,2012,34(4)∶102-105.

猜你喜歡
節(jié)約路線計(jì)量
CPMF-I 取樣式多相流分離計(jì)量裝置
最優(yōu)路線
『原路返回』找路線
節(jié)約
節(jié)約
節(jié)約
計(jì)量自動(dòng)化在線損異常中的應(yīng)用
計(jì)量與測(cè)試
找路線
基于因子分析的人力資本計(jì)量研究
平果县| 仁怀市| 肥城市| 五华县| 南靖县| 新平| 安远县| 迁安市| 铜陵市| 元阳县| 崇信县| 友谊县| 张家港市| 全州县| 永靖县| 五台县| 洪洞县| 定远县| 双鸭山市| 万年县| 肥城市| 根河市| 武乡县| 边坝县| 泌阳县| 镇赉县| 津南区| 玉溪市| 蓬莱市| 开原市| 南溪县| 郎溪县| 达拉特旗| 正宁县| 闻喜县| 遂平县| 黑水县| 资兴市| 青州市| 环江| 新绛县|