線路截斷法在卷煙配送路徑規(guī)劃中的應(yīng)用

魏 嫄， 曾 華， 吳耀華 WEI Yuan,ZENG Hua,WU Yao-hua

（1.山東大學(xué) 現(xiàn)代物流研究中心，山東 濟(jì)南 250061；2.四川省煙草公司成都市公司，四川 成都 610072）

在我國，一般以市級煙草配送中心為中心，直接配送到全市各地的上萬個配送點(diǎn)。負(fù)責(zé)卷煙配送的車輛由煙草配送中心出發(fā)，依次到其負(fù)責(zé)的收貨點(diǎn)進(jìn)行配送，最終配送完成后車輛返回配送中心[1]。現(xiàn)有的卷煙配送車輛型號眾多，載貨量也有區(qū)別。卷煙配送路線的規(guī)劃是一個LS-VRP（大規(guī)模車輛路徑）問題，是一個NP問題。對于一般的LS-VRP問題有精確算法、亞啟發(fā)式算法和啟發(fā)式算法等。

眾所周知，我國卷煙配送工作由來已久，因此各地?zé)煵萆虡I(yè)企業(yè)在發(fā)展中已經(jīng)形成了自己的配貨順序，并根據(jù)配貨順序安排配送車輛。這種配貨順序有其存在的合理性，并且已經(jīng)在運(yùn)行之中，進(jìn)行較大的改動有一定的風(fēng)險。但是傳統(tǒng)的車輛配送任務(wù)分配主要采取人工的方式進(jìn)行，工作量大且優(yōu)化程度較低。另外，在解決大規(guī)模VRP問題的方法中，一種思想先按照TSP問題利用算法生成一個全局的配送路線，之后對這個總的配送路線進(jìn)行截斷，來確定分配給每輛車的配送路線，從而生成卷煙配送VRP問題的配送方案。這種方法優(yōu)化程度較高，而且可以保證較快的計算速度。因此基于大線路截斷成小線路進(jìn)行配送的方法有一定的實際價值。

而且除了總配送路程最短、費(fèi)用最小、時間最短等一般VRP問題的約束之外，處于管理上的考慮，卷煙配送過程有其特有的特點(diǎn)，例如要求不同車輛工作時間比較均衡且小于上限、車輛之間的配送量均衡等。因此引入了一些原則進(jìn)行配送任務(wù)劃分來保證車輛工作強(qiáng)度的均衡。

本文研究的基于配送任務(wù)均衡的線路截斷方法，屬于一種亞啟發(fā)式算法，主要實現(xiàn)的功能是在收貨點(diǎn)配送排序確定的情況下，把這些收貨點(diǎn)的配送任務(wù)分配給各配送貨車。貨車從配送中心出發(fā)，按照指定的順序配送其負(fù)責(zé)的收貨點(diǎn)，之后返回配送中心。在這個過程中要考慮配送路徑最短、所用車輛最少、配送工作量均衡的要求。

1 模型建立

收貨點(diǎn)配送任務(wù)序列為：

其中s1,s2,…,sn表示n個收貨點(diǎn)的收貨量。而其角標(biāo)表示該收貨點(diǎn)配送的次序。s1為第一個配送，s2為第二個配送，依次類推，sn為最后一個。每個收貨點(diǎn)只能由一個車輛配送。

每個車輛包含標(biāo)準(zhǔn)載貨量和標(biāo)準(zhǔn)服務(wù)客戶數(shù)兩個指標(biāo)，這兩個指標(biāo)由車輛的型號和配送人員的工作時間確定。

配送車輛標(biāo)準(zhǔn)載貨量為：與標(biāo)準(zhǔn)載貨量、服務(wù)客戶數(shù)與標(biāo)準(zhǔn)服務(wù)客戶數(shù)的比值，即裝載率和服務(wù)率，用來衡量車輛的工作負(fù)荷程度。表示了所有車輛的裝載率和服務(wù)率。Pv與Pc計算了車輛實際裝載率、服務(wù)率與平均值的差值之和，其值越大表示車輛的任務(wù)分配越不均衡。目標(biāo)函數(shù)反映了實際卷煙配送中的實際要求。

