魏 嫄, 曾 華, 吳耀華 WEI Yuan,ZENG Hua,WU Yao-hua
(1.山東大學(xué) 現(xiàn)代物流研究中心,山東 濟(jì)南 250061;2.四川省煙草公司成都市公司,四川 成都 610072)
在我國(guó),一般以市級(jí)煙草配送中心為中心,直接配送到全市各地的上萬個(gè)配送點(diǎn)。負(fù)責(zé)卷煙配送的車輛由煙草配送中心出發(fā),依次到其負(fù)責(zé)的收貨點(diǎn)進(jìn)行配送,最終配送完成后車輛返回配送中心[1]?,F(xiàn)有的卷煙配送車輛型號(hào)眾多,載貨量也有區(qū)別。卷煙配送路線的規(guī)劃是一個(gè)LS-VRP(大規(guī)模車輛路徑)問題,是一個(gè)NP問題。對(duì)于一般的LS-VRP問題有精確算法、亞啟發(fā)式算法和啟發(fā)式算法等。
眾所周知,我國(guó)卷煙配送工作由來已久,因此各地?zé)煵萆虡I(yè)企業(yè)在發(fā)展中已經(jīng)形成了自己的配貨順序,并根據(jù)配貨順序安排配送車輛。這種配貨順序有其存在的合理性,并且已經(jīng)在運(yùn)行之中,進(jìn)行較大的改動(dòng)有一定的風(fēng)險(xiǎn)。但是傳統(tǒng)的車輛配送任務(wù)分配主要采取人工的方式進(jìn)行,工作量大且優(yōu)化程度較低。另外,在解決大規(guī)模VRP問題的方法中,一種思想先按照TSP問題利用算法生成一個(gè)全局的配送路線,之后對(duì)這個(gè)總的配送路線進(jìn)行截?cái)?,來確定分配給每輛車的配送路線,從而生成卷煙配送VRP問題的配送方案。這種方法優(yōu)化程度較高,而且可以保證較快的計(jì)算速度。因此基于大線路截?cái)喑尚【€路進(jìn)行配送的方法有一定的實(shí)際價(jià)值。
而且除了總配送路程最短、費(fèi)用最小、時(shí)間最短等一般VRP問題的約束之外,處于管理上的考慮,卷煙配送過程有其特有的特點(diǎn),例如要求不同車輛工作時(shí)間比較均衡且小于上限、車輛之間的配送量均衡等。因此引入了一些原則進(jìn)行配送任務(wù)劃分來保證車輛工作強(qiáng)度的均衡。
本文研究的基于配送任務(wù)均衡的線路截?cái)喾椒?,屬于一種亞啟發(fā)式算法,主要實(shí)現(xiàn)的功能是在收貨點(diǎn)配送排序確定的情況下,把這些收貨點(diǎn)的配送任務(wù)分配給各配送貨車。貨車從配送中心出發(fā),按照指定的順序配送其負(fù)責(zé)的收貨點(diǎn),之后返回配送中心。在這個(gè)過程中要考慮配送路徑最短、所用車輛最少、配送工作量均衡的要求。
收貨點(diǎn)配送任務(wù)序列為:
其中s1,s2,…,sn表示n個(gè)收貨點(diǎn)的收貨量。而其角標(biāo)表示該收貨點(diǎn)配送的次序。s1為第一個(gè)配送,s2為第二個(gè)配送,依次類推,sn為最后一個(gè)。每個(gè)收貨點(diǎn)只能由一個(gè)車輛配送。
每個(gè)車輛包含標(biāo)準(zhǔn)載貨量和標(biāo)準(zhǔn)服務(wù)客戶數(shù)兩個(gè)指標(biāo),這兩個(gè)指標(biāo)由車輛的型號(hào)和配送人員的工作時(shí)間確定。
配送車輛標(biāo)準(zhǔn)載貨量為:與標(biāo)準(zhǔn)載貨量、服務(wù)客戶數(shù)與標(biāo)準(zhǔn)服務(wù)客戶數(shù)的比值,即裝載率和服務(wù)率,用來衡量車輛的工作負(fù)荷程度。表示了所有車輛的裝載率和服務(wù)率。Pv與Pc計(jì)算了車輛實(shí)際裝載率、服務(wù)率與平均值的差值之和,其值越大表示車輛的任務(wù)分配越不均衡。目標(biāo)函數(shù)反映了實(shí)際卷煙配送中的實(shí)際要求。
在實(shí)際的配送過程中,首先需要設(shè)定每輛車的裝載率和服務(wù)率的上下限值即車輛的裝載率不得高
式中Dis表示每個(gè)配送車輛的配送距離d之和,即總配送距離。N為使用的車輛總數(shù)。ρvj、ρcj分別表示第j輛車的裝載量行配送任務(wù)的劃分。
為了保證任務(wù)量的均衡和較短的配送距離,本文設(shè)計(jì)了基于線路截?cái)嗟膩唵l(fā)式算法進(jìn)行配送任務(wù)劃分。算法的流程如下:
Step1 對(duì)每輛車進(jìn)行模擬裝車,以車輛j為例,將待分配任務(wù)序列(第一次循環(huán)時(shí)即為初始S序列)中的收貨點(diǎn)從前到后依次裝入車輛j中,當(dāng)車輛j的裝載量與服務(wù)率之一達(dá)到其下限值時(shí),當(dāng)前最后一個(gè)裝入的點(diǎn)即為其裝載任務(wù)的下限點(diǎn),假設(shè)該點(diǎn)為sl,之后繼續(xù)裝載,當(dāng)車輛j的裝載量與服務(wù)率之一達(dá)到上限值時(shí),最后一個(gè)裝入的點(diǎn)即為其裝載任務(wù)的上限點(diǎn),假設(shè)該點(diǎn)為su,則車輛j的可截?cái)鄥^(qū)間為[sl,su]。即該車輛的當(dāng)前配送任務(wù)可以是從配送序列的第一個(gè)點(diǎn)s1開始到[sl,su]中任何一點(diǎn)結(jié)束。計(jì)算所有車輛的可截?cái)鄥^(qū)間。
Step2 找到每個(gè)車輛可截?cái)鄥^(qū)間內(nèi)相隔距離最長(zhǎng)的一組相鄰點(diǎn)兩點(diǎn)之間距離記錄為Savj, 則車輛的模擬配送任務(wù)為是剩余配送任務(wù)序列的起始點(diǎn),即新的s1。之后比較所有車輛當(dāng)前模擬裝車的使用效率選擇使用效率最高的車型作為當(dāng)前循環(huán)的所選車型,其配送任務(wù)為其對(duì)應(yīng)的 (s1… sa),將已配送的點(diǎn)以及該車輛從任務(wù)序列和備選車型中刪除。于其上限值,也不能低于其下限值,服務(wù)率亦然。這樣可以保證車輛的使用率。如果車輛運(yùn)力緊張的情況下可以將下限值提高,但會(huì)降低在配送距離優(yōu)化中的調(diào)整余地。如果需主要考慮配送里程的節(jié)約可以適當(dāng)擴(kuò)大區(qū)間,從而可以在更寬的范圍內(nèi)進(jìn)
圖1 某車輛的服務(wù)區(qū)間計(jì)算示意圖
Step3 如果最后一個(gè)車的使用效率低于平均使用效率的20%,則可以通過調(diào)高每輛車的裝載率和服務(wù)率下限值之后返回Step1,直到將最后一輛車的配送任務(wù)分配至其他車輛為止。如果使用效率高于平均使用效率的20%低于85%,則通過調(diào)低每輛車的裝載率和服務(wù)效率下限值返回Step1,可以減少前面車輛的任務(wù)量,提升最后一輛車使用效率。如果最后一輛車的使用效率高于平均使用效率的85%則任務(wù)分配結(jié)束。
若循環(huán)20次之后仍無法跳出循環(huán),則輸出當(dāng)前解。
下面通過Matlab軟件編程進(jìn)行仿真實(shí)驗(yàn)。
配送任務(wù)序列為某地市實(shí)際卷煙配送任務(wù),共712個(gè)點(diǎn)。
輸入數(shù)據(jù):
配送中心與收貨點(diǎn)、各收貨點(diǎn)之間的距離矩陣,各收貨點(diǎn)的收貨量,車輛矩陣:
車輛編號(hào) 1 2 3 4 5 6 7 8 9載貨量下限 3 800 3 800.0 3 800.0 4 200.0 4 800.0 5 000.0 5 500 5 800.0 6 000.0載貨量上限 4 180 4 180.0 4 180.0 4 620.0 5 280.0 5 500.0 6 050 6 380.0 6 600.0服務(wù)客戶數(shù)下限 70 75.0 75.0 75.0 75.0 75.0 80 85.0 85.0服務(wù)客戶數(shù)上限 77 82.5 82.5 82.5 82.5 82.5 88 93.5 93.5
首次循環(huán)的裝車方案為:
車輛編號(hào) 3 1 2 4 5 6 7 8 9載重量 3 623.00 3 881.00 4 163.00 4 169.000 4 493.00 5 368.00 4 839.00 5 246.00 2 498.00服務(wù)客戶數(shù) 82.00 77.00 79.00 82.000 82.00 82.00 88.00 93.00 47.00裝載率 0.95 1.02 1.09 0.992 0.93 1.07 0.87 0.90 0.41服務(wù)率 1.09 1.10 1.05 1.090 1.09 1.09 1.10 1.09 0.55
當(dāng)前總配送里程為1 262km。由于最后一輛車的使用效率0.96為平均使用效率2.06的46%,從而通過調(diào)低其他車輛的載貨量與服務(wù)率的下限來將前面的車配送任務(wù)向后移。
通過8次循環(huán)調(diào)整后,裝車方案為:
車輛編號(hào) 4 7 8 9 5 1 3 6 2載重量 3 575.00 4 489.00 4 361.00 4 899.00 5 033.00 3 822.00 4 013.00 4 239.00 3 849.00服務(wù)客戶數(shù) 81.00 87.00 92.00 92.00 80.00 58.00 77.00 81.00 64.00裝載率 0.85 0.81 0.75 0.81 1.04 1.00 1.05 0.84 1.01服務(wù)率 1.08 1.08 1.08 1.08 1.06 0.82 1.02 1.08 0.85
當(dāng)前總配送里程為1 201km。最后一輛車的使用效率1.96為平均使用效率1.93的1.014%,達(dá)到終止條件,配送任務(wù)分配完畢。整個(gè)算法運(yùn)行時(shí)間為1.87s。
可以看出,該算法可以在很短的時(shí)間內(nèi)完成大規(guī)模配送任務(wù)的劃分,并且較好地實(shí)現(xiàn)了配送任務(wù)的均衡與配送里程的節(jié)約,從而可以針對(duì)不同的卷煙需求做出相應(yīng)的配送方案,從而實(shí)現(xiàn)動(dòng)態(tài)任務(wù)規(guī)劃和卷煙敏捷供應(yīng)的目的。
[1] 翁建紅,李朝陽.基于GPS的煙草物流配送線路規(guī)劃[J].物流科技,2008,31(9):18-20.