付志英，呂夢鴿，王谷青，賀晴，王蒙，武杰

（陜西師范大學(xué)計算機科學(xué)學(xué)院，西安 710119）

由于車輛配備有限而快件量爆炸增長，使得物流企業(yè)快件派送的服務(wù)質(zhì)量和派送時效無法有效滿足需求。為了解決該問題，提出一種基于優(yōu)先隊列分支限界思想的算法并應(yīng)用于多貨車多貨箱裝載問題的求解。該方法利用貪心策略，采用分階段分支限界方法裝載每輛貨車。實例分析表明應(yīng)用該算法可以獲得多貨車多貨箱問題的可行方案。

優(yōu)先隊列分支限界法；貪心策略；分階段決策；裝載問題

0 引言

2018年，“雙11”落下帷幕，各方面數(shù)據(jù)再次刷新紀錄，當(dāng)日物流訂單量突破10 億大關(guān)。因此，在車輛配備有限而快件量爆炸增長的情況下，合理有效地對快件進行裝載是應(yīng)對當(dāng)前物流需求，提高配送效率的核心問題。

本文針對多輛貨車、多個貨箱的裝載問題，首先對該問題進行了分析。當(dāng)使用兩輛貨車進行裝載時，貨車的裝載次序與裝載可行性無關(guān)；當(dāng)貨車數(shù)量大于2時，貨車的裝載次序與裝載可行性具有很大相關(guān)性。其次，針對這一問題，本文采用貪心策略和優(yōu)先隊列分支限界法分階段對多貨車多貨箱裝載問題進行建模求解。最后，實驗表明，本文所提算法可以有效搜索到多輛貨車多個貨箱裝載問題的可行解。

1 裝載問題

1.1 多貨車多貨箱裝載問題定義

設(shè)現(xiàn)有m輛貨車來裝載n個貨箱（貨箱不可拆），第i輛貨車的最大載重量為Ci(i=1,2,…,m)，第j個貨箱的重量是Wj(j=1,2,…,n)?，F(xiàn)在需要求解一種裝載方案使得全部貨箱均裝入貨車。易證明，若給定的裝載問題有，可通過下面的方案得到可行解：

（1）首先將第一輛貨車盡可能裝滿；

（2）然后從剩余車輛中選擇一輛車，并盡可能將其裝滿；

（3）重復(fù)步驟（2）直到所有貨箱均裝下。

當(dāng)只有兩輛貨車時，其裝載序列最多有兩種，且通過數(shù)學(xué)證明可以發(fā)現(xiàn)貨車的裝載次序與裝載可行性無關(guān)。即若采用一種貨車的裝載序列可以裝下，則另一種裝載序列也可以裝下。證明如下：

（設(shè)兩輛貨車分別為A、B，其對應(yīng)最大載重量為WA、WB）

裝載序列一：先裝A 后裝B 有可行方案，即：

貨車A 的實際裝載量：

貨車B 的實際裝載量：

裝載序列二：按照先裝B 后裝A 的順序裝車，貨車B 的實際裝載量，即：

待裝車的貨箱總重量：

此時，貨車A 一定能裝下剩余貨箱。

綜上所述，當(dāng)貨車數(shù)為2 時，貨車的裝載次序與裝載可行性無關(guān)。然而，對多于兩輛貨車的裝載問題，其裝載序列有多種，且貨車的裝載次序與裝載可行性有關(guān)。即若采用一種貨車的裝載序列不能裝下貨箱，但是可能存在另一種裝載序列可以裝下貨箱。在此基礎(chǔ)上，我們提出了兩種假設(shè)，即：①按照貨車載重量從大到小的順序裝載，若不能完全裝載貨箱，則按其他的貨車順序裝載貨箱都不能裝下；②按照貨車載重量從小到大的順序裝載，若不能完全裝載貨箱，則按其他的貨車順序裝載貨箱都不能裝下。經(jīng)過實例驗證（如表1-4），我們發(fā)現(xiàn)存在不符合這兩個假設(shè)的情況。故，對于多貨車多貨箱裝載問題（貨車數(shù)＞2），貨車裝載序列與裝載可行性有關(guān)。

