求解快遞車輛配裝問題分支限界算法

趙秦怡，趙榆琴

（大理大學數(shù)學與計算機學院，云南大理 671003）

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

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

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

1 EVAKNP問題描述

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

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

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

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

2 EVAKNP算法描述

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

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

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

其中，v為搜索了前i-1個物品獲得的實際價值，Ck-Ck（i-1）為車輛此時剩余空間，vi/wi為第i種物品的單位重量價值。

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

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

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

圖1 子問題1解空間樹

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

圖2 子問題1搜索樹

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

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

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

｛V=0；

while（i＜=m）

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

newheap（n*n）；//申請堆空間

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

while（xnode＜n）//xnode不是搜索樹中的葉子結點

｛createlchildnode（ynode）；//生成當前搜索結點的左孩子結點

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

insert（heap，ynode）；//在堆中插入左孩子結點并調整堆

createrchildnode（znode）；//右孩子結點

bound（znode）；

insert（heap，znode）；

deltop（heap，xnode）；//取堆頂元素作為當前待搜索結點xnode

｝

vi=xnode→v；

V+=vi；i++；

｝

｝

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

［］，int n）//計算結點node的限界函數(shù)值

｛int i=node-＞k；//計算i-1號物品裝載情況的限界

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 算法分析及實驗

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

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

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

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

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

4 結語

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