邢航　張新邦　李貴棟　汪恭書

摘 要：研究了物流作業(yè)中同時考慮整車和零擔混合運輸模式的配載問題，決策每個托運物品由哪種運輸模式服務以及物品在整車運輸模式下如何配載，目標為最小化兩種運輸模式下的總配載費用。為該問題建立了新型整數(shù)規(guī)劃模型，并提出了強化模型的有效不等式，使用商業(yè)優(yōu)化軟件iLog-CPLEX求得了小規(guī)模算例的最優(yōu)解。由于iLog-CPLEX優(yōu)化軟件不能在有限時間內求得大規(guī)模問題的最優(yōu)解甚至可行解，針對大規(guī)模問題提出一種基于分組編碼方式的離散差分進化算法。實驗結果顯示所提出的算法明顯優(yōu)于傳統(tǒng)啟發(fā)式算法，驗證了離散差分進化算法在求解整車和零擔混合物流配載問題的有效性。

關鍵詞：整車運輸；零擔運輸；配載問題；混合整數(shù)規(guī)劃；差分進化

中圖分類號：U294 文獻標識碼：A

Abstract： This paper studies the logistics loading problem with hybrid of full and less-than truck load modes， which is to decide that each consignment is serviced by which transportation model and how to load consignments under full truck load model such that total loading cost under two transportation models is minimized. A novel integer programming model formulated， and valid inequalities are proposed to strengthen the model. Commercial optimization software iLog-CPLEX is used to solve the model to optimization for small-scale instances. Because no optimal or even feasible solution of the large-scale problem can be obtained by iLog-CPLEX optimization software within limited computational time， a discrete differential evolution algorithm based on group coding method is proposed for the large-scale problems. Experimental results show that the proposed algorithm is obviously superior to the traditional heuristic algorithm， which verifies that the discrete differential evolution algorithm is efficient to solve the logistics loading problem with hybrid of full truck load and less-than truck load.

Key words： full truck load； less-than truck load； loading problem； mixed integer programming； differential evaluation

0 引 言

運輸按照車輛裝載的貨物形態(tài)分為整車運輸與零擔運輸兩種模式[1-2]。零擔運輸一般指當一批貨物的重量或容積不滿一輛貨車時，可與其他幾批甚至上百批貨物共用一輛貨車裝運的運輸方式；而整車運輸通常是指因一批貨物的重量、性質、體積或形狀需要以一輛或一輛以上貨車裝運而按整車條件來運輸?shù)倪\輸方式。對比兩種運輸方式，整車運輸具有一次運載量大、運輸組織相對簡單、單位配載費用較低等特點，而零擔物流則具有一次運載量較小、運輸組織相對復雜、單位配載費用一般較高的特點。對物流公司來說，當貨物數(shù)量較多時，其自有車的運輸能力有限不能滿足用戶需求，往往需要外雇其他貨運公司的運輸車輛。在實際配載過程中需要綜合很多因素，比如考慮到公司利益以及外雇車的實際情況，通常對外雇車采用整車運輸模式，對自有車采用零擔運輸模式，這樣既可以提高物流的運輸效率又能夠降低運營成本。另外在實際配載過程中由于運輸貨物屬性多樣，出于安全考慮，要求一些有毒有害物品不能與食品等同車運輸，所以實際配載時又需要考慮物品的兼容性。本文研究的整車和零擔混合物流配載問題，目的在于決策如何配載以使在兩種運輸模式下的總配載費用最小，具有重要的現(xiàn)實意義。

對于零擔運輸問題，Chu在文獻[3]中提出了一種針對整車和零擔物流問題的啟發(fā)式算法，通過五個算例對算法進行了測試，結果表明他們提出的啟發(fā)式算法在針對時間及準確性的問題中能得出較好的解決方案；Konur和Schaefer[4]為評估碳排放量，有創(chuàng)意的研究了零擔運輸問題，通過大量實際的零擔物流問題，設計了一個?；贓stes快遞網(wǎng)絡和操作的、可針對未知運輸商的零擔物流通用模型。對于整車運輸，Jothi等[5]通過大量對整車物流的研究，以及大量相關數(shù)據(jù)，評價研究了整車物流的重要性、一些典型的模型以及當前的研究趨勢等。Doerner等[6]提出了一種新的解決整車物流問題的混合蟻群算法，通過實驗得出結論，在解決特定車隊規(guī)模的整車物流問題時，這種新的混合遺傳算法解得的解決方案要優(yōu)于傳統(tǒng)的蟻群算法。

