趙秦怡，趙榆琴

（大理大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

快遞車輛配裝問題是指快遞公司從配送中心派出車輛向某條路線上快遞站點(diǎn)進(jìn)行貨物配送時(shí)，還需將快遞站點(diǎn)攬收的貨物帶回配送中心，給出攬收貨物的重量及價(jià)值，在每個(gè)站點(diǎn)只被服務(wù)一次的情況下，使得車輛在完成貨物配送的同時(shí)在每個(gè)站點(diǎn)都取回價(jià)值盡可能大的貨物，車輛配裝問題屬于背包問題的范疇。

背包問題是指給定一組重量和價(jià)值已知的貨物和一個(gè)有載重限制的背包，如何選擇裝入背包的貨物，使得裝入背包的貨物價(jià)值盡可能大。背包問題是重要的NP困難問題，是典型的組合優(yōu)化問題，在投資決策、資源分配、裝載問題和下料問題的研究中具有重要的理論價(jià)值。圍繞經(jīng)典背包問題的研究已取得豐碩成果，文獻(xiàn)〔1〕提出了0－1增量背包問題，背包容量可遞增；文獻(xiàn)〔2〕提出了折扣0－1背包問題，物品不僅有重量和價(jià)值維度，且物品價(jià)值帶有折扣系數(shù)；文獻(xiàn)〔3〕提出多維背包問題，背包及物品均有多維特征；文獻(xiàn)〔4〕提出多維多選擇背包問題，在進(jìn)行物品選擇時(shí)有多個(gè)約束條件的附加；文獻(xiàn)〔5〕提出在線背包問題，背包容量可卸載，物品隨流水線移動(dòng)且重量及價(jià)值事先未知。

分支限界法是求最優(yōu)解的有效算法〔6〕，本文提出一種求解快遞車輛配裝問題帶限界函數(shù)的分支限界（express vehicle assembling knapsack problem，EVAKNP）算法。

1 EVAKNP問題描述

給定快遞車輛運(yùn)輸線路D的m個(gè)配送點(diǎn)車輛容量集｛C1，C2，…，Cm｝，m個(gè)物品集Pi=｛（v1，w1），…，（vi，wi），…，（vn，wn）｝，其中wi為第i種物品重量，vi為第i種物品價(jià)值，物品價(jià)值可以和快遞貨物的投遞時(shí)間、貨物本身的價(jià)值等因素相關(guān)，物品數(shù)量n在m個(gè)物品集中取值不同?？爝f車輛配裝問題，以下簡(jiǎn)稱EVAKNP問題，是指依次在m個(gè)配送點(diǎn)進(jìn)行物品配送和配裝，在車輛容量變化及物品集變化的情況下如何進(jìn)行裝載，使得經(jīng)m個(gè)配送點(diǎn)后車輛獲得最大價(jià)值V。原問題可由若干個(gè)子問題構(gòu)成，子問題k指車輛在配送點(diǎn)k卸貨，在該站車輛獲得Ck的容量，待裝載物品集為Pk，如何在Pk中進(jìn)行物品選擇增加車輛價(jià)值Vk，使得車輛途經(jīng)所有配送點(diǎn)后獲得最大價(jià)值。經(jīng)m個(gè)配送點(diǎn)后，出發(fā)時(shí)的物品均卸載完，每一次卸載之后獲得的容量Ck轉(zhuǎn)換為價(jià)值Vk，車輛返回時(shí)的價(jià)值V=V1+V2+…+Vm。

可以證明車輛返回時(shí)的價(jià)值V滿足最優(yōu)性原理。設(shè)V1為車輛在第一個(gè)配送點(diǎn)增加的最大價(jià)值，車輛之后增加的最大價(jià)值為Vx，則V=V1+Vx，顯然V一定是車輛最后獲得的最大價(jià)值。如若不然，設(shè)Vx是車輛在第一個(gè)配送點(diǎn)之后增加的最大價(jià)值，V1'是在第一個(gè)配送點(diǎn)獲得的價(jià)值且比V1還大，則V1'+Vx是車輛最后獲得的價(jià)值且比V還大，導(dǎo)致矛盾。同理，在第二個(gè)配送點(diǎn)車輛增加的最大價(jià)值V2使得Vx最大，以此類推。

快遞車輛配裝問題的子問題k可形式化描述為：

