考慮班列周期的零擔貨物集結點拼箱運輸優(yōu)化

蔡 云，邵若楠，寧亞美

（大連海事大學 交通運輸工程學院，遼寧 大連 116026）

0 引言

“一帶一路”[1]倡議的提出，為我國鐵路運輸發(fā)展帶來機遇和挑戰(zhàn)。中歐各國貿易量的快速增長、進出口物流通道網(wǎng)絡及跨境電子商務模式等方面的不斷完善，以中歐班列為主角的中歐鐵路運輸通道逐漸發(fā)展起來[2]。隨著中歐班列開行規(guī)模、覆蓋范圍不斷擴大，所運貨物逐漸與當?shù)亟?jīng)濟特點相結合，因此小批量物資數(shù)量大幅度增加[3]。目前，集裝箱裝載大多依靠工人經(jīng)驗，對于復雜貨物的裝載存在勞動效率低、裝載效果差等問題，裝載和拼箱[4]規(guī)劃過程具有很大的優(yōu)化空間，優(yōu)化貨物的裝載和拼箱方式對降低物流配送成本、提高經(jīng)濟效益等具有積極意義。

國內外許多學者都對集裝箱零擔貨物裝載運輸相關問題進行了優(yōu)化研究。王普玉[5]分析了傳統(tǒng)拼箱運輸中存在的組織、信息管理等問題，并且為提高拼箱運輸效率，提出了信息可視化、工具集裝箱單元化等建議。呂博文，等[6]考慮決策有關的小批量多起點和目的地貨物的裝卸、整合、轉運等因素，利用遺傳算法實現(xiàn)了貨物中轉集拼的運作優(yōu)化。Thitipong，等[7]分析了集裝箱裝載的工業(yè)及商業(yè)作用，同時為提高集裝箱空間利用率和減少貨物沖突，提出一種基于擴展優(yōu)先級的混合遺傳算法，有效解決拼箱問題中的實際問題。崔會芬，等[8]針對集裝箱三維裝箱問題，提出一種基于改進遺傳算法的人工智能算法，根據(jù)實際裝箱問題出現(xiàn)的約束條件，建立數(shù)學優(yōu)化模型，從而有效實現(xiàn)了集裝箱裝載效率的提高。李偉，等[9]為提高集裝箱的空間利用率，以集裝箱空間利用率最大化為目標設定裝箱方案，提出了一種混合遺傳算法并得到裝箱最優(yōu)解。卜雷，等[10]對多類型零擔貨物的拼箱裝配問題進行研究，并構造合理的個體編碼適應度函數(shù)，運用遺傳算法優(yōu)化了普零貨物拼箱裝配問題。王祎樓[11]以三維多層貨物裝載布局為研究對象，結合貨物裝載的實際需要，將最大化集裝箱的空間利用率作為首要優(yōu)化目標，最大化載重率為次要目標，采用啟發(fā)式算法并通過引入貨物塊的概念優(yōu)化了集裝箱空間利用率。Taylor，等[12]針對貨物裝箱問題提出了一種混合整數(shù)規(guī)劃模型，通過分層包裝，不僅考慮層高問題，同時結合逐層動態(tài)規(guī)劃的啟發(fā)式算法進行求解，最終獲得滿意解。Toffolo，等[13]以體積利用率最大為目標函數(shù)，提出了一種通過本地搜索并加以改進的基于多階段啟發(fā)式的分解算法，得出快速生成可行解的方法。劉秀田，等[14]提出對于零擔專線運輸行業(yè)可以通過構建“公用型集成化”的方式，并且完成了相關系統(tǒng)結構、流程及功能的設計，有效實現(xiàn)信息化。