本文針對整車和零擔混合物流配載問題，建立了整數(shù)規(guī)劃模型，并使用商業(yè)優(yōu)化軟件iLog-CPLEX求得了小規(guī)模算例的最優(yōu)解。由于iLog-CPLEX無法求解大規(guī)模問題，本文選擇智能優(yōu)化算法進行求解。智能優(yōu)化算法能夠在較短時間內獲得近優(yōu)解，不受問題結構規(guī)模的限制，適合求解較大規(guī)模問題。本文則是選用一種較好的智能優(yōu)化算法——差分進化算法來求解整車和零擔混合物流配載問題。

差分進化算法是一類基于種群的啟發(fā)式算法，對于實值參數(shù)的優(yōu)化有較好的魯棒性。應用DE求解整車和零擔混合物流配載問題需要合理設計編碼方式、交叉和變異過程等。本文針對此類問題的特點，對DE的編碼、變異以及交叉過程進行設計，提出了一種基于分組編碼方式的離散差分進化算法。通過和iLog-CPLEX軟件的結果對比，驗證了本文提出的改進差分進化算法在求解整車和零擔混合物流配載問題上的有效性。

1 整車和零擔混合物流配載問題

本文研究的整車和零擔混合物流配載問題可以描述如下：給定貨物集合N，任意貨物i∈N的重量記為w，車廂最大裝載量記為B，整車運輸模式的單車配載費用記為λ，零擔物流模式下單位重量配載費用記為μ，可外雇采用整車運輸?shù)能噹嫌洖镵；不兼容的貨物對集合記為A，在滿足車廂容量限制和貨物兼容性約束的前提下，決策每個托運物品由哪種運輸模式服務以及物品在整車運輸模式下如何配載，從而使得總配載費用最小。令二元變量x定義貨物i的裝載模式，即x=1表示貨物采用零擔運輸模式，x=0表示貨物采用整車運輸模式；二元變量y表示是否將貨物i裝入第k個箱子；二元變量z表示第k個車箱是否啟用?；谏鲜鰠?shù)和變量的定義，整車和零擔混合物流配載問題可以表示為以下的整數(shù)規(guī)劃模型：

目標函數(shù)（1）為最小化兩種運輸模式下的總配載費用；約束（2）要求每個貨物要么使用零擔運輸模式，要么使用整車運輸模式且必須被裝載到一個車廂；約束（3）定義了整車運輸模式下車載容量的上限和下限；約束（4）是對物品裝載的兼容性要求，即當兩個貨物不兼容時，就不能同時裝載到一個車廂；約束（5）～（7）定義了變量的取值范圍。

注意到，約束（3）的左端項屬于有效不等式約束，即使省去左端項的約束也不影響模型的最優(yōu)解，因為當一個車廂的裝載量小于λ/μ時，在最優(yōu)解中是不用采用整車運輸模式，這是由于此時將整車運輸模式轉換為零擔運輸模式不會增加裝載費用。雖然不影響最優(yōu)解，但是增加約束（3）左端項的有效不等式可以縮減可行解空間，由此可以提高模型的求解效率。另外，為了降低模型結構的對稱性，增加以下有效不等式（8）～（9）來削減解空間。

當問題規(guī)模較小時，上述MIP模型可以使用商業(yè)優(yōu)化軟件iLog-CPLEX直接求解。以開發(fā)環(huán)境visual studio2008為例，具體實現(xiàn)過程如下：（1）啟動visual studio 2008，創(chuàng)建一個win32控制臺應用程序。在C/C++下選擇常規(guī)，在附加包含目錄中添加iLog-CPLEX軟件所包含的concer和cplex文件夾下的include文件夾，目的是確定需要引用iLog-CPLEX相關函數(shù)的頭文件的位置；在C/C++下選擇預處理器，在預處理器定義中添加IL_ STD；在C/C++下選擇代碼生成，在運行時庫中選擇多線程

（/MT），在左側的配置屬性中選擇鏈接器，將cplex125.1ib，ilocplex.lib，concert.lib三個靜態(tài)鏈接庫所在的文件夾位置信息配置到附加庫目錄中，同時在附加依賴項中添加上述三個靜態(tài)鏈接庫。（2）在程序代碼中定義參數(shù)常量，包括：貨物重量數(shù)組IloNumArray w，不兼容貨物對數(shù)組IloArrayA，以及int N；int B；int K；double lambda；double miu。從外部數(shù)據(jù)文件中將數(shù)據(jù)讀入上述定義的參數(shù)中。（3）在程序代碼中定義決策變量，包括：IloBoolVarArray x；IloArrayy；IloBoolVarArray z；基于定義的常量和變量，將目標函數(shù)和約束添加到模型IloModelMIPmodel（env_）；定義求解器IloCplexcplex（env_），并將模型裝載到求解器cplex.extract（MIPmodel）；運行求解器cplex.solve。（4）基于求解器運行的結果，得到決策變量x，y，z的最優(yōu)值和最優(yōu)目標函數(shù)值。