2 模型求解

在實際的配送過程中，首先需要設(shè)定每輛車的裝載率和服務(wù)率的上下限值即車輛的裝載率不得高

式中Dis表示每個配送車輛的配送距離d之和，即總配送距離。N為使用的車輛總數(shù)。ρvj、ρcj分別表示第j輛車的裝載量行配送任務(wù)的劃分。

為了保證任務(wù)量的均衡和較短的配送距離，本文設(shè)計了基于線路截斷的亞啟發(fā)式算法進(jìn)行配送任務(wù)劃分。算法的流程如下：

Step1 對每輛車進(jìn)行模擬裝車，以車輛j為例，將待分配任務(wù)序列（第一次循環(huán)時即為初始S序列）中的收貨點(diǎn)從前到后依次裝入車輛j中，當(dāng)車輛j的裝載量與服務(wù)率之一達(dá)到其下限值時，當(dāng)前最后一個裝入的點(diǎn)即為其裝載任務(wù)的下限點(diǎn)，假設(shè)該點(diǎn)為sl，之后繼續(xù)裝載，當(dāng)車輛j的裝載量與服務(wù)率之一達(dá)到上限值時，最后一個裝入的點(diǎn)即為其裝載任務(wù)的上限點(diǎn)，假設(shè)該點(diǎn)為su，則車輛j的可截斷區(qū)間為［sl,su］。即該車輛的當(dāng)前配送任務(wù)可以是從配送序列的第一個點(diǎn)s1開始到［sl,su］中任何一點(diǎn)結(jié)束。計算所有車輛的可截斷區(qū)間。

Step2 找到每個車輛可截斷區(qū)間內(nèi)相隔距離最長的一組相鄰點(diǎn)兩點(diǎn)之間距離記錄為Savj， 則車輛的模擬配送任務(wù)為是剩余配送任務(wù)序列的起始點(diǎn)，即新的s1。之后比較所有車輛當(dāng)前模擬裝車的使用效率選擇使用效率最高的車型作為當(dāng)前循環(huán)的所選車型，其配送任務(wù)為其對應(yīng)的 （s1… sa），將已配送的點(diǎn)以及該車輛從任務(wù)序列和備選車型中刪除。于其上限值，也不能低于其下限值，服務(wù)率亦然。這樣可以保證車輛的使用率。如果車輛運(yùn)力緊張的情況下可以將下限值提高，但會降低在配送距離優(yōu)化中的調(diào)整余地。如果需主要考慮配送里程的節(jié)約可以適當(dāng)擴(kuò)大區(qū)間，從而可以在更寬的范圍內(nèi)進(jìn)

圖1 某車輛的服務(wù)區(qū)間計算示意圖

Step3 如果最后一個車的使用效率低于平均使用效率的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ù)據(jù)分析

下面通過Matlab軟件編程進(jìn)行仿真實驗。

配送任務(wù)序列為某地市實際卷煙配送任務(wù)，共712個點(diǎn)。

輸入數(shù)據(jù)：

配送中心與收貨點(diǎn)、各收貨點(diǎn)之間的距離矩陣，各收貨點(diǎn)的收貨量，車輛矩陣：

車輛編號 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)的裝車方案為：

車輛編號 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)整后，裝車方案為：

車輛編號 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ù)分配完畢。整個算法運(yùn)行時間為1.87s。

可以看出，該算法可以在很短的時間內(nèi)完成大規(guī)模配送任務(wù)的劃分，并且較好地實現(xiàn)了配送任務(wù)的均衡與配送里程的節(jié)約，從而可以針對不同的卷煙需求做出相應(yīng)的配送方案，從而實現(xiàn)動態(tài)任務(wù)規(guī)劃和卷煙敏捷供應(yīng)的目的。

[1] 翁建紅，李朝陽.基于GPS的煙草物流配送線路規(guī)劃[J].物流科技，2008,31(9):18-20.