一類多車、多貨物運輸配送問題新的簡便解法

賈春玉

(寧波工程學(xué)院 經(jīng)濟與管理學(xué)院，浙江 寧波 315211)

兩個城市(或區(qū)域)之間,多車、多貨物可混裝運輸配送問題是物流行業(yè)中常見的問題.單一貨物或單一型號貨車裝載、運輸配送問題已有很多研究成果，但多車、多貨物可混裝運輸配送問題研究成果較少，目前只能查到為數(shù)不多的相關(guān)文獻,針對這種復(fù)雜的組合優(yōu)化問題，尚無有效簡便的規(guī)劃解法.現(xiàn)有相關(guān)單一貨物或單一型號貨車裝載運輸問題的主要解法為規(guī)劃解法[1-2]和人工智算法[3-6].規(guī)劃解法在問題規(guī)模小時比較有效，規(guī)模大時不一定有效且會發(fā)生“組合爆炸”，影響其運用和推廣；人工智算法繁瑣、求解時間長，有些方法易陷入局部最優(yōu)、具有早熟、停滯的缺點，不如規(guī)劃求解法的優(yōu)化程度高.物流運輸配送行業(yè)的競爭激烈、利潤率低，如何降低成本，是人們早已關(guān)注的問題.以往都是憑經(jīng)驗配載裝車、安排運輸配送車輛，優(yōu)化程度不高.為了解決這些問題，本文提出一種能夠有效避免“組合爆炸”而簡便、實用、易于掌握的規(guī)劃問題新解法.

1 多車、多貨物可混裝運輸配送問題及其數(shù)學(xué)模型

1.1 多車、多貨物可混裝運輸配送問題描述

設(shè)不同型號的運輸配送車輛為Vi(i=1，2，…，n)；兩點之間不同型號車輛運費為Fi(i=1，2，…，n)，裝卸、理貨費假設(shè)每個型號貨車均相等，或已包含在運費中，因此不再考慮；不同型號的運輸配送車輛載重為ZWi(i=1，2，…，n)；不同規(guī)格的待運貨物單件質(zhì)量為DWh(h=1，2，…，m)，貨物容重比遠(yuǎn)小于貨車容重比，屬于“重貨”，所以不考慮體積問題；每種貨物需要運輸配送數(shù)量為Qh(h=1，2，…，m).現(xiàn)需作出運輸配送計劃，使總的運費最低.

1.2 多車、多貨物可混裝運輸配送問題的數(shù)學(xué)模型

1.2.1 單獨使用一種車輛的數(shù)學(xué)模型

(1)

1.2.2 組合優(yōu)化各種車輛的數(shù)學(xué)模型

(2)

2 新的簡便解法采取的主要措施

2.1 問題規(guī)模較小時采取的主要措施與解法

解決規(guī)模較小問題時,首先給出每種型號貨車對各種貨物的可行配裝方案,貨物質(zhì)量最小的最大可行配裝方案數(shù)為k,其余貨物配裝方案數(shù)小于等于k；然后按最大可行配裝方案數(shù)k列出各種配裝組合方案,不足k個方案的按貨物裝載數(shù)量為0計算；最后分別按照數(shù)學(xué)模型(1)式和數(shù)學(xué)模型(2)式,借助Excel軟件確定相應(yīng)規(guī)劃的求解公式，求解即可.

確定可行配裝方案的步驟是：首先分別計算每種貨物在各種車型車輛上的最大裝載數(shù)量ZKi，即每種型號車輛載重除以貨物單件質(zhì)量(ZKi=[ZWi/DWh]1)，向下取整(這里符號[ ]1代表向下取整)；然后確定最小單件貨重的貨物配裝方案，可用Excel軟件編輯相應(yīng)計算公式，求出組合質(zhì)量和剩余載重，也可用Excel軟件的規(guī)劃求解功能，得到優(yōu)化組合方案后，參考各種貨物不同裝載數(shù)量，給出可行優(yōu)化組合方案，可行優(yōu)化組合方案取舍的標(biāo)準(zhǔn)是剩余載重小于貨物最小單件質(zhì)量；最后確定其他貨物的配裝方案.

2.2 問題規(guī)模較大時采取的主要措施與解法

2.2.1 問題規(guī)模較大時采取的主要措施