其中，vi和xi是該子問題物品集Pi中物品的價(jià)值和重量，Ck為第k個(gè)子問題中車輛的剩余容量，xi在集合｛0，1｝中取值，xi=0不裝載i號(hào)物品，xi=1則裝載i號(hào)物品。車輛配送問題可形式化描述為：

2 EVAKNP算法描述

2.1 算法思想EVAKNP問題求解由m個(gè)子問題的求解構(gòu)成，由式（1）可知第k個(gè)子問題的解Vk=max｛Vk1，…，Vki，…｝，Vki是子問題的可行解，Vk是子問題的最優(yōu)解。在本算法中采用分支限界法求最優(yōu)解，分支限界法按廣度優(yōu)先策略搜索問題的解空間樹，在搜索過程中，待處理結(jié)點(diǎn)用限界函數(shù)估算目標(biāo)函數(shù)（背包獲得的實(shí)際價(jià)值）的可能取值，在待處理結(jié)點(diǎn)中選取使目標(biāo)函數(shù)取得極值的結(jié)點(diǎn)優(yōu)先進(jìn)行解空間樹的廣度優(yōu)先搜索，不斷調(diào)整搜索方向，盡快找到問題的最優(yōu)解。

在子問題中，結(jié)點(diǎn)目標(biāo)函數(shù)值是指從該結(jié)點(diǎn)往下搜索解空間樹到達(dá)葉子結(jié)點(diǎn)使得背包獲得的最大價(jià)值，由該結(jié)點(diǎn)往下的路徑可能有多條，背包最后獲得的最大價(jià)值在解空間樹未搜索完的情況下不確定，即該結(jié)點(diǎn)的目標(biāo)函數(shù)值不確定。在EVAKNP算法中設(shè)計(jì)了一個(gè)合理的限界函數(shù)，在搜索過程中用限界函數(shù)值進(jìn)行目標(biāo)函數(shù)值的估算。先將子問題k物品集合Pi中元素（vi，wi）二元組按物品的單位重量?jī)r(jià)值進(jìn)行排序，搜索到第i層的結(jié)點(diǎn)t時(shí)，已搜索了前i-1個(gè)物品，對(duì)結(jié)點(diǎn)t的搜索過程由第i個(gè)物品及后續(xù)物品的搜索構(gòu)成，則有

前i-1個(gè)物品獲得的價(jià)值確定，后續(xù)物品的搜索過程未確定，用一個(gè)極大值進(jìn)行估算，將車輛剩余空間全部裝載成后續(xù)物品中單位重量?jī)r(jià)值最大的第i號(hào)物品。由此，限界函數(shù)可設(shè)計(jì)為：

其中，v為搜索了前i-1個(gè)物品獲得的實(shí)際價(jià)值，Ck-Ck（i-1）為車輛此時(shí)剩余空間，vi/wi為第i種物品的單位重量?jī)r(jià)值。

EVAKNP算法采用大根堆存儲(chǔ)搜索樹中生成的結(jié)點(diǎn)，堆頂結(jié)點(diǎn)的限界函數(shù)值最大。首先計(jì)算根節(jié)點(diǎn)的限界函數(shù)值，生成其左右孩子結(jié)點(diǎn)到搜索樹，優(yōu)先選取堆中（搜索樹中）限界函數(shù)值最大的結(jié)點(diǎn)（堆頂元素）進(jìn)行搜索，生成該結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)插入堆，并進(jìn)行堆調(diào)整，搜索原理在于限界函數(shù)值大的結(jié)點(diǎn)其目標(biāo)函數(shù)值也趨向于大。重復(fù)上述過程，若當(dāng)前搜索結(jié)點(diǎn)是葉子結(jié)點(diǎn)e，計(jì)算出葉子結(jié)點(diǎn)的目標(biāo)函數(shù)值（背包實(shí)際獲得的價(jià)值），如果該值大于堆中其余結(jié)點(diǎn)的限界函數(shù)值，則已找到最優(yōu)解，搜索過程結(jié)束。由式（6）限界函數(shù)的定義可知其余結(jié)點(diǎn)的搜索越往下，其目標(biāo)函數(shù)取值趨向于越小，故相較于結(jié)點(diǎn)e搜索已無(wú)意義。

