付志英，呂夢(mèng)鴿，王谷青，賀晴，王蒙，武杰

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

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

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

0 引言

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

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

1 裝載問(wèn)題

1.1 多貨車(chē)多貨箱裝載問(wèn)題定義

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

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

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

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

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

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

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

貨車(chē)A 的實(shí)際裝載量：

貨車(chē)B 的實(shí)際裝載量：

裝載序列二：按照先裝B 后裝A 的順序裝車(chē)，貨車(chē)B 的實(shí)際裝載量，即：

待裝車(chē)的貨箱總重量：

此時(shí)，貨車(chē)A 一定能裝下剩余貨箱。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 裝載一輛貨車(chē)的解空間樹(shù)

2.3 算法流程圖

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

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

2.4 算法實(shí)現(xiàn)

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

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

（2）堆結(jié)點(diǎn)類，用來(lái)創(chuàng)建堆結(jié)點(diǎn)：

（3）大堆類，用來(lái)創(chuàng)建一個(gè)大堆對(duì)象，在對(duì)大堆進(jìn)行插入或刪除堆結(jié)點(diǎn)時(shí)，調(diào)整堆型以形成最大頂堆：

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

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

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

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)例證

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

表5 貨車(chē)與貨箱的信息

表6 貨車(chē)的一種裝載方案與可行性驗(yàn)證

4 結(jié)語(yǔ)

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