影響該類問題規(guī)模的主要因素有如下3個：一是配裝組合方案個數(shù)(10個以上定義為大)；二是貨物數(shù)量，貨物數(shù)量越多(30 t以上定義為多)，則需要車輛越多,規(guī)劃求解組合方案數(shù)越大；三是車輛型號的多少(5種以上定義為多).這類問題是復(fù)雜組合優(yōu)化問題，這3個因素綜合作用會產(chǎn)生“組合爆炸”，使組合數(shù)呈幾何級數(shù)增長、膨脹.問題規(guī)模大時將大大降低規(guī)劃求解的有效性，甚至表現(xiàn)為不可行.為了克服這一弊端，可從三方面采取措施.

(1)選擇代表性好的優(yōu)化組合方案，減少配裝方案數(shù)量.貨物單件質(zhì)量與車輛載重之比越小，配裝貨物組合方案數(shù)就越多.當(dāng)配裝組合方案眾多時，在全部組合方案中求最優(yōu)解是不明智的，有時在規(guī)定時間內(nèi)也無法求解.代表性好的優(yōu)化組合方案是指保證裝下各種貨物且優(yōu)化程度高的配裝方案.可通過規(guī)劃求解，在保證每種貨物裝載件數(shù)大于ZKi的較大(如70%以上)和小于較小(如15%以下)的比例約束下，給出優(yōu)化組合方案.這樣可有效克服“組合爆炸”弊端.

(2)調(diào)整編制計劃策略，減少待運貨物總質(zhì)量.待運貨物總質(zhì)量是影響配裝方案組合數(shù)量的因素之一，總質(zhì)量越大則配裝方案組合數(shù)量越多.調(diào)整編制計劃策略，減少待運貨物總質(zhì)量，如通過縮短規(guī)劃求解時間跨度、把眾多貨物分成小批量編制計劃等策略，縮小待運貨物總質(zhì)量，能夠有效克服“組合爆炸”弊端.

(3)科學(xué)取舍車輛種類，減少車輛種類數(shù).車輛種類數(shù)n是影響該類問題規(guī)模的重要因素之一.可根據(jù)待運貨物總質(zhì)量，科學(xué)選擇三四種車型.貨物數(shù)量多、總質(zhì)量大時，優(yōu)先選取幾種載重大的車型，否則，選擇小車型.這樣可有效克服“組合爆炸”弊端.

2.2.2 問題規(guī)模較大時采取的解法

為了提高優(yōu)化程度, 首先適當(dāng)調(diào)整每種貨物裝載件數(shù)大于ZKi的較大百分比和小于較小的百分比的比例,獲得幾組可行優(yōu)化組合方案；然后分別規(guī)劃求解,擇優(yōu)作為最終近似最優(yōu)解,通?？色@得理想的近似最優(yōu)解.

3 計算實例

3.1 實例1

某配送中心，編制2 d運輸配送計劃，現(xiàn)有載重15 t、10 t和8 t的車輛可供使用，分別按單車運費660元、580元和500元運送3種重貨，單件貨物質(zhì)量分別為3 t、4 t和5 t，需要運送貨物數(shù)量(簡稱運量)分別為22件、29件和21件，問最低的總運費為多少元？

解:該問題規(guī)模比較小，可直接求解.

3.1.1 求單獨用15 t車運送3種貨物的最優(yōu)解

(3)

表1 用15 t車裝載3種貨物(問題規(guī)模較小)的配裝方案 件

3.1.2 求單獨用10 t車運送3種貨物的最優(yōu)解

(4)

表2 用10 t車裝載3種貨物(問題規(guī)模較小)的配裝方案 件

3.1.3 求單獨用8 t車運送3種貨物的最優(yōu)解

(5)

表3 用8 t車裝載3種貨物(問題規(guī)模較小)的配裝方案 件

3.1.4 求3種車組合優(yōu)化運送3種貨物的最優(yōu)解

根據(jù)表1、表2、表3及其他相關(guān)數(shù)據(jù)，3種車組合優(yōu)化運送3種貨物(問題規(guī)模較小)的數(shù)學(xué)模型如下：

(6)

利用Excel軟件的規(guī)劃求解功能，可得表4所示3種車組合優(yōu)化運送3種貨物(問題規(guī)模較小)的規(guī)劃求解結(jié)果.

表4 3種車組合優(yōu)化運送3種貨物(問題規(guī)模較小)的規(guī)劃求解結(jié)果 輛