表1 假設(shè)1 貨車與貨箱的信息

表2 假設(shè)1 貨車的兩種裝載方案與可行性驗證

表3 假設(shè)2 貨車與貨箱的信息

表4 假設(shè)2 貨車的兩種裝載方案與可行性驗證

1.2 裝載問題數(shù)學(xué)模型

根據(jù)1.1 小節(jié)所述，解決問題的關(guān)鍵是在一種特定的貨車裝載序列下，裝載每一輛貨車時裝盡可能多的貨箱。因此，裝載每一輛貨車的過程可以看作一系列的決策過程，即在裝載每一輛貨車時決策哪些貨箱要裝車，哪些貨箱不裝。由此，求解多貨車多貨箱裝載問題，就是在一種貨車裝載順序下，對于m輛貨車n個貨箱 且找 出 一 個m元 向 量，其 中1 ≤k≤n,1 ≤i≤m（k,i為整數(shù)，1 表示裝載該貨箱，0 表示不裝載該貨箱）。多貨車多貨箱可表示為如下0-1 整數(shù)規(guī)劃數(shù)學(xué)模型：

其中,fi為第i輛貨車的裝載貨箱空閑空間最小的目標函數(shù)，即盡可能裝滿每一輛貨車。

2 利用優(yōu)先隊列分支限界法解決多輛車多貨箱裝載問題

2.1 裝載問題數(shù)學(xué)模型

優(yōu)先隊列分支限界法屬于一種常用的樹型搜索算法，其中限界是在分支搜索的基礎(chǔ)上加入結(jié)點限制，對以不滿足條件的結(jié)點為根的分支子樹不再進行搜索，以此縮小搜索范圍，提高搜索效率；優(yōu)先隊列是對活結(jié)點表進行優(yōu)先隊列組織，每次擴展結(jié)點都從當(dāng)前活結(jié)點表中選擇一個優(yōu)先級最高（最有利）的結(jié)點，使每一步搜索向最優(yōu)解靠近。當(dāng)擴展到葉結(jié)點時，就得到一個最優(yōu)解。優(yōu)先隊列使用數(shù)據(jù)結(jié)構(gòu)“堆（heap）”實現(xiàn)，每次都取優(yōu)先級最高的元素即堆頂元素作為下一個擴展節(jié)點。如圖1 為裝載一輛貨車時，使用優(yōu)先隊列分支限界法進行分析。

2.2 裝載問題數(shù)學(xué)模型

由1.1 小節(jié)裝載問題定義可知，多貨車多貨箱裝載問題屬于多輛貨車的裝載組合最優(yōu)化問題。由于貨車數(shù)量、每輛貨車的載重量和貨箱數(shù)量、每個貨箱的重量都不確定，導(dǎo)致整體可行裝載方案不易求出。故，當(dāng)有m輛貨車時，對給定的一種貨車裝載序列分為m個階段依次進行裝載，盡可能將每一輛貨車裝滿，且在裝載每一輛貨車時，采用優(yōu)先隊列分支限界法搜索貨箱裝載的解空間樹。當(dāng)貨車的載重量不同時，多輛貨車存在多種裝載序列，且多輛貨車裝載方案可行性與貨車裝載序列有關(guān)，因此，該問題就轉(zhuǎn)化為遍歷所有貨車裝載序列，搜索可行解的問題。本文為了提高搜索的效率，選擇采用具有樹型搜索結(jié)構(gòu)的優(yōu)先隊列分支限界法來解決多貨車多貨箱裝載問題，并要求找到一個可行解即停止搜索。