由式（1）可知，本算法待求解子問題的最優(yōu)解是解空間樹中使目標(biāo)函數(shù)取最大值的葉子節(jié)點(diǎn)，在搜索過程中，為盡快獲得最優(yōu)解，可設(shè)計(jì)一個(gè)合理的搜索下界進(jìn)行搜索樹的剪枝，若結(jié)點(diǎn)限界函數(shù)值小于該下界，由該結(jié)點(diǎn)往下搜索得到的葉子結(jié)點(diǎn)都不可能是最優(yōu)解，可進(jìn)行剪枝。解空間樹中任意一個(gè)可行解均可作為下界，本算法采用貪心選擇法求得的解作為較合理的搜索下界。

例1某EVAKNP問題中，快遞車輛容量50，途經(jīng)3個(gè)快遞站點(diǎn)，第一個(gè)站點(diǎn)卸貨之后車輛剩余容量20，待裝載物品集｛（50，10），（24，6），（14，7），（5，5）｝，第二個(gè)站點(diǎn)卸貨之后車輛剩余容量16，待裝 載 物 品 集｛（10，1），（12，6），（8，2），（9，3），（6，6）｝，第三個(gè)站點(diǎn)卸貨之后車輛剩余容量14，待裝 載 物 品 集｛（18，3），（10，2），（16，4），（12，4），（6，3），（4，4）｝。原問題的解由3個(gè)子問題的解構(gòu)成，以下是子問題1的求解過程。子問題1的解空間樹見圖1，葉子結(jié)點(diǎn)中重量小于等于20的解都是可行解。

圖1 子問題1解空間樹

由貪心選擇法（優(yōu)先選擇單位重量?jī)r(jià)值大的物品）得到的搜索下界為74，生成的搜索樹見圖2，優(yōu)先選擇限界函數(shù)值ub大的結(jié)點(diǎn)搜索，ub值小于74的結(jié)點(diǎn)剪枝。

圖2 子問題1搜索樹

由搜索樹可得子問題1最優(yōu)解背包價(jià)值為74，x1-x4取值1 100，即物品1裝載，物品2裝載，物品3不裝載，物品4不裝載。

2.2 算法描述EVAKNP算法子問題的求解采用堆存儲(chǔ)搜索樹中的結(jié)點(diǎn)，堆依據(jù)結(jié)點(diǎn)的限界函數(shù)值進(jìn)行調(diào)整。首先生成并初始化根節(jié)點(diǎn)，取堆頂元素作為當(dāng)前搜索結(jié)點(diǎn)，生成其左孩子結(jié)點(diǎn)（裝載物品）及右孩子結(jié)點(diǎn)（不裝載物品），分別計(jì)算限界值，將左、右孩子結(jié)點(diǎn)插入堆并進(jìn)行堆調(diào)整。重復(fù)上述搜索過程直到當(dāng)前搜索結(jié)點(diǎn)是搜索樹的葉子結(jié)點(diǎn)。

EVAKNP（m，goos［m］［100］）

｛V=0；

while（i＜=m）

｛n=length（goods［i］）；//第i站物品數(shù)

newheap（n*n）；//申請(qǐng)堆空間

createrootnode（xnode）；//建立并初始化根節(jié)點(diǎn)

while（xnode＜n）//xnode不是搜索樹中的葉子結(jié)點(diǎn)

｛createlchildnode（ynode）；//生成當(dāng)前搜索結(jié)點(diǎn)的左孩子結(jié)點(diǎn)

bound（ynode）；//計(jì)算限界函數(shù)值

insert（heap，ynode）；//在堆中插入左孩子結(jié)點(diǎn)并調(diào)整堆

createrchildnode（znode）；//右孩子結(jié)點(diǎn)

bound（znode）；

insert（heap，znode）；

deltop（heap，xnode）；//取堆頂元素作為當(dāng)前待搜索結(jié)點(diǎn)xnode

｝

vi=xnode→v；

V+=vi；i++；

｝

｝

void bound（KNAPNODE*node，int M，goods a

［］，int n）//計(jì)算結(jié)點(diǎn)node的限界函數(shù)值

｛int i=node-＞k；//計(jì)算i-1號(hào)物品裝載情況的限界

float w=node-＞w；

float p=node-＞p；

if（node-＞w＞M）//物體重量超過背包載重量

node-＞b=0；

else