從表4可看出：第1種車(15 t)對應(yīng)變量X1j中X15=7，X16=7，X19=4，其余均為0；第2種車(10 t)對應(yīng)變量X2j中X26=1，其余均為0；第3種車(8 t)對應(yīng)變量X3j中X32=1，其余均為0。

最終計算結(jié)果為：∑X1j=18，運費為18×660=11 880元；∑X2j=1，運費為1×580=580元；∑X3j=1，運費為1×500=500元。因此，最低總成本MinTF=11 880+580+500=12 960元。

3.2 實例2

某配送中心，編制2 d運輸配送計劃，現(xiàn)有載重8 t、10 t和15 t車輛可供使用，分別按單車運費660元、580元和500元運送3種重貨，單件質(zhì)量分別為0.4 t、0.7 t和1.1 t，數(shù)量分別為212件、80件和120件，問近似最優(yōu)解總的運費為多少元？

解：該問題以15 t車為例，3種貨物最大裝載數(shù)量分別為37件、21件和13件，配裝方案最大可能組合數(shù)為37×21×13=10 101.顯然，問題規(guī)模較大，不易直接求解.在規(guī)劃求解的基礎(chǔ)上，選擇代表性好的優(yōu)化組合方案,以保證各種貨物能裝下且優(yōu)化程度高.其求解過程與數(shù)學(xué)模型類似于實例1，因篇幅所限,從略.這里只給出求解結(jié)果。表5、表6和表7所示分別為采用15 t、10 t和8 t車裝載3種貨物(問題規(guī)模較大)的配裝方案。

表5 用15 t車裝載3種貨物(問題規(guī)模較大)的配裝方案 件

表6 用10 t車裝載3種貨物(問題規(guī)模較大)的配裝方案 件

表7 用8 t車裝載3種貨物(問題規(guī)模較大)的配裝方案 件

3種車組合優(yōu)化運送3種貨物求解過程及數(shù)學(xué)模型與實例1類似，因篇幅所限,從略。這里只給出求解結(jié)果。根據(jù)表5、表6、表7及其他相關(guān)數(shù)據(jù)，可得表8所示3種車組合優(yōu)化運送3種貨物(問題規(guī)模較大)的規(guī)劃求解結(jié)果。

表8 3種車組合優(yōu)化運送3種貨物(問題規(guī)模較大)的規(guī)劃求解結(jié)果 輛

從表8可看出：第1種車(15 t)對應(yīng)變量X1j中X11=1，X12=2，X13=2，X14=5，X15=1，X17=6，其余均為0；第2種車(10 t)對應(yīng)變量X2j中X22=1，X26=1，其余均為0；第3種車(8 t)對應(yīng)變量X3j均為0。

最終計算結(jié)果為：∑X1j=17，運費為17×660=11 220元；∑X2j=2，運費為2×580=1 160元；∑X3j=0，運費為0。因此，最低總成本MinTF=11 220+1 160=12 380元，低于只用15 t車的運輸成本12 540元。

4 結(jié)束語

多車、多貨物運輸裝車問題屬于復(fù)雜組合優(yōu)化問題，是企業(yè)急需解決的降低成本問題.多車、多貨物(重貨)可混裝運輸配送，當(dāng)規(guī)模較小時,借助Excel軟件,巧妙設(shè)計計算公式和規(guī)劃求解參數(shù),可有效解決這類問題；當(dāng)問題規(guī)模較大時，可采取3種措施來克服“組合爆炸”弊端.這3種措施為：選擇代表性好的優(yōu)化組合方案，減少配裝方案組合數(shù)量；調(diào)整編制計劃策略，減少待運貨物的總質(zhì)量；科學(xué)取舍車輛種類，減少車輛種類數(shù).選擇幾種優(yōu)化組合方案，分別規(guī)劃求解，優(yōu)中擇優(yōu)，可獲得理想的近似最優(yōu)解.新的簡便解法相對簡單、易于掌握、優(yōu)化程度高.該方法不僅可用于(重貨)按貨物質(zhì)量計算裝箱方案，充分利用車輛的載重能力，還可用于(輕貨)按貨物體積計算裝箱方案，充分利用車輛的容積能力.針對重貨和輕貨搭配的裝車方案更為復(fù)雜，需要進一步研究問題的解決方法.