整車(chē)和零擔(dān)混合物流配載問(wèn)題的建模與求解
2016-08-03 09:24:28邢航張新邦李貴棟汪恭書(shū)
物流科技 2016年7期
邢航 張新邦 李貴棟 汪恭書(shū)
摘 要：研究了物流作業(yè)中同時(shí)考慮整車(chē)和零擔(dān)混合運(yùn)輸模式的配載問(wèn)題，決策每個(gè)托運(yùn)物品由哪種運(yùn)輸模式服務(wù)以及物品在整車(chē)運(yùn)輸模式下如何配載，目標(biāo)為最小化兩種運(yùn)輸模式下的總配載費(fèi)用。為該問(wèn)題建立了新型整數(shù)規(guī)劃模型，并提出了強(qiáng)化模型的有效不等式，使用商業(yè)優(yōu)化軟件iLog-CPLEX求得了小規(guī)模算例的最優(yōu)解。由于iLog-CPLEX優(yōu)化軟件不能在有限時(shí)間內(nèi)求得大規(guī)模問(wèn)題的最優(yōu)解甚至可行解，針對(duì)大規(guī)模問(wèn)題提出一種基于分組編碼方式的離散差分進(jìn)化算法。實(shí)驗(yàn)結(jié)果顯示所提出的算法明顯優(yōu)于傳統(tǒng)啟發(fā)式算法，驗(yàn)證了離散差分進(jìn)化算法在求解整車(chē)和零擔(dān)混合物流配載問(wèn)題的有效性。
關(guān)鍵詞：整車(chē)運(yùn)輸；零擔(dān)運(yùn)輸；配載問(wèn)題；混合整數(shù)規(guī)劃；差分進(jìn)化
中圖分類(lèi)號(hào)：U294 文獻(xiàn)標(biāo)識(shí)碼：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 引 言
運(yùn)輸按照車(chē)輛裝載的貨物形態(tài)分為整車(chē)運(yùn)輸與零擔(dān)運(yùn)輸兩種模式[1-2]。零擔(dān)運(yùn)輸一般指當(dāng)一批貨物的重量或容積不滿一輛貨車(chē)時(shí)，可與其他幾批甚至上百批貨物共用一輛貨車(chē)裝運(yùn)的運(yùn)輸方式；而整車(chē)運(yùn)輸通常是指因一批貨物的重量、性質(zhì)、體積或形狀需要以一輛或一輛以上貨車(chē)裝運(yùn)而按整車(chē)條件來(lái)運(yùn)輸?shù)倪\(yùn)輸方式。對(duì)比兩種運(yùn)輸方式，整車(chē)運(yùn)輸具有一次運(yùn)載量大、運(yùn)輸組織相對(duì)簡(jiǎn)單、單位配載費(fèi)用較低等特點(diǎn)，而零擔(dān)物流則具有一次運(yùn)載量較小、運(yùn)輸組織相對(duì)復(fù)雜、單位配載費(fèi)用一般較高的特點(diǎn)。對(duì)物流公司來(lái)說(shuō)，當(dāng)貨物數(shù)量較多時(shí)，其自有車(chē)的運(yùn)輸能力有限不能滿足用戶(hù)需求，往往需要外雇其他貨運(yùn)公司的運(yùn)輸車(chē)輛。在實(shí)際配載過(guò)程中需要綜合很多因素，比如考慮到公司利益以及外雇車(chē)的實(shí)際情況，通常對(duì)外雇車(chē)采用整車(chē)運(yùn)輸模式，對(duì)自有車(chē)采用零擔(dān)運(yùn)輸模式，這樣既可以提高物流的運(yùn)輸效率又能夠降低運(yùn)營(yíng)成本。另外在實(shí)際配載過(guò)程中由于運(yùn)輸貨物屬性多樣，出于安全考慮，要求一些有毒有害物品不能與食品等同車(chē)運(yùn)輸，所以實(shí)際配載時(shí)又需要考慮物品的兼容性。本文研究的整車(chē)和零擔(dān)混合物流配載問(wèn)題，目的在于決策如何配載以使在兩種運(yùn)輸模式下的總配載費(fèi)用最小，具有重要的現(xiàn)實(shí)意義。
對(duì)于零擔(dān)運(yùn)輸問(wèn)題，Chu在文獻(xiàn)[3]中提出了一種針對(duì)整車(chē)和零擔(dān)物流問(wèn)題的啟發(fā)式算法，通過(guò)五個(gè)算例對(duì)算法進(jìn)行了測(cè)試，結(jié)果表明他們提出的啟發(fā)式算法在針對(duì)時(shí)間及準(zhǔn)確性的問(wèn)題中能得出較好的解決方案；Konur和Schaefer[4]為評(píng)估碳排放量，有創(chuàng)意的研究了零擔(dān)運(yùn)輸問(wèn)題，通過(guò)大量實(shí)際的零擔(dān)物流問(wèn)題，設(shè)計(jì)了一個(gè)專(zhuān)基于Estes快遞網(wǎng)絡(luò)和操作的、可針對(duì)未知運(yùn)輸商的零擔(dān)物流通用模型。對(duì)于整車(chē)運(yùn)輸，Jothi等[5]通過(guò)大量對(duì)整車(chē)物流的研究，以及大量相關(guān)數(shù)據(jù)，評(píng)價(jià)研究了整車(chē)物流的重要性、一些典型的模型以及當(dāng)前的研究趨勢(shì)等。Doerner等[6]提出了一種新的解決整車(chē)物流問(wèn)題的混合蟻群算法，通過(guò)實(shí)驗(yàn)得出結(jié)論，在解決特定車(chē)隊(duì)規(guī)模的整車(chē)物流問(wèn)題時(shí)，這種新的混合遺傳算法解得的解決方案要優(yōu)于傳統(tǒng)的蟻群算法。
本文針對(duì)整車(chē)和零擔(dān)混合物流配載問(wèn)題，建立了整數(shù)規(guī)劃模型，并使用商業(yè)優(yōu)化軟件iLog-CPLEX求得了小規(guī)模算例的最優(yōu)解。由于iLog-CPLEX無(wú)法求解大規(guī)模問(wèn)題，本文選擇智能優(yōu)化算法進(jìn)行求解。智能優(yōu)化算法能夠在較短時(shí)間內(nèi)獲得近優(yōu)解，不受問(wèn)題結(jié)構(gòu)規(guī)模的限制，適合求解較大規(guī)模問(wèn)題。本文則是選用一種較好的智能優(yōu)化算法——差分進(jìn)化算法來(lái)求解整車(chē)和零擔(dān)混合物流配載問(wèn)題。
差分進(jìn)化算法是一類(lèi)基于種群的啟發(fā)式算法，對(duì)于實(shí)值參數(shù)的優(yōu)化有較好的魯棒性。應(yīng)用DE求解整車(chē)和零擔(dān)混合物流配載問(wèn)題需要合理設(shè)計(jì)編碼方式、交叉和變異過(guò)程等。本文針對(duì)此類(lèi)問(wèn)題的特點(diǎn)，對(duì)DE的編碼、變異以及交叉過(guò)程進(jìn)行設(shè)計(jì)，提出了一種基于分組編碼方式的離散差分進(jìn)化算法。通過(guò)和iLog-CPLEX軟件的結(jié)果對(duì)比，驗(yàn)證了本文提出的改進(jìn)差分進(jìn)化算法在求解整車(chē)和零擔(dān)混合物流配載問(wèn)題上的有效性。
1 整車(chē)和零擔(dān)混合物流配載問(wèn)題
本文研究的整車(chē)和零擔(dān)混合物流配載問(wèn)題可以描述如下：給定貨物集合N，任意貨物i∈N的重量記為w，車(chē)廂最大裝載量記為B，整車(chē)運(yùn)輸模式的單車(chē)配載費(fèi)用記為λ，零擔(dān)物流模式下單位重量配載費(fèi)用記為μ，可外雇采用整車(chē)運(yùn)輸?shù)能?chē)廂集合記為K；不兼容的貨物對(duì)集合記為A，在滿足車(chē)廂容量限制和貨物兼容性約束的前提下，決策每個(gè)托運(yùn)物品由哪種運(yùn)輸模式服務(wù)以及物品在整車(chē)運(yùn)輸模式下如何配載，從而使得總配載費(fèi)用最小。令二元變量x定義貨物i的裝載模式，即x=1表示貨物采用零擔(dān)運(yùn)輸模式，x=0表示貨物采用整車(chē)運(yùn)輸模式；二元變量y表示是否將貨物i裝入第k個(gè)箱子；二元變量z表示第k個(gè)車(chē)箱是否啟用?；谏鲜鰠?shù)和變量的定義，整車(chē)和零擔(dān)混合物流配載問(wèn)題可以表示為以下的整數(shù)規(guī)劃模型：
目標(biāo)函數(shù)（1）為最小化兩種運(yùn)輸模式下的總配載費(fèi)用；約束（2）要求每個(gè)貨物要么使用零擔(dān)運(yùn)輸模式，要么使用整車(chē)運(yùn)輸模式且必須被裝載到一個(gè)車(chē)廂；約束（3）定義了整車(chē)運(yùn)輸模式下車(chē)載容量的上限和下限；約束（4）是對(duì)物品裝載的兼容性要求，即當(dāng)兩個(gè)貨物不兼容時(shí)，就不能同時(shí)裝載到一個(gè)車(chē)廂；約束（5）～（7）定義了變量的取值范圍。
注意到，約束（3）的左端項(xiàng)屬于有效不等式約束，即使省去左端項(xiàng)的約束也不影響模型的最優(yōu)解，因?yàn)楫?dāng)一個(gè)車(chē)廂的裝載量小于λ/μ時(shí)，在最優(yōu)解中是不用采用整車(chē)運(yùn)輸模式，這是由于此時(shí)將整車(chē)運(yùn)輸模式轉(zhuǎn)換為零擔(dān)運(yùn)輸模式不會(huì)增加裝載費(fèi)用。雖然不影響最優(yōu)解，但是增加約束（3）左端項(xiàng)的有效不等式可以縮減可行解空間，由此可以提高模型的求解效率。另外，為了降低模型結(jié)構(gòu)的對(duì)稱(chēng)性，增加以下有效不等式（8）～（9）來(lái)削減解空間。
當(dāng)問(wèn)題規(guī)模較小時(shí)，上述MIP模型可以使用商業(yè)優(yōu)化軟件iLog-CPLEX直接求解。以開(kāi)發(fā)環(huán)境visual studio2008為例，具體實(shí)現(xiàn)過(guò)程如下：（1）啟動(dòng)visual studio 2008，創(chuàng)建一個(gè)win32控制臺(tái)應(yīng)用程序。在C/C++下選擇常規(guī)，在附加包含目錄中添加iLog-CPLEX軟件所包含的concer和cplex文件夾下的include文件夾，目的是確定需要引用iLog-CPLEX相關(guān)函數(shù)的頭文件的位置；在C/C++下選擇預(yù)處理器，在預(yù)處理器定義中添加IL_ STD；在C/C++下選擇代碼生成，在運(yùn)行時(shí)庫(kù)中選擇多線程
（/MT），在左側(cè)的配置屬性中選擇鏈接器，將cplex125.1ib，ilocplex.lib，concert.lib三個(gè)靜態(tài)鏈接庫(kù)所在的文件夾位置信息配置到附加庫(kù)目錄中，同時(shí)在附加依賴(lài)項(xiàng)中添加上述三個(gè)靜態(tài)鏈接庫(kù)。（2）在程序代碼中定義參數(shù)常量，包括：貨物重量數(shù)組IloNumArray w，不兼容貨物對(duì)數(shù)組IloArray
2 差分進(jìn)化算法
由于iLog-CPLEX只能求得小規(guī)模算例的最優(yōu)解，對(duì)于大規(guī)模問(wèn)題，在有限時(shí)間內(nèi)不能求解最優(yōu)解甚至可行解。因此需要設(shè)計(jì)更有效的算法。DE算法的本質(zhì)是一種基于實(shí)數(shù)編碼的具有保優(yōu)思想的進(jìn)化算法，其基本思想是：對(duì)當(dāng)前種群進(jìn)行變異和交叉操作，產(chǎn)生另一個(gè)新種群，然后利用貪婪算法對(duì)這兩個(gè)種群進(jìn)行選擇，從而產(chǎn)生最終的新一代種群。
編碼方式：針對(duì)零擔(dān)與整車(chē)物流的配載問(wèn)題，本文采用了一種基于分組的編碼方式。在這種編碼方式中，個(gè)體的基因表示一組物品的子集，子集中物品的重量不超過(guò)箱子的容量。該編碼方式使得種群空間與解空間一一對(duì)應(yīng)，解決了傳統(tǒng)編碼方式放大解空間的缺陷，提高了算法的搜索速率與魯棒性。
由于編碼方式的差異，傳統(tǒng)的變異與交叉操作已不再適用，因此本文設(shè)計(jì)了新的變異與交叉操作方法。
交叉操作：首先計(jì)算兩親代各基因的裝載量，再將兩親代的基因按照等位基因順序與裝載量的大小進(jìn)行重新排序，其中等位基因按照裝載量大小排序，裝載量大的基因位于裝載量小的基因前，非等位基因按照基因的順序進(jìn)行排序。再?gòu)幕蚺判虻牡诙€(gè)基因位開(kāi)始，將含有之前基因已存在物品的基因刪除，并用BFD啟發(fā)式算法將未裝入箱子的個(gè)體編入個(gè)體，最后根據(jù)各基因的裝載量大小對(duì)各基因進(jìn)行排序，得到交叉?zhèn)€體。
3 仿真實(shí)驗(yàn)
針對(duì)零擔(dān)與整車(chē)物流混合配載問(wèn)題進(jìn)行仿真實(shí)驗(yàn)，對(duì)小規(guī)模算例分別采用iLog-CPLEX軟件和改進(jìn)的離散差分進(jìn)化（IDE）算法進(jìn)行求解，對(duì)較大規(guī)模算例采用改進(jìn)的離散差分進(jìn)化算法進(jìn)行求解。IDE算法利用Microsoft Visual studio編程實(shí)現(xiàn)，在Intel（R）Core（TM）i5-4210M CPU@2.60GHz， 4.00GB內(nèi)存物理地址擴(kuò)展，Microsoft Windows 8.1系統(tǒng)電腦上運(yùn)行。
從表2可以看出，BFD算法雖然求解速度快，但是解的質(zhì)量較差，甚至全都差于IDE算法的最差解，說(shuō)明IDE在求解大規(guī)模問(wèn)題上具有很大優(yōu)勢(shì)，采用IDE求解大規(guī)模零擔(dān)與整車(chē)物流混合配載問(wèn)題是可行的，并且值得推廣使用。
4 結(jié) 論
本文研究了一類(lèi)廣泛存在于物流運(yùn)輸過(guò)程中的整車(chē)和零擔(dān)混合物流配載問(wèn)題，建立了該問(wèn)題的混合整數(shù)規(guī)劃模型，提出了一種基于分組編碼方式的離散差分進(jìn)化算法，并通過(guò)和iLog-CPLEX優(yōu)化軟件結(jié)果以及傳統(tǒng)啟發(fā)式算法BFD結(jié)果進(jìn)行比較，驗(yàn)證了本文的改進(jìn)的離散差分進(jìn)化算法在求解此類(lèi)問(wèn)題的有效性，可以在實(shí)際中推廣使用。
參考文獻(xiàn)：
[1] 張婷. 零擔(dān)物流業(yè)回顧與發(fā)展[J]. 中國(guó)儲(chǔ)運(yùn)，2011（9）：66-69.
[2] 楊懷珍，熊煒，董歡歡. 整車(chē)物流研究現(xiàn)狀述評(píng)與趨勢(shì)展望[J]. 生產(chǎn)力研究，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.