if（i＜n）

node-＞b=p+（M-w）*a［i］.p/a［i］.w；

else

node-＞b=p；

｝

3 算法分析及實(shí)驗(yàn)

分支限界法的實(shí)質(zhì)是在解空間樹中優(yōu)先選擇限界函數(shù)值大的結(jié)點(diǎn)進(jìn)行搜索，由于解空間樹的結(jié)點(diǎn)具有指數(shù)階，在最壞情況下，算法時(shí)間復(fù)雜度為指數(shù)階。在EVAKNP算法中，站點(diǎn)數(shù)記為m，各站點(diǎn)待裝載物品最大數(shù)記為n，則算法在最壞情況下的時(shí)間復(fù)雜度為O（m2n），算法在最好情況下搜索過程持續(xù)沿一個(gè)分支往下進(jìn)行，其時(shí)間復(fù)雜度為O（mn）。對(duì)于具體的問題實(shí)例，很難預(yù)測(cè)其搜索行為，無(wú)法判斷能否在合理時(shí)間范圍內(nèi)求解，故很難估算EVAKNP算法在平均情況下的時(shí)間復(fù)雜度，可記為O（m2n）。由于解空間樹中結(jié)點(diǎn)的搜索是跳躍性的，在每個(gè)結(jié)點(diǎn)中需存儲(chǔ)從根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的搜索路徑，算法還需要維護(hù)搜索樹待處理結(jié)點(diǎn)表T，并且需要快速?gòu)谋鞹中查找限界值大的結(jié)點(diǎn)，這些都增加了算法的空間耗費(fèi)。最壞情況下，表T中結(jié)點(diǎn)數(shù)是指數(shù)階的，故本算法的空間復(fù)雜性為指數(shù)階。

實(shí)驗(yàn)數(shù)據(jù)集由隨機(jī)合成，實(shí)驗(yàn)環(huán)境為Visual Studio 2012，編程采用C++語(yǔ)言。圖3是站點(diǎn)數(shù)5，物品數(shù)分別為26、27、28、29、30的最優(yōu)解。表1為站點(diǎn)數(shù)10，各站物品數(shù)均取10、15、20、25、30、35下算法運(yùn)行時(shí)間比較，由表中數(shù)據(jù)可知在站點(diǎn)數(shù)相同的情況下，算法運(yùn)行時(shí)間和物品數(shù)之間不構(gòu)成函數(shù)關(guān)系，驗(yàn)證了分支限界法在最優(yōu)解求解過程中搜索結(jié)點(diǎn)選擇的不確定性。最優(yōu)解的搜索過程往往與車輛容量、物品構(gòu)成、物品數(shù)等均有關(guān)系，在車輛容量、站點(diǎn)數(shù)、物品數(shù)相同的情況下，物品構(gòu)成不同，其搜索過程不同，算法運(yùn)行時(shí)間也會(huì)不一樣。表2是在站點(diǎn)數(shù)、車輛容量、物品數(shù)均一致（10站，車輛容量150，每站20個(gè)物品）算法5次運(yùn)行時(shí)間比較，由于每次物品重量及價(jià)值隨機(jī)生成，物品構(gòu)成不同，算法運(yùn)行時(shí)間均不同。

表1 不同數(shù)據(jù)規(guī)模EVAKNP算法時(shí)間性能

表2 相同數(shù)據(jù)規(guī)模EVAKNP算法時(shí)間性能

圖3 EVAKNP問題最優(yōu)解

4 結(jié)語(yǔ)

背包問題求解可采用蠻力法、貪心法、動(dòng)態(tài)規(guī)劃法、分支限界法等，蠻力法時(shí)間復(fù)雜度較高，貪心法可求近似最優(yōu)解，動(dòng)態(tài)規(guī)劃法〔7〕和分支限界法求最優(yōu)解。本文提出一個(gè)基于堆結(jié)構(gòu)帶限界函數(shù)的EVAKNP算法，實(shí)驗(yàn)結(jié)果表明該算法可以求解快遞車輛配裝問題最優(yōu)解，算法在不同數(shù)據(jù)規(guī)模下具有有效的時(shí)間性能，由于分支限界法的搜索特點(diǎn)，算法在相同的數(shù)據(jù)規(guī)模、不同的數(shù)據(jù)集上具有不同的時(shí)間性能。