綜上所述，目前對于拼箱運輸流程強調關注信息化、平臺化；對于裝箱方式，大多數(shù)集裝箱貨物裝載優(yōu)化算法集中在三維裝箱上，以實現(xiàn)較高的空間利用率為優(yōu)化目標，對周期性班列存在的未拼箱貨物研究較少。本文以考慮班列周期的集裝箱拼箱運輸為研究背景，考慮實際裝載過程中的諸多約束，在此基礎上搭建數(shù)學模型，提出一種適應本模型的遺傳算法，以拼箱運輸總成本最小為優(yōu)化目標，結合載重、體積、時間窗約束構建合理的適應度函數(shù)。采用幾組具體貨物裝載數(shù)據(jù)進行計算，驗證了算法的有效性與實用性。

1 問題描述及建模

1.1 問題描述

本文研究的對象是抵達集結點的數(shù)量不足整箱的小票貨物，根據(jù)貨物目的地分類，同時根據(jù)貨物時間窗以及班列周期時間安排進行拼箱優(yōu)化，使得貨物在拼箱過程中，能夠提升拼箱率，降低整體貨運成本。針對本周期未能成功拼箱的貨物問題，基于貨物時間窗約束以及有限的貨運能力約束，將部分貨物放至下周期拼箱任務中考慮；針對不同目的地的貨物拼箱組合問題，通過考慮各個站點是否有貨物進行轉運來進行合理分析。拼箱運輸方案如圖1所示，為減少集裝箱空箱率，貨物裝箱后將每個集裝箱內貨物按目的地分類，以貨物質量總和最大的目的地為該集裝箱目的地，當?shù)竭_該目的地時，將其他目的地貨物卸箱后，通過其他轉運方式運輸至各貨物最終目的地。

圖1 零擔貨物拼箱運輸方案

1.2 基本假設

選擇零擔貨物配載作為研究對象，將每個貨主的貨物記為一票貨，根據(jù)實際情況及便于求解，做出以下基本假設：

（1）假定不同貨主的貨物可以混裝，且不可分割；

（2）貨物提前到達班列集結點等待拼箱，且僅考慮集結點處待拼箱貨物的拼箱過程；

（3）集裝箱數(shù)量足夠多，不存在貨等箱的情況，但運輸量需小于線路最大運輸能力；

（4）貨物轉運過程中，不考慮車輛調度問題，且不同節(jié)點采用相同的單位轉運成本；

（5）使用40英尺集裝箱，裝箱時僅考慮貨物質量和體積約束，不考慮裝箱結構問題；

（6）集裝箱利用率不得低于一定限制，且不得超過最大承載量和最大容積；

（7）運輸過程中不考慮突發(fā)事件，保證每個目的節(jié)點準時到達。

1.3 符號說明

1.3.1 集合與參數(shù)

集合：I表示貨物i的集合；M表示目的地m的集合；K表示集裝箱k的集合；表示貨物i可接受到達時間窗；H表示弧的集合，表示節(jié)點m到節(jié)點n的距離。

貨物參數(shù)：q i表示貨物i的質量；v i表示貨物i的體積。

成本參數(shù)：c1表示單個集裝箱使用成本；c2表示單位質量貨物裝箱成本；c3表示單位質量貨物卸載成本；c4表示單個集裝箱運輸至m地的單位運輸成本；c5表示單位質量貨物由m地轉運至n地的運輸成本；c6表示單位質量未裝箱貨物在集結點處的堆存成本；c i表示貨物i的逾期懲罰系數(shù)。

時間參數(shù)：t p表示距離下次發(fā)車的時間間隔；t0m表示班列至m地所需要的時間；表示由m地轉運至n地的時間；T i表示貨物i的到達時間表示貨物i能夠到達的最早時刻；表示貨物i可接受的最晚到達時刻。

集裝箱參數(shù)：Gmax表示集裝箱可裝載的最大承載量；Gmin表示集裝箱的最小承載量；Vmax表示集裝箱可裝載的最大裝載容積；Vmin表示集裝箱的最小裝載容積；Q表示線路的最大運輸能力。

速度參數(shù)：V表示班列運輸速度；V'表示轉運速度。

1.3.2 決策變量

-貨物i在集結點處裝入集裝箱k處時為1，否則為0；

