李麗瀅 付寒梅



摘 要:針對整車物流服務供應鏈的訂單分配問題,提出了考慮多種運輸方式的雙層訂單分配模型。首先,考慮到運輸方式會影響運輸成本、客戶的準時送達要求等因素,建立以準時送達和最小化物流采購成本為目標的雙層規劃模型;其次,設計啟發式算法(HA)確定各運輸方式的任務量;然后,借助混合蛙跳算法(SFLA)求解各功能物流服務提供商間各運輸方式的任務量分配;最后,通過不同規模的算例與遺傳算法(GA)、粒子群算法(PSO)、蟻群算法(ACO)等進行求解對比。算例結果表明,與原有的成本438萬元相比,所提模型得到顯著優化的421萬元,說明所構建模型的訂單分配方案能夠更有效解決整車物流的訂單分配問題。實驗對比表明,較傳統智能算法(GA、PSO、ACO)的求解結果,兩階段的HA-SFLA算法能更快得出顯著優化的結果,說明HA-SFLA算法能更好地求解考慮運輸方式的雙層訂單分配規劃模型。在滿足客戶送達時間要求的同時,考慮運輸方式的雙層訂單分配模型及算法顯著降低物流成本,促進物流集成商為獲取更多利益而在訂單分配階段考慮運輸方式。
關鍵詞:物流服務供應鏈;訂單分配;運輸方式;雙層規劃;混合蛙跳算法
中圖分類號: F273.1(企業技術管理)
文獻標志碼:A
Focusing on the order allocation in vehicle logistics service supply chain, a bi-level programming model considering multiple modes of transportation was proposed. Firstly, considering that different transportation modes affect the transportation cost and the customers on-time delivery requirement, a bi-level programming model aiming to punctual delivery and minimization of purchasing cost was established. Secondly, a Heuristic Algorithm (HA) was designed to determine the tasks of each transportation mode. Thirdly, Shuffled Frog Leaping Algorithm (SFLA) was used to solve task allocation of each transportation mode between functional logistics service providers. Finally, the solution of the proposed model was compared with those of Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO) through different scale examples. The results show that compared with the original purchasing cost 4.38 million yuan, the proposed model has a significantly optimized result 4.21 million yuan, which shows the order allocation scheme of the proposed model solves the order allocation problem of vehicle logistics more effectively. Experimantal results show that HA-SFLA can obtain the significantly optimized result quickly compared to GA, PSO and ACO, illustrating that HA-SFLA can solve the bi-level model considering transportation modes more efficiently. The bi-level order allocation model and algorithm considering transportation modes can reduce logistics costs while meet customer on-time requirements, making the logistics suppliers consider the transportation modes in order allocation phase to achieve more benefits.
Key words: Logistics Service Supply Chain (LSSC); order allocation; transportation mode; bi-level programming; Shuffled Frog Leaping Algorithm (SFLA)
0 引言
隨著經濟全球化的發展,整車物流的公路運輸中存在低效率、高污染、高成本等問題[1],解決上述問題仍是汽車物流企業的主要任務。整車物流服務供應鏈(Logistics Service Supply Chain, LSSC)中,物流服務集成商(Logistics Service Integrator, LSI)整合客戶的整車物流需求訂單,根據客戶時間要求確定各種運輸方式的運量分配計劃,然后把運輸任務具體分配到公路、鐵路、水路各功能型物流服務提供商(Functional Logistics Service Provider, FLSP)。隨著零庫存、精益生產等理念在實踐運營中的推廣,整車物流對交貨準時率的要求越來越高,不同運輸方式具有不同的時間和經濟特性,進而影響整車物流運輸的交貨準時率和物流成本。物流服務集成商如何利用大批量、低成本的水路和鐵路運輸以及靈活的公路運輸,將整車運輸任務合理地分配給物流服務提供商,保證準時交貨同時最小化物流成本,是整車物流供應鏈長期穩定運營的關鍵。特別是商品車的需求存儲空間大導致存儲成本高,客戶對準時送達的要求較高,物流服務集成商必須在保證商品車準時送達的前提下,盡量降低物流成本。因此,本文研究考慮多種運輸方式的整車運輸訂單分配問題,建立優先保證準時送達的雙層訂單分配模型并進行分析。
訂單分配的研究引起了越來越多的學者關注。劉偉華等[2]考慮了關系成本系數,以最小化LSI總成本和懲罰強度、最大化FLSP滿意度和不同能力之間的匹配為研究目標構建任務分配模型。姜意楊等[3]引入FLSP現有手頭訂單、物流能力可獲得性等因素,構建FLSP選擇與訂單分配組合優化模型。張廣勝等[4]針對應急任務的服務時效特性,建立基于服務時效性的物流服務供應鏈應急任務分配模型。李珊珊[5]針對交易費用為交易額的線性函數這一特點對訂單分配問題進行研究,并采用混合遺傳算法進行求解。Liu等[6]研究大規模定制物流服務環境下,考慮新訂單相似性參數的訂單分配問題。但這些研究均未考慮多種運輸方式的技術和經濟特性,考慮多種運輸方式的物流服務供應鏈訂單分配問題未得到有效研究。現有關于整車物流運輸的研究大都集中在物流成本控制和路徑優化方面[7-10]。部分整車物流任務分配的研究考慮了多種運輸方式,如劉弘超等[11]借鑒混合軸輻射理論,建立整車物流企業的多式聯運網絡優化模型。Masoud等[12]探討了多種運輸方式在短周期汽車零件的生產與運輸的總成本、可靠性和時間上的影響。但現有整車物流的研究多集中在路徑優化、物流網絡設計、庫存選址等方面[13-15],在訂單分配方面的研究仍未出現。
目前關于整車物流服務供應鏈訂單分配問題的研究均未考慮多種運輸方式的技術經濟特性,與實際情況存在一定差異,不能適應實際需求。實際工作中LSI的整車物流訂單分配,通常是先分析各種運輸方式的運量,再將運輸任務分配給各FLSP,因此本文設定運送時間為運輸方式的函數,構建雙層規劃模型,從而更好地反映整車物流服務供應鏈的訂單分配決策。同時,已有研究多采用遺傳算法(Genetic Algorithm, GA)、粒子群算法(Particle Swarm Optimization, PSO)、蟻群算法(Ant Colony Optimization, ACO)等傳統的智能優化算法,雙層訂單分配模型中目標與約束的復雜性使計算復雜度大幅度上升,現有的單一問題的求解方法均不太理想,本文設計HA-SFLA的兩階段算法求解,并將其與GA、PSO等進行求解對比。
1 模型構建
物流集成商根據客戶商品車的運輸要求,確定運輸方式及其運輸量,然后根據各FLSP所擁有的運輸方式的運力狀況,將運輸任務分解到各物流服務提供商,因此模型構建分兩階段。第一階段進行運輸方式的選擇,物流集成商對客戶需求點對之間的商品車運輸需求進行整合,由于商品車的獨特性,需求存儲空間大且價值高導致存儲成本高,客戶對準時送達的要求較高,提前送達或延遲送達均會產生客戶存儲成本,因此集成商以延遲/提前送達時間最少為目標,確定各需求點對間的運輸方式及各運輸方式的運量,提出準時送達為目標的上層規劃模型。第二階段,LSI集成各物流服務提供商的運輸能力,將各運輸方式的運量分配給各物流服務提供商,提出最小化采購成本為目標的下層規劃模型。第一階段的各運輸方式運量分配結果會影響第二階段的總采購成本,即本文提出的雙層規劃模型。
結合實際情況,本文作了如下約定:1)運輸點對{i, j}間的距離dij大于1000km的遠距離運輸且商品車的運輸量Qij大于300時,采用鐵路、水路運輸;運輸距離dij小于500km的短距離運輸,采用公路運輸。2)由于集成商和多個功能提供商合作,各運輸方式的運力是無限的。3)各運輸點對間可采用多種運輸方式,不考慮中轉,且不考慮運輸點的裝卸成本。4)運輸點對間各種運輸方式的運輸時間是確定的,一運輸點對之間的運輸可以由多個功能提供商共同完成。
1.1 模型的相關參數和變量
某LSI收到多個城市間的商品車運輸任務訂單,整合各FLSP運輸方式運力及客戶送達時間要求信息,集成商將運輸任務分配給合作的物流服務提供商。
為方便建模,設置如下參數:{i, j}為將商品車從城市i運往城市j的運輸點對,{i, j}∈A,A為運輸需求點對的集合;G表示功能型物流服務提供商集合,b表示FLSP的數量;k =1,2,3分別表示公路、鐵路、水路運輸;vk表示運輸方式k的運輸速度;pkf為物流服務提供商f運輸方式k的單位能力報價;ak為單位運輸工具k的商品車裝載量;Ukij,f為物流服務提供商f在{i, j}間運輸方式k的可用運力;dkij為 {i, j}間采用運輸方式k的運輸距離;Nkij為 {i, j}間采用運輸方式k的運輸工具數量;Nkij,f為 {i, j}間集成商采購物流服務提供商f的運輸工具k的數量;Tkij為{i, j}間采用第k種運輸方式的運輸時間;Tij為{i, j}間商品車運輸的期望需求時間;TSkij為{i, j}間采用運輸方式k的出發時間;hkij=1,{i, j}間的運輸方式k可用0,其他。
1.2 模型建立
上層規劃是在滿足客戶準時送達要求的前提下,確定運輸點對{i, j}間的運輸方式及其運量。此階段物流服務集成商的目標是提前和延遲送達的總時間最少,某運輸點對{i, j}間的整車物流所需的各運輸工具數量及運輸時間可表示為:Nkij=[qkij/ak]+ 和Tkij=[dij/vk]+,其中“[]+”表示向上取整,進而某運輸方式的延遲和提前送達時間表示為:max{Tkij×xkij+TSkij-Tij,0}和max{Tij-Tkij×xkij-TSkij,0}。
最終客戶的總延遲和提前送達時間的表達式為式(1)。其中:式(2)表示遠距離運輸或運輸量大時,使用鐵路、水路運輸;式(3)表示必須選擇一種運輸方式;式(4)為運輸需求滿足約束;式(5)為運輸工具的滿載率約束,表示采用某運輸工具的裝載率需滿足80%或滿載,避免造成火車、貨輪等運載工具的裝載空間浪費;式(6)為變量非負約束。整車物流服務供應鏈訂單分配的上層模型(U)為:
2 兩階段算法
訂單分配問題是NP難問題,由于雙層規劃問題的非凸性、非連續性等特點決定了常規的優化方法并不能有效解決該問題。因此,根據雙層規劃的思想,設計HA-SFLA兩階段算法求解考慮多種運輸方式的訂單分配問題,兩階段算法流程如圖1所示。
2.1 啟發式算法
針對訂單分配問題的第一階段,LSI以準時送達為目標確定各運輸點對間運輸需求的運輸方式及其運量,設計啟發式算法來求解。
2.1.1 初始解的生成
采用整數編碼方式對需求點對間的運輸方式選擇及運量分配進行編碼,某一運輸點對間的編碼為:{x1ij x2ij x3ij q1ij q2ij q3ij TS1ij TS2ij TS3ij},如:{0 0 1 0 0 270 0 0 6}表示對運輸點對{i, j}間采用水路運輸且運輸量為270,在6d后開始出發運輸。
針對實際中的長距離、大貨物量運輸,通常采用水路、鐵路運輸的特性,采取如下步驟構造初始解。
步驟1 距離特性下xkij的確定。判斷某一運輸點對{i, j}間的距離dij及運輸需求量Qij,根據距離長短及需求量的大小程度確定運輸方式xkij。
步驟2 滿載率特性下qkij的確定。對步驟1中確定的鐵路、水路兩種運輸方式,分別計算滿載率,若不滿足滿載率約束,則將不滿足滿載率約束部分的需求量用公路運輸。
步驟3 出發時間TSkij的確定。選擇某種運輸方式后,確定完運輸方式的出發時間以滿足準時送達需求。首先確定各運輸方式的運輸時間Tkij,然后比較運輸時間和客戶要求送達時間,最后確定出發時間TSkij和延遲時間。
2.1.2 啟發式規則調整解
計算拖延時間Z1,若Z1>0,則調整運輸方式使Z1=0,具體啟發式規則為:
步驟1
對某運輸點對{i, j},若選擇的運輸方式僅為公路運輸則無需調整此運輸點對,無法滿足此運輸點對間的時間約束,遍歷下一運輸點對。
步驟2 若{i, j}間選擇的運輸方式為水路,且鐵路可用時,則調整為較快的鐵路運輸。
步驟3 若{i, j}間選擇的運輸方式為水路,但鐵路不可用時,則調整為更快的公路運輸。
步驟4 若{i, j}間選擇的運輸方式為鐵路,則調整為更快的公路運輸。直至遍歷所有的運輸點對,否則返回步驟1。
2.2 混合蛙跳算法設計
混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是Eusuff等[16]提出的一種亞啟發式協同搜索群智能算法。文獻[17]表明混合蛙跳算法結合了模因演算算法和粒子群算法的優點,具有參數少、計算速度快、全局尋有能力強、易于實現等特點,應用廣泛。
針對訂單分配問題的第二階段,LSI將第一階段各運輸點對間確定的運輸方式及運量分配給有合作關系的FLSP。由于運輸方式的選擇已在第一階段確定,因此,第二階段的分配即不考慮運輸方式的訂單分配問題,即NP難問題,采用混合蛙跳算法求解。
2.2.1 個體編碼
采用基于整數的矩陣個體編碼方式,某運輸點對{i, j}間的第二階段運輸分配結果編碼矩陣。此矩陣為b行9列,b為物流服務提供商的個數,其中:1~3列為ykij,f,表示各物流服務提供商是否被分配各運輸方式的運輸任務;4~6列為Nkij,f,表示各物流服務提供商被分配的3種運輸方式的工具數量;7~9列為qkij,f,表示各物流服務提供商被分配的3種運輸方式的任務量。
2.2.2 個體啟發式規則修正
混合蛙跳算法的迭代過程中,可能出現不滿足約束的非可行解。因此需要設計一定的啟發式規則來修正個體,導向性的產生滿足約束且更優的個體。具體步驟如下:
步驟1 對某一運輸點對{i, j}間的運輸方式k=1∶3,執行步驟2~3。
步驟2 運輸方式數量約束。若∑Gf=1Nkij,f≠Nkij,則調整某物流服務提供商f的運輸方式數量以滿足:1)物流服務提供商分配的運輸方式數量不為負值;2)不超出物流服務提供商的運輸能力約束。
步驟3 運輸能力約束。對f=1∶G,若Nkij,f 步驟4 判斷是否修正結束。k=k+1,若k=3,則結束修正;反之,重復步驟2~3。 個體修正主要是對個體矩陣編碼中的Nkij,f進行操作,修正完成后更新矩陣中的ykij,f和qkij,f。這樣可以既符合第一階段結果,又保證滿足需求量約束,避免了計算的復雜性。 2.2.3 混合蛙跳算法的蛙跳規則 結合蛙跳規則的改進研究,本文采用鄭仕鏈等[18]提出的蛙跳規則,如下: 其中:r表示0與1之間的隨機數;D表示上一次更新時的蛙跳距離向量;Dmax表示蛙所允許改變位置的最大值;D′表示本次更新時的蛙跳距離向量。式(14)加入了上次的蛙跳距離,在本次蛙跳時學習了以往的經驗,具有初步的學習能力,尋優能力強。 3 算例仿真與分析 3.1 實例分析 某汽車物流公司是全國業務規模最大的汽車物流服務商,主要從事汽車整車物流服務。本文選取該物流公司某月訂單數據進行測試,相關數據如表1,其中hkij和dkij可由《中國公路鐵路水路圖集》確定,與其合作的物流服務提供商有7個,編號為A到F,各功能型物流服務提供商的運力數據略,其他數據如表2所示。 3.2 算例比較 為了驗證HA-SFLA兩階段算法的求解性能,鑒于已有研究多采用遺傳算法(GA)、粒子群算法(PSO)、蟻群算法(ACO)等進行求解,隨機產生算例數據進行測試,與GA、PSO、ACO進行對比實驗。算例的參數按如下均勻分布產生:Qij~U(10,1000),dij~U(400,2000),U1ij,f~U(0,30),U2ij,f~U(0,2),U3ij,f~U(0,3),按月訂單量的一般要求,訂單送達時間Tij均設為30d,構建不同規模的8個算例,如表4所示。 由于智能算法每次的求解結果不一致,因此取運行20次的結果來保證算法的求解效果。HA-SFLA的參數設置和3.1節相同,不同算例規模下各算法的求解結果對比如表5所示,其中“最優結果”項為不同規模算例下對比分析HA-SFLA和GA、PSO、ACO算法所求得最優成本值。 在求解質量上,通過對比表5中各算法的求解結果可以看出,除算例2中HA-SFLA的求解結果略優于GA,HA-SFLA的求解結果比GA、PSO、ACO均有數量級的優化,說明本文提出的HA-SFLA兩階段算法求解質量明顯優于GA、PSO、ACO。根據雙層規劃的思想,將HA-SFLA整合的兩階段算法,首先使用啟發式算法進行上層規劃的求解,方向性地縮小了下層規劃的解空間;然后采用SFLA求解下層規劃,最后求得的結果保證了客戶的準時送達要求,同時最小化物流成本。同時求解過程中,GA產生大量不滿足滿載約束的非可行解,而由于HA-SFLA中加入啟發式修正規則,求得結果滿足約束。 在求解速度上,規模較小的實驗算例1~3,GA等算法的求解時間在5min左右;中等規模的實驗算例4~5,GA的求解時間在15min左右,PSO、ACO的求解時間也在10min左右;對于算例6~7,GA算法的求解時間在30min左右,PSO、ACO的求解時間超出了20min;對于算例8,GA算法的求解時間為60min左右,PSO、ACO的求解時間為40min左右,遠超出了物流集成商實際訂單分配運作的可接受時間。而由于兩階段算法是在第一階段HA的求解方向性地縮小了解空間,第二SFLA的求解速度更快,HA-SFLA算法的求解時間均未超過5min。隨著算例規模的增大, GA、PSO等的求解時間迅速增加,約為HA-FLSA求解時間的8倍,而HA-SFLA的求解時間均未超過5min。因此,無論是求解效果還是求解速度方面,HA-SFLA兩階段求解算法明顯優于傳統的GA、PSO、ACO,可以提供保證客戶準時送達和物流采購成本更少的訂單分配方案。 4 結語 本文研究了整車LSSC的訂單分配問題,結合整車物流服務供應鏈實際運作方式,考慮運輸方式的技術和經濟特性,建立保證準時送達與最小化物流采購成本的雙層訂單分配模型,然后針對雙層規劃模型的特點,提出了一種整合啟發式算法、混合蛙跳算法的兩階段算法。在算例集上對模型及算法進行了有效性測試,通過實驗對比表明,本文所構建的訂單分配模型能反映整車物流運輸中的運輸方式因素,所設計的兩階段算法能夠較快地求解出質量較高的滿意解。 本文的研究仍存在一定的不足,如未考慮商品車的種類問題。實際中,不同類型的商品車對在不同運輸工具中的裝載量會有所不同,如在轎車型運輸和SUVSport UtilityVehicle,運動型多用途車車型運輸中,可能存在兩種車型混和運輸。后續研究會考慮不同車型的三維裝載對訂單分配問題的影響。 參考文獻 (References) [1] 甘家華,張晉姝,王秀.貨物運輸結構調整: 以汽車整車物流為例[J].綜合運輸,2018,40(7):10-14.(GAN J H, ZHANG J S, WANG X. Transportation structure adjustment of automobile vehicle logistics [J]. China Transportation Review, 2018, 40(7): 10-14.) [2] 劉偉華,季建華,周樂.兩級物流服務供應鏈任務分配模型[J].上海交通大學學報,2008,42(9):1524-1528.(LIU W H, JI J H, ZHOU L. An order allocation model in two-echelon logistics service supply chain [J]. Journal of Shanghai Jiaotong University, 2008, 42(9): 1524-1528.) [3] 姜意揚,王勇,鄧哲鋒.基于LSSC的供應商選擇與訂單分配[J].工業工程,2011,14(3):80-86.(JIANG Y Y, WANG Y, DENG Z F. Supplier selection and order allocation based on logistics service supply chain [J]. Industrial Engineering Journal, 2011, 14(3): 80-86.) [4] 張廣勝,劉偉.考慮服務時效的物流服務供應鏈應急任務分配[J].計算機應用,2016,36(8):2335-2339.(ZHAGN G S, LIU W. Coordinating emergency task allocation of logistics service supply chain under time-to-service [J]. Journal of Computer Applications, 2016, 36(8): 2335-2339.) [5] 李珊珊.物流服務供應鏈訂單分配優化及其遺傳算法[J].運籌與管理,2014,23(5):35-41.(LI S S. Genetic algorithm to logistics service supply chain order allocation problem [J]. Operations Research and Management Science, 2014, 23(5): 35-41.) [6] LIU W H, WU R Z, LIANG Z C, et al. Decision model for the customer order decoupling point considering order insertion scheduling with capacity and time constraints in logistics service supply chain [J]. Applied Mathematical Modeling, 2018, 54: 112-135. [7] 董鵬,宋守文.中國汽車整車物流與零部件物流的分析[J].鐵路采購與物流,2014,9(8):54-55.(DONG P, SONG S W. Analysis of vehicle and parts logistics in China [J]. Railway Purchase and Logistics, 2014, 9(8): 54-55.) [8] 施國洪,錢坤.基于VMI和TPL理論的汽車整車物流的系統動力學分析[J].中國管理信息化,2009,12(20):81-85.(SHI G H, QIAN K. System dynamics analysis of vehicle logistics based on VMI and TPL theory [J]. Chain Management Informationization, 2009, 12(20): 81-85.) [9] 喬露露.汽車整車物流成本控制與績效研究評價[D].西安:長安大學,2011:23-39.(QIAO L L. Study of automobile vehicle logistics cost control and performance evaluation [D]. Xian: Changan University, 2011: 23-39.) [10] 劉大成.“公轉鐵”中整車物流發展的新契機[N].經濟參考報,2018-10-09[2018-11-01].(LIU D C. A new opportunity for the development of vehicle logistics in the “transfer iron” [N]. Economic Reference Daily, 2018-10-09[2018-11-01].) [11] 劉弘超,秦璐,張晉姝.基于合規運輸的第三方整車物流多式聯運網絡優化[J].商業經濟研究,2016,7(23):90-93.(LIU H C, QIN L, ZHANG J S. Optimization of third-party vehicle logistics multimodal transport network based on compliance transportation [J]. Journal of Commercial Economics, 2016, 7(23): 90-93.) [12] MASOUD S A, MASON S J. Assessing the cost impact of multiple transportation modes to enhance sustainability in an integrated, two stage, automotive supply chain [J]. Informatics, 2017, 34: 72-84. [13] 李銳,孫福明.多種運輸方式的4PL多到多網絡設計模型與算法[J].計算機工程與應用,2018,42(3):229-234.(LI R, SUN F M. Model and algorithm for 4PL many-to-many network design with multiple transportation modes [J]. Computer Engineering and Applications, 2018, 54(18): 229-234.) [14] 于雪嶠,郎茂祥,王偉哲,等.考慮模糊需求的多式聯運路徑優化[J].北京交通大學學報,2018,42(3):23-29,36.(YU X Q, LANG M X, WANG W Z, et al. Multimodal transportation routing optimization considering fuzzy demands [J]. Journal of Beijing Jiaotong University, 2018, 42(3): 23-29, 36.) [15] HADDAD-SISAKHT A, RYAN S M. Closed-loop supply chain network design with multiple transportation modes under stochastic demand and uncertain carbon tax [J]. International Journal of Production Economics, 2018, 195: 118-131. [16] EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled forg leaping algorithm [J]. Journal of Water Resources Planning and Management, 2003, 129(3): 210-225. [17] 崔文華,劉曉冰,王偉,等.混合蛙跳算法研究綜述[J].控制與決策,2012,27(4):481-486, 493.(CUI W H, LIU X B, WANG W,et al. Survey on shuffled frog leaping algorithm [J]. Control and Decision, 2012, 27(4): 481-486, 493.) [18] 鄭仕鏈,樓才義,楊小牛.基于改進混合蛙跳算法的認知無線電協作頻譜感知[J].物理學報,2010,59(5):3611-3617.(ZHENG S L, LOU C Y, YANG X N. Cooperative spectrum sensing for cognitive radios based on a modified shuffled frog leaping algorithm [J]. Acta Physica Sinica, 2010, 59(5): 3611-3617.)