2 差分進化算法

由于iLog-CPLEX只能求得小規(guī)模算例的最優(yōu)解，對于大規(guī)模問題，在有限時間內不能求解最優(yōu)解甚至可行解。因此需要設計更有效的算法。DE算法的本質是一種基于實數(shù)編碼的具有保優(yōu)思想的進化算法，其基本思想是：對當前種群進行變異和交叉操作，產生另一個新種群，然后利用貪婪算法對這兩個種群進行選擇，從而產生最終的新一代種群。

編碼方式：針對零擔與整車物流的配載問題，本文采用了一種基于分組的編碼方式。在這種編碼方式中，個體的基因表示一組物品的子集，子集中物品的重量不超過箱子的容量。該編碼方式使得種群空間與解空間一一對應，解決了傳統(tǒng)編碼方式放大解空間的缺陷，提高了算法的搜索速率與魯棒性。

由于編碼方式的差異，傳統(tǒng)的變異與交叉操作已不再適用，因此本文設計了新的變異與交叉操作方法。

交叉操作：首先計算兩親代各基因的裝載量，再將兩親代的基因按照等位基因順序與裝載量的大小進行重新排序，其中等位基因按照裝載量大小排序，裝載量大的基因位于裝載量小的基因前，非等位基因按照基因的順序進行排序。再從基因排序的第二個基因位開始，將含有之前基因已存在物品的基因刪除，并用BFD啟發(fā)式算法將未裝入箱子的個體編入個體，最后根據(jù)各基因的裝載量大小對各基因進行排序，得到交叉?zhèn)€體。

3 仿真實驗

針對零擔與整車物流混合配載問題進行仿真實驗，對小規(guī)模算例分別采用iLog-CPLEX軟件和改進的離散差分進化（IDE）算法進行求解，對較大規(guī)模算例采用改進的離散差分進化算法進行求解。IDE算法利用Microsoft Visual studio編程實現(xiàn)，在Intel（R）Core（TM）i5-4210M CPU@2.60GHz， 4.00GB內存物理地址擴展，Microsoft Windows 8.1系統(tǒng)電腦上運行。

從表2可以看出，BFD算法雖然求解速度快，但是解的質量較差，甚至全都差于IDE算法的最差解，說明IDE在求解大規(guī)模問題上具有很大優(yōu)勢，采用IDE求解大規(guī)模零擔與整車物流混合配載問題是可行的，并且值得推廣使用。

4 結 論

本文研究了一類廣泛存在于物流運輸過程中的整車和零擔混合物流配載問題，建立了該問題的混合整數(shù)規(guī)劃模型，提出了一種基于分組編碼方式的離散差分進化算法，并通過和iLog-CPLEX優(yōu)化軟件結果以及傳統(tǒng)啟發(fā)式算法BFD結果進行比較，驗證了本文的改進的離散差分進化算法在求解此類問題的有效性，可以在實際中推廣使用。

參考文獻：

[1] 張婷. 零擔物流業(yè)回顧與發(fā)展[J]. 中國儲運，2011（9）：66-69.

[2] 楊懷珍，熊煒，董歡歡. 整車物流研究現(xiàn)狀述評與趨勢展望[J]. 生產力研究，2012（9）：242-244.

[3] Chu C W. A heuristic algorithm for the truckload and less-than-truckload problem[J]. European Journal of Operational Research， 2005，165（3）：657-667.

[4] Konur D， Schaefer B. Integrated inventory control and transportation decisions under carbon emissions regulations： LTL vs. TL carriers[J]. Transportation Research Part E Logistics & Transportation Review， 2014，68（4）：14-38.

[5] Basu R J， Subramanian N， Cheikhrouhou N. Review of Full Truckload Transportation Service Procurement[J]. Transport Reviews， 2015，35（5）：599-621.

[6] Doerner K， Hartl R F， Reimann M. A hybrid ACO algorithm for the Full Truckload Transportation Problem[J]. Institute of Management University of Vienna， 2001（5）：137-145.

[7] Storn R， Price K. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces[J]. Journal of Global Optimization， 1997，11（4）：341-359.