-貨物i在m地從集裝箱k處卸載時為1，否則為0；

Z k-集裝箱k被使用時為1，否則為0；

B i-貨物i在本周期內被安排裝箱為1，否則為0；

-集裝箱k在m地被卸載為1，否則為0；

Wim-貨物i在m地被轉運為1，否則為0。

1.4 模型建立

零擔貨物拼箱運輸總成本目標函數(shù)包括集裝箱的使用成本、貨物裝卸成本、集裝箱運輸成本、貨物轉運成本、未拼箱庫存成本、影響客戶滿意度的逾期懲罰成本，其中，逾期懲罰成本包括未拼箱貨物的逾期懲罰成本和轉運貨物的逾期懲罰成本。

建立的目標函數(shù)如下：

約束條件：

式（1）是零擔貨物拼箱運輸總成本目標函數(shù)，包括集裝箱的使用成本、貨物裝卸成本、集裝箱運輸成本、需轉運貨物的轉運成本、未拼箱庫存成本、影響客戶滿意度的逾期懲罰成本。其中，逾期懲罰成本包括未拼箱貨物和需轉運貨物的逾期懲罰成本。

式（2）表示時間函數(shù)，即每個貨物的到達時間，包括直達貨物、需轉運貨物及未拼箱貨物的預計到達時間。

式（3）表示貨物拼箱約束，即保證本周期的拼箱貨物全部裝箱；式（4）表示貨物裝卸箱限制，即拼箱貨物裝箱與卸箱流程需要對應；式（5）表示同一貨主的貨物裝箱約束，即同一貨主的貨物不能分箱包裝；式（6）表示集裝箱貨物數(shù)量約束，即每個集裝箱中存在至少一票貨物；式（7）表示貨物卸箱限制，即所有拼箱貨物都隨集裝箱卸箱而卸載；式（8）表示貨物的轉運限制，即貨物僅在卸載節(jié)點處被轉運；式（9）表示貨物到達的時間約束，即貨物到達時間在顧客能接受的時間窗內；式（10）表示集裝箱質量約束，即集裝箱內質量總和不低于最小承載量，且不超過最大承載量；式（11）表示集裝箱體積約束，即集裝箱內體積總和不低于最小容積，且不超過最大容積；式（12）表示貨運量約束，即貨物的運量不超過線路的運輸能力；式（13）-（18）表示0-1約束。

2 求解算法

集結點零擔貨物拼箱運輸優(yōu)化模型包含貨物的裝卸分配以及站點轉運問題，因此是一個具有復雜條件的組合優(yōu)化問題，屬于NP-hard問題。本文針對拼箱運輸?shù)幕旌险麛?shù)規(guī)劃問題，基于遺傳算法，求解出整個過程中總成本最小的拼箱運輸方案。

2.1 算法步驟

步驟1 初始化種群Chrom，每條染色體代表每個貨物序號對應的拼箱分配編號；

步驟2 解碼染色體，計算每個染色體對應的適應度值，即拼箱運輸過程中的總成本；

步驟3 判斷是否滿足迭代停止條件：最大的遺傳代數(shù)，若滿足，則結束算法操作，否則轉步驟2，進行適應度值的計算；

步驟4 選取適應度值相對最大的染色體組成新的種群；

步驟5 以新種群作為父代，按照交叉概率P c，變異概率P m執(zhí)行對應算子，獲得子代，重復進行步驟2的操作。

2.2 編碼和解碼

本文的染色體編碼和解碼過程如圖2所示。編碼采用雙層染色體實數(shù)編碼方式，第一層編碼為維度可變的貨物編號序列，第二層編碼為對應貨物的擬定裝箱編號。解碼過程首先根據(jù)相同的擬定裝箱編號分類，同編號的貨物裝入同一集裝箱，其次再按擬定裝箱編號由0開始重新順序排列，形成最終裝箱編號，其中0號箱表示未拼箱貨物的集合。

圖2 染色體編碼與解碼方式

