魏 嫄， 曾 華， 吳耀華 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è)過程中要考慮配送路徑最短、所用車輛最少、配送工作量均衡的要求。

1 模型建立

收貨點(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í)際要求。

2 模型求解

在實(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)前解。

3 仿真實(shí)驗(yàn)與數(shù)據(jù)分析

下面通過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.