程全明+趙揚

[摘 要] 針對一類需要進行貨物往返運輸?shù)倪\輸問題，建立了貨物裝箱模型，并設(shè)計了一種貨物的拆分策略。貨物裝箱模型考慮了中心站點貨物數(shù)量和各個配送站點貨物數(shù)量，使得運輸車輛可以進行往返運輸。貨物的拆分策略對數(shù)量比較多的貨物進行拆分，保證了貨物裝入運輸車輛的可運輸性和其他運輸車輛的滿載性。最后對所提出的模型和策略進行了實驗。

[關(guān)鍵詞] 裝箱問題；貨物分拆；裝卸貨

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 23. 082

[中圖分類號] F511.41 [文獻標(biāo)識碼] A [文章編號] 1673 - 0194（2016）23- 0153- 04

0 引 言

裝箱問題（Bin Packing Problem）廣泛存在于服務(wù)業(yè)、運輸工業(yè)、建筑工業(yè)、金屬制造業(yè)等領(lǐng)域，是許多重要實際優(yōu)化問題的基礎(chǔ)。在實際的貨物運輸過程中，對于貨物如何在運輸車輛上分配裝載，裝箱問題得到了廣泛的應(yīng)用。

裝箱問題屬于典型的NP難問題，難以精確求解，只能得到問題的近似解，在某些極端情況下，結(jié)果很不理想。在實際的貨物裝載過程中，很多貨物的總量由于超出了運輸工具的容量或者本身數(shù)量較大，因此無法直接使用裝箱問題的模型。

本文針對現(xiàn)有的貨物裝配問題的實際情況，結(jié)合裝箱問題模型的思想，提出一種考慮貨物裝卸的貨物分拆裝箱策略。該裝箱策略首先考慮運輸車輛在每個站點卸貨和裝貨的總運量來確定運輸車輛的數(shù)量，然后通過貨物組合模型對貨物進行裝箱分配，再對數(shù)量較大的貨物進行拆分，使得車輛能夠滿載運輸。

1 問題描述

本文研究的運輸系統(tǒng)如下：在整個運輸系統(tǒng)中，有一個中心站點和若干配送站點。中心站點可以是倉庫或者加工中心，對各種貨物進行儲存或者加工操作。配送站點是提供服務(wù)的地點，貨物從中心站點被運送到各個配送站點。在每個配送站點都有需要運回中心站點的貨物，每輛車在該站點將需要運回中心站點的貨物裝車后，去往下一個配送點，最后所有的配送站點都經(jīng)過后，運輸車輛返回中心站點。

運輸貨物的車輛都集中停放在中心站點。每次運輸過程中，管理者通過管理信息系統(tǒng)收集中心站點中對應(yīng)每個配送站的貨物的數(shù)據(jù)，以及每個配送站中貨物的數(shù)據(jù)。根據(jù)這些數(shù)據(jù)，管理者制定車輛裝配貨物的方案以及每個車輛經(jīng)過的配送站點。

為了節(jié)約成本，運輸車輛每次運輸要求完成一次性運送和裝卸任務(wù)，即運輸車輛從中心站點出發(fā)，裝上貨物后，一次性的經(jīng)過貨物需要卸載的配送站點且只經(jīng)過一次。每經(jīng)過一個配送站點的時候，運輸車輛首先在該配送站點卸下該站點的貨物，然后裝上該配送站點需要運回中心站點的貨物。然后，運輸車輛去往下個配送站點。全都結(jié)束后，運輸車輛返回中心站點。

這種衣物配送計劃需要考慮需要卸下的貨物和需要裝載的衣物之間的關(guān)系，能夠是的使得貨物卸載后在運輸車輛上有足夠的空間來盛放后來裝載上來的貨物。

2 模型

2.1 符號

模型中各個符號說明如下：

CSi，配送站點i；

CsiNum，配送站點i中存放的待運輸?shù)呢浳飻?shù)量；

WS，中心站點；

WsiNum，中心站點WS中對應(yīng)于配送站點i的待運輸貨物數(shù)量；

VC，運輸車輛能夠盛裝的貨物的最大數(shù)量；

TSnum，WS的貨物數(shù)量總和；

TFnum，CSi的貨物數(shù)量總和。

2.2 貨物裝箱模型

對于N個配送站，x表示模型的一組解，其中X=（X1，X2，…，XN）。在這里xi表示配送站點i被選中的狀態(tài)。在模型中，Xi表示運輸車輛是否經(jīng)過CSi，即是否盛裝該配送站點的貨物。如果運輸車輛經(jīng)過CSi則Xi=1；不經(jīng)過CSi則Xi=0。

當(dāng)Xi=1時，如果運輸車輛經(jīng)過CSi，則說明在WS中如果有對應(yīng)CSi的待運送貨物，則需要將其裝上運輸車輛，若沒有則不裝載；同時，在CSi中如果有待運輸?shù)呢浳?，則需要將其送上運輸車輛，若沒有則不裝載。

對于每次裝載運輸車上的貨物的數(shù)量總和都不能超過運輸車輛容量。因此從中心站點WS運出貨物的總和不能超過運輸車輛容量；從各個站點CSi運回中心站點WS貨物的總和不能超過運輸車輛容量

模型的目標(biāo)函數(shù)根據(jù)實際的貨物數(shù)量決定。如果由于WS貨物數(shù)量多于CSi的貨物數(shù)量，則目標(biāo)函數(shù)為WS貨物數(shù)量優(yōu)先滿載；相反如果CSi的貨物數(shù)量多于WS貨物數(shù)量，則目標(biāo)函數(shù)為CSi貨物數(shù)量優(yōu)先滿載。下文表示為CSi貨物數(shù)量優(yōu)先滿載。

