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

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

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

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

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

0 引言

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

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

1 裝載問題

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

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

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

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

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

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

（設兩輛貨車分別為A、B，其對應最大載重量為WA、WB）

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

貨車A 的實際裝載量：

貨車B 的實際裝載量：

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

待裝車的貨箱總重量：

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

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

表1 假設1 貨車與貨箱的信息

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

表3 假設2 貨車與貨箱的信息

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

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

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

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

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

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

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

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

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

采用優(yōu)先隊列分支限界法解決多貨車多貨箱裝載問題中的限界條件為：結(jié)點裝載上界大于當前最優(yōu)方案，并且從該結(jié)點到根結(jié)點路徑對應的裝載方案，其裝載量不超過當前裝載貨車的載重量，且結(jié)點的裝載上界等于當前裝載貨車已裝載貨箱重量加上即將被裝載物品的重量；當前最優(yōu)方案是指從初始到當前所有狀態(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)時，為了降低時間復雜度，當找到一種可行裝載方案時就退出循環(huán)；執(zhí)行第二層循環(huán)時要搜索到解空間樹葉子結(jié)點時才退出循環(huán)。

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

2.4 算法實現(xiàn)

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

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

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

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

2.5 算法時間復雜度

本文在采取遍歷貨車裝載序列的同時，采用找到一種符合條件的裝載順序就退出循環(huán)的方法來降低時間復雜度，當遍歷到最后一個貨車次序才找到可行解時，算法的時間復雜度最大，值是O(log(m!*m*n))。其中m為貨車數(shù)量，n為貨箱數(shù)量，m!為遍歷貨車的所有裝載順序。當按照第一個貨車次序進行裝載就能找到可行解時，算法的時間復雜度最小，值為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++程序設計語言實現(xiàn)算法，運行結(jié)果如表6 所示。從表6 可以看出，在對貨車的重量序列進行全排列之后，算法在第一次遍歷該排列時（即貨車從小到大的序列）不能找到裝載方案。但在遍歷過程中存在可以裝載所有貨物的序列。

表5 貨車與貨箱的信息

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

4 結(jié)語

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