采用優(yōu)先隊列分支限界法解決多貨車多貨箱裝載問題中的限界條件為：結(jié)點裝載上界大于當(dāng)前最優(yōu)方案，并且從該結(jié)點到根結(jié)點路徑對應(yīng)的裝載方案，其裝載量不超過當(dāng)前裝載貨車的載重量，且結(jié)點的裝載上界等于當(dāng)前裝載貨車已裝載貨箱重量加上即將被裝載物品的重量；當(dāng)前最優(yōu)方案是指從初始到當(dāng)前所有狀態(tài)中，能夠裝載貨箱的最大總重量。

圖1 裝載一輛貨車的解空間樹

2.3 算法流程圖

總體上來看，本算法的流程主要由兩層循環(huán)嵌套實現(xiàn)，第一層循環(huán)調(diào)用一個全排列函數(shù)（next_permutation）對所有貨車裝載序列進行遍歷；第二層循環(huán)調(diào)用自己實現(xiàn)的一個最大裝載函數(shù)（MaxLoading）對第一層循環(huán)給定的裝載序列分為m個階段依次進行裝載。執(zhí)行第一層循環(huán)時，為了降低時間復(fù)雜度，當(dāng)找到一種可行裝載方案時就退出循環(huán)；執(zhí)行第二層循環(huán)時要搜索到解空間樹葉子結(jié)點時才退出循環(huán)。

圖2 優(yōu)先隊列分支限界解決多輛貨車多貨箱裝載問題流程圖

2.4 算法實現(xiàn)

為了實現(xiàn)問題求解，本文采用C++面向?qū)ο蟪绦蛘Z言來進行計算機求解。其中，本文所定義的關(guān)鍵類如下：

（1）堆結(jié)點關(guān)系類，用于記錄活結(jié)點的裝載上界，父親結(jié)點等信息：

（2）堆結(jié)點類，用來創(chuàng)建堆結(jié)點：

（3）大堆類，用來創(chuàng)建一個大堆對象，在對大堆進行插入或刪除堆結(jié)點時，調(diào)整堆型以形成最大頂堆：

2.5 算法時間復(fù)雜度

本文在采取遍歷貨車裝載序列的同時，采用找到一種符合條件的裝載順序就退出循環(huán)的方法來降低時間復(fù)雜度，當(dāng)遍歷到最后一個貨車次序才找到可行解時，算法的時間復(fù)雜度最大，值是O(log(m!*m*n))。其中m為貨車數(shù)量，n為貨箱數(shù)量，m!為遍歷貨車的所有裝載順序。當(dāng)按照第一個貨車次序進行裝載就能找到可行解時，算法的時間復(fù)雜度最小，值為O(log(m*n))。

3 算例及結(jié)果分析

3.1 實驗環(huán)境

本文算法的實驗環(huán)境為Windows 10 64 位操作系統(tǒng)（CPU 為2.30GHz，內(nèi)存4G）并采用CodeBlocks 軟件進行編譯運行。

3.2 實驗例證

貨車和貨箱數(shù)量及載重量信息如表5 所示。利用C++程序設(shè)計語言實現(xiàn)算法，運行結(jié)果如表6 所示。從表6 可以看出，在對貨車的重量序列進行全排列之后，算法在第一次遍歷該排列時（即貨車從小到大的序列）不能找到裝載方案。但在遍歷過程中存在可以裝載所有貨物的序列。

表5 貨車與貨箱的信息

表6 貨車的一種裝載方案與可行性驗證

4 結(jié)語

本文采用C++面向?qū)ο蟪绦蛘Z言，利用貪心策略和優(yōu)先隊列分支限界法來求解多貨車多貨箱裝載問題。實驗實例表明，對于包含任意數(shù)目和載重量的貨車，及任意數(shù)目和重量貨箱的貨車裝載問題，本文算法不僅可以判斷該問題是否有具有可行裝載方案，還可以對滿足裝載可行性的問題搜索到相應(yīng)的可行裝載方案。