考慮貨物裝卸的貨物分拆裝箱策略中的一個重要問題是處理WS中WsiNum和每個CSi中CsiNum之間的關(guān)系。

對于運輸車輛的運輸方案來說，為了保證運輸車輛一次性經(jīng)過每個CSi，需要在CSi先卸貨，同時在該CSi裝貨，需要考慮WsiNum和CsiNum之間的關(guān)系：

（1）當(dāng)一個車輛所運輸?shù)乃蠧Si的貨物，有WsiNum>CsiNum，則表示卸下的貨物比裝上的貨物多，不會發(fā)生車上剩余空間無法容納需裝載貨物的情況；

（3）當(dāng)一個車輛所運輸?shù)乃蠧Si的貨物，既有WsiNumCsiNum，則需要首先對WsiNum>CsiNum的進行貨物的裝卸，然后再對WsiNum

2.3 貨物的拆分策略

首先根據(jù)待運貨物的情況確定最少的運輸車輛數(shù)量Max{「TSnum/VC，TFnum/VC}。然后通過分組模型（2.2）來獲得分組結(jié)果，如果分組的數(shù)量與最少的運輸車輛數(shù)量相同，則分組結(jié)束；否則，則需要對某些待送數(shù)量較多的站點的貨物拆分到其他車輛上，使得最后的車輛總數(shù)等于最少的運輸車輛數(shù)量。

因為待送貨物數(shù)量較多的站點不容易與其他站點組合，所以從未被裝車的貨物中選擇數(shù)量最多的貨物進行拆分。

分組后待送貨物的總數(shù)如果等于車輛容量，則該組分配完畢。如果分組后待送貨物的總數(shù)如果小于車輛容量，則可以從未被裝車的貨物中選擇數(shù)量最多的貨物進行拆分，使得車輛運輸滿負荷。

3 實驗

本實驗說明2.2中所提出的模型和算法的效果，模型程序的實現(xiàn)工具是Matlab。程序運行環(huán)境為Intel Core2 Duo 2.2 GHz/2 GB RAM/Windows XP。實驗所需要數(shù)據(jù)為隨機產(chǎn)生如表1所示。

基于實驗數(shù)據(jù)表1，通過模型2.2計算，實驗結(jié)果如表2所示。前面進行裝車的貨物，由于存在工作站貨物數(shù)量=0或者衣物收集站貨物數(shù)量=0的情況，所以在組合的時候，可以能夠容納較多數(shù)量的CSi。 從第3組開始后面的組合時，由于沒有了上述前提，因此每個車輛所盛裝的CSi的數(shù)量逐漸減少。

4 結(jié) 語

本文建立了貨物裝箱模型，并設(shè)計了一種貨物的拆分策略。貨物裝箱模型考慮了中心站點貨物數(shù)量和各個配送站點貨物數(shù)量，使得運輸車輛可以進行往返運輸。貨物的拆分策略對數(shù)量比較多的貨物進行拆分，保證了貨物裝入運輸車輛的可運輸性和其他運輸車輛的滿載性。本文提出的貨物裝箱模型避免了傳統(tǒng)裝箱問題求解困難，具有較強的實用性，可以為實際的貨物運輸裝箱計劃提供參考。

主要參考文獻

[1]Dyckhoff H.A Typology of Cutting and Packing Problems[J]. European Journal of Operational Research ， 1990， 44（2）：145-159

[2]李敬峰，葉艷，傅惠.面向貨物裝卸需求的越庫倉門分配和貨車排序[J].工業(yè)工程，2016（2）.

[3]MIAO Z，CAI S，XU D. Applying an Adaptive Tabu Search Algorithm to Optimize Truck-dock Assignment in the Crossdock Management System[J].Expert Systems with Applications，2014，41（1） ： 16-22.

[4]余小兵. 基于改進粒子群算法的多目標(biāo)應(yīng)急物資調(diào)度[J]. 工業(yè)工程， 2014， 17（ 3） ： 18-21.

[5]KUO Y.Optimizing Truck Sequencing and Truck Dock Assignment in a Cross Docking System[J].Expert Systems with Applications，2013，40（14）：5532-5547.

[6]邵飛牛.一維裝箱問題啟發(fā)式算法的設(shè)計與分析[D].沈陽：東北大學(xué)，2013.

[7]LEE K，KIM B S，JOO C M. Genetic Algorithms for Doorassigning and Sequencing of Trucks at Distribution Centers for the Improvement of Operational Performance[J]. Expert Systems with Applications，2012，39（1）：12975-12973.

[8]湯巖.遺傳算法在裝箱問題中的應(yīng)用[D].大連：大連海事大學(xué)，2005.

[9]LIAO T W，EGBELUA P G，CHANG P C. Simultaneous Dock Assignment and Sequencing of Inbound Trucks under a Fixed Outbound Truck Schedule in Multi-door Cross Docking Operations[J].International Journal of Production Economics， 2013， 141 （1）：212-229.

[10]A Bettinelli， A Ceselli， G Righini.A Branch-and-price Algorithm for the Variable Size Bin Packing Problem with Minimum Filling Constraint [J].Annals of Operations Research，2010，179（1）：221-241.

[11]杜少波，張國基，劉清. 一種新的多約束尺寸可變的裝箱問題[J].計算機工程與應(yīng)用，2011，47（19）： 242-244

[12]虞才珠，邵志清.一種基于最優(yōu)個體保存策略的服務(wù)組合優(yōu)化選取方法[J].華東理工大學(xué)學(xué)報：自然科學(xué)版，2010（5）.