2.3 適應度計算

根據(jù)目標函數(shù)中拼箱運輸總成本最小化，計算適應度的步驟如下：

步驟1 對所有染色體進行編碼解碼，形成拼箱方案，包括拼箱貨物的裝箱方案和未拼箱貨物，根據(jù)集裝箱數(shù)量計算集裝箱固定使用成本C1和拼箱貨物的裝卸成本C2；

步驟2 在拼箱貨物的裝箱方案中，設置集裝箱質量體積、客戶時間窗以及轉運次數(shù)的約束條件，對不符合約束條件的方案，給予一個較大的懲罰因子，計算其懲罰成本C p；

步驟3 將每個集裝箱內的貨物按運輸目的地進行分類，計算每個類別的貨物總質量，總質量最大的貨物目的地為該集裝箱目的地，集裝箱到達后進行卸箱及其他目的地貨物的轉運，計算集裝箱運輸成本C3和貨物轉運成本C4；

步驟4 對于未拼箱貨物計算其庫存成本C5；

步驟5 根據(jù)班列周期及貨物質量，計算總的時間懲罰成本C6，其中包括未拼箱貨物和拼箱貨物的逾期懲罰成本；

步驟6 計算拼箱運輸總成本C=C1+C2+C3+C4+C5+C6+C p，種群的適應度值為f it=1/C，計算種群的適應度值。

3 算例分析

3.1 數(shù)據(jù)描述

為了考察模型與算法的有效性，本文以“義新歐”班列的義烏-馬德里線路為例，并假設集結點現(xiàn)有50個貨主的貨物等待拼箱作業(yè)。班列由阿拉山口出境，根據(jù)貨主需求將貨物分別發(fā)往4個目的站點，按途徑順序分別為馬拉舍維奇、杜伊斯堡、巴黎、馬德里。使用40英尺國際標準通用集裝箱，規(guī)定集裝箱承載量范圍為13～26t，裝載容積范圍為27～54m3，且班列發(fā)車間隔時間為3d，班列運輸速度為120km/h，轉運速度為75km/h。貨物相關信息和單位成本信息見表1、表2。

表1 貨物信息

表2 單位成本信息

表3表明了客戶時間窗與逾期懲罰的相關性。班列集結點根據(jù)不同客戶的時間窗要求，得出客戶能接受的延遲天數(shù)，因此判斷出客戶能接受的逾期程度以設定相對應的不同客戶能接受延遲的天數(shù)對應的逾期懲罰系數(shù)。

表3 客戶滿意度相關變量對應關系

3.2 結果與分析

3.2.1 模型有效性驗證。優(yōu)化算法通過Python語言編寫，設置其種群規(guī)模為300，迭代次數(shù)為300代，其中到達50代時，曲線趨于收斂趨勢，其后相對收斂緩慢，此時的滿意成本是301 915.35元，需要安排6個集裝箱，以滿足整體作業(yè)要求，迭代曲線圖如圖3所示，貨物拼箱運輸方案見表4。

圖3 迭代曲線

根據(jù)表4的貨物拼箱運輸方案，未拼箱的貨物于下一周期班列貨物進行拼箱運輸，該貨物對逾期的影響較小，且能接受延遲天數(shù)為3，與發(fā)車間隔時間相同，滿足該客戶時間窗；所有轉運貨物的到達時間也均滿足客戶時間窗。因此，通過對貨物拼箱運輸方案的分析，驗證了算法的有效性及可行性。

表4 集裝箱目的地及貨物裝箱分布

零擔貨物拼箱運輸優(yōu)化前后各成本及集裝箱平均利用率見表5。根據(jù)50件貨物的原始拼箱方案，以目的地分類進行全體拼箱，共需8個集裝箱。而進行優(yōu)化的拼箱方案僅需6個集裝箱，且優(yōu)化后的集裝箱噸位利用率和容積利用率均增長了21%。

表5 優(yōu)化前后各成本及利用率對比

從各成本對比來看，集裝箱使用數(shù)量的減少對各成本均有不同程度的影響。其中，集裝箱運輸成本占總成本約94%，優(yōu)化后增加的轉運成本、未拼箱貨物的庫存成本及影響客戶滿意度的逾期懲罰成本之和占總成本約4%。因此，集裝箱個數(shù)的減少能夠有效的減少總體運輸成本。

根據(jù)資料中歐班列出口需求旺盛，常出現(xiàn)“一箱難求”現(xiàn)象；然而境外攬貨能力不足，“重去空回”現(xiàn)象突出。因此，零擔貨物拼箱運輸優(yōu)化后集裝箱使用減少，不僅可以在中歐班列去程時提高集裝箱裝載率和減少運輸成本，而且對于返程時集裝箱利用率提高及運輸成本降低有很大程度影響，實現(xiàn)資源的極大利用。

3.2.2 模型參數(shù)敏感性分析。優(yōu)化后的拼箱運輸方案增加了貨物轉運成本、未拼箱庫存成本及影響客戶滿意度的逾期懲罰成本。其中，班列發(fā)車間隔天數(shù)是影響客戶滿意度的逾期懲罰成本的主要因素；同時，轉運速度和單位轉運成本主要影響需中轉貨物的轉運成本和逾期懲罰成本，因此，本文對其相關變量進行敏感性分析。

（1）班列周期變化分析。班列發(fā)車間隔天數(shù)對貨物裝卸成本、貨物轉運成本、未拼箱庫存成本以及逾期懲罰成本有影響。通過圖4可以看出，班列周期變化對貨物轉運成本、未拼箱庫存成本和未拼箱逾期成本有較大影響，隨著班列發(fā)車間隔天數(shù)減少，待轉運的貨物可以在規(guī)定時間窗內跟隨下一班列進行拼箱運輸，能夠減少一定的轉運成本；同時通過圖5可以看出，總成本的變化曲線和轉運成本的變化曲線較為相似，這意味著，增加轉運貨物可以有效減少集裝箱的使用，同時減少總運輸成本，在班列周期時間減少時，可以有效減少轉運成本同時減少總運輸成本。因此，在中歐班列的零擔貨物數(shù)量足夠多時，中歐班列運行班次根據(jù)需求隨之增加時，發(fā)車間隔時間越短，可以在客戶規(guī)定時間窗內將待轉運貨物跟隨下一周期班列進行拼箱運輸，能夠有效減少貨物轉運成本，提升班列運輸?shù)慕?jīng)濟效益。

圖4 班列發(fā)車間隔天數(shù)對各成本影響圖

圖5 總成本及各成本占成本比例圖

圖6 轉運速度/單位轉運成本影響圖

4 結語

國家“一帶一路”倡議為鐵路國際聯(lián)運發(fā)展和物流化轉型帶來了良好機遇，同時跨境電商及中小型企業(yè)的迅猛發(fā)展，中歐班列的拼箱需求增多，拼箱運輸是大量零擔貨物運輸?shù)闹饕緩健１疚膶χ袣W班列的零擔貨物拼箱運輸優(yōu)化問題進行分析，通過分析拼箱方案、是否轉運及客戶滿意度，提供了一種基于班列集結點的拼箱運輸優(yōu)化機制。通過設計改進的遺傳算法進行優(yōu)化計算，得出以下結論：（1）針對班列集結點零擔貨物的拼箱運輸優(yōu)化，在考慮客戶時間窗及班列周期的基礎上，同時綜合考慮復雜的零擔貨物是否拼箱以及拼箱貨物在各目的節(jié)點是否轉運，可以提高集裝箱利用率，減少運輸總成本，對資源進行合理分配利用；（2）班列發(fā)車間隔天數(shù)減少、班次的增加，能夠有效減少轉運費用以及總運輸成本；（3）轉運速度的提升，可以有效減少轉運成本及運輸時間，提高客戶滿意度，優(yōu)化班列全程運輸效率。