蔡 云,邵若楠,寧亞美
(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院,遼寧 大連 116026)
“一帶一路”[1]倡議的提出,為我國鐵路運(yùn)輸發(fā)展帶來機(jī)遇和挑戰(zhàn)。中歐各國貿(mào)易量的快速增長(zhǎng)、進(jìn)出口物流通道網(wǎng)絡(luò)及跨境電子商務(wù)模式等方面的不斷完善,以中歐班列為主角的中歐鐵路運(yùn)輸通道逐漸發(fā)展起來[2]。隨著中歐班列開行規(guī)模、覆蓋范圍不斷擴(kuò)大,所運(yùn)貨物逐漸與當(dāng)?shù)亟?jīng)濟(jì)特點(diǎn)相結(jié)合,因此小批量物資數(shù)量大幅度增加[3]。目前,集裝箱裝載大多依靠工人經(jīng)驗(yàn),對(duì)于復(fù)雜貨物的裝載存在勞動(dòng)效率低、裝載效果差等問題,裝載和拼箱[4]規(guī)劃過程具有很大的優(yōu)化空間,優(yōu)化貨物的裝載和拼箱方式對(duì)降低物流配送成本、提高經(jīng)濟(jì)效益等具有積極意義。
國內(nèi)外許多學(xué)者都對(duì)集裝箱零擔(dān)貨物裝載運(yùn)輸相關(guān)問題進(jìn)行了優(yōu)化研究。王普玉[5]分析了傳統(tǒng)拼箱運(yùn)輸中存在的組織、信息管理等問題,并且為提高拼箱運(yùn)輸效率,提出了信息可視化、工具集裝箱單元化等建議。呂博文,等[6]考慮決策有關(guān)的小批量多起點(diǎn)和目的地貨物的裝卸、整合、轉(zhuǎn)運(yùn)等因素,利用遺傳算法實(shí)現(xiàn)了貨物中轉(zhuǎn)集拼的運(yùn)作優(yōu)化。Thitipong,等[7]分析了集裝箱裝載的工業(yè)及商業(yè)作用,同時(shí)為提高集裝箱空間利用率和減少貨物沖突,提出一種基于擴(kuò)展優(yōu)先級(jí)的混合遺傳算法,有效解決拼箱問題中的實(shí)際問題。崔會(huì)芬,等[8]針對(duì)集裝箱三維裝箱問題,提出一種基于改進(jìn)遺傳算法的人工智能算法,根據(jù)實(shí)際裝箱問題出現(xiàn)的約束條件,建立數(shù)學(xué)優(yōu)化模型,從而有效實(shí)現(xiàn)了集裝箱裝載效率的提高。李偉,等[9]為提高集裝箱的空間利用率,以集裝箱空間利用率最大化為目標(biāo)設(shè)定裝箱方案,提出了一種混合遺傳算法并得到裝箱最優(yōu)解。卜雷,等[10]對(duì)多類型零擔(dān)貨物的拼箱裝配問題進(jìn)行研究,并構(gòu)造合理的個(gè)體編碼適應(yīng)度函數(shù),運(yùn)用遺傳算法優(yōu)化了普零貨物拼箱裝配問題。王祎樓[11]以三維多層貨物裝載布局為研究對(duì)象,結(jié)合貨物裝載的實(shí)際需要,將最大化集裝箱的空間利用率作為首要優(yōu)化目標(biāo),最大化載重率為次要目標(biāo),采用啟發(fā)式算法并通過引入貨物塊的概念優(yōu)化了集裝箱空間利用率。Taylor,等[12]針對(duì)貨物裝箱問題提出了一種混合整數(shù)規(guī)劃模型,通過分層包裝,不僅考慮層高問題,同時(shí)結(jié)合逐層動(dòng)態(tài)規(guī)劃的啟發(fā)式算法進(jìn)行求解,最終獲得滿意解。Toffolo,等[13]以體積利用率最大為目標(biāo)函數(shù),提出了一種通過本地搜索并加以改進(jìn)的基于多階段啟發(fā)式的分解算法,得出快速生成可行解的方法。劉秀田,等[14]提出對(duì)于零擔(dān)專線運(yùn)輸行業(yè)可以通過構(gòu)建“公用型集成化”的方式,并且完成了相關(guān)系統(tǒng)結(jié)構(gòu)、流程及功能的設(shè)計(jì),有效實(shí)現(xiàn)信息化。
綜上所述,目前對(duì)于拼箱運(yùn)輸流程強(qiáng)調(diào)關(guān)注信息化、平臺(tái)化;對(duì)于裝箱方式,大多數(shù)集裝箱貨物裝載優(yōu)化算法集中在三維裝箱上,以實(shí)現(xiàn)較高的空間利用率為優(yōu)化目標(biāo),對(duì)周期性班列存在的未拼箱貨物研究較少。本文以考慮班列周期的集裝箱拼箱運(yùn)輸為研究背景,考慮實(shí)際裝載過程中的諸多約束,在此基礎(chǔ)上搭建數(shù)學(xué)模型,提出一種適應(yīng)本模型的遺傳算法,以拼箱運(yùn)輸總成本最小為優(yōu)化目標(biāo),結(jié)合載重、體積、時(shí)間窗約束構(gòu)建合理的適應(yīng)度函數(shù)。采用幾組具體貨物裝載數(shù)據(jù)進(jìn)行計(jì)算,驗(yàn)證了算法的有效性與實(shí)用性。
本文研究的對(duì)象是抵達(dá)集結(jié)點(diǎn)的數(shù)量不足整箱的小票貨物,根據(jù)貨物目的地分類,同時(shí)根據(jù)貨物時(shí)間窗以及班列周期時(shí)間安排進(jìn)行拼箱優(yōu)化,使得貨物在拼箱過程中,能夠提升拼箱率,降低整體貨運(yùn)成本。針對(duì)本周期未能成功拼箱的貨物問題,基于貨物時(shí)間窗約束以及有限的貨運(yùn)能力約束,將部分貨物放至下周期拼箱任務(wù)中考慮;針對(duì)不同目的地的貨物拼箱組合問題,通過考慮各個(gè)站點(diǎn)是否有貨物進(jìn)行轉(zhuǎn)運(yùn)來進(jìn)行合理分析。拼箱運(yùn)輸方案如圖1所示,為減少集裝箱空箱率,貨物裝箱后將每個(gè)集裝箱內(nèi)貨物按目的地分類,以貨物質(zhì)量總和最大的目的地為該集裝箱目的地,當(dāng)?shù)竭_(dá)該目的地時(shí),將其他目的地貨物卸箱后,通過其他轉(zhuǎn)運(yùn)方式運(yùn)輸至各貨物最終目的地。
圖1 零擔(dān)貨物拼箱運(yùn)輸方案
選擇零擔(dān)貨物配載作為研究對(duì)象,將每個(gè)貨主的貨物記為一票貨,根據(jù)實(shí)際情況及便于求解,做出以下基本假設(shè):
(1)假定不同貨主的貨物可以混裝,且不可分割;
(2)貨物提前到達(dá)班列集結(jié)點(diǎn)等待拼箱,且僅考慮集結(jié)點(diǎn)處待拼箱貨物的拼箱過程;
(3)集裝箱數(shù)量足夠多,不存在貨等箱的情況,但運(yùn)輸量需小于線路最大運(yùn)輸能力;
(4)貨物轉(zhuǎn)運(yùn)過程中,不考慮車輛調(diào)度問題,且不同節(jié)點(diǎn)采用相同的單位轉(zhuǎn)運(yùn)成本;
(5)使用40英尺集裝箱,裝箱時(shí)僅考慮貨物質(zhì)量和體積約束,不考慮裝箱結(jié)構(gòu)問題;
(6)集裝箱利用率不得低于一定限制,且不得超過最大承載量和最大容積;
(7)運(yùn)輸過程中不考慮突發(fā)事件,保證每個(gè)目的節(jié)點(diǎn)準(zhǔn)時(shí)到達(dá)。
1.3.1 集合與參數(shù)
集合:I表示貨物i的集合;M表示目的地m的集合;K表示集裝箱k的集合;表示貨物i可接受到達(dá)時(shí)間窗;H表示弧的集合,表示節(jié)點(diǎn)m到節(jié)點(diǎn)n的距離。
貨物參數(shù):q i表示貨物i的質(zhì)量;v i表示貨物i的體積。
成本參數(shù):c1表示單個(gè)集裝箱使用成本;c2表示單位質(zhì)量貨物裝箱成本;c3表示單位質(zhì)量貨物卸載成本;c4表示單個(gè)集裝箱運(yùn)輸至m地的單位運(yùn)輸成本;c5表示單位質(zhì)量貨物由m地轉(zhuǎn)運(yùn)至n地的運(yùn)輸成本;c6表示單位質(zhì)量未裝箱貨物在集結(jié)點(diǎn)處的堆存成本;c i表示貨物i的逾期懲罰系數(shù)。
時(shí)間參數(shù):t p表示距離下次發(fā)車的時(shí)間間隔;t0m表示班列至m地所需要的時(shí)間;表示由m地轉(zhuǎn)運(yùn)至n地的時(shí)間;T i表示貨物i的到達(dá)時(shí)間表示貨物i能夠到達(dá)的最早時(shí)刻;表示貨物i可接受的最晚到達(dá)時(shí)刻。
集裝箱參數(shù):Gmax表示集裝箱可裝載的最大承載量;Gmin表示集裝箱的最小承載量;Vmax表示集裝箱可裝載的最大裝載容積;Vmin表示集裝箱的最小裝載容積;Q表示線路的最大運(yùn)輸能力。
速度參數(shù):V表示班列運(yùn)輸速度;V'表示轉(zhuǎn)運(yùn)速度。
1.3.2 決策變量
-貨物i在集結(jié)點(diǎn)處裝入集裝箱k處時(shí)為1,否則為0;
-貨物i在m地從集裝箱k處卸載時(shí)為1,否則為0;
Z k-集裝箱k被使用時(shí)為1,否則為0;
B i-貨物i在本周期內(nèi)被安排裝箱為1,否則為0;
-集裝箱k在m地被卸載為1,否則為0;
Wim-貨物i在m地被轉(zhuǎn)運(yùn)為1,否則為0。
零擔(dān)貨物拼箱運(yùn)輸總成本目標(biāo)函數(shù)包括集裝箱的使用成本、貨物裝卸成本、集裝箱運(yùn)輸成本、貨物轉(zhuǎn)運(yùn)成本、未拼箱庫存成本、影響客戶滿意度的逾期懲罰成本,其中,逾期懲罰成本包括未拼箱貨物的逾期懲罰成本和轉(zhuǎn)運(yùn)貨物的逾期懲罰成本。
建立的目標(biāo)函數(shù)如下:
約束條件:
式(1)是零擔(dān)貨物拼箱運(yùn)輸總成本目標(biāo)函數(shù),包括集裝箱的使用成本、貨物裝卸成本、集裝箱運(yùn)輸成本、需轉(zhuǎn)運(yùn)貨物的轉(zhuǎn)運(yùn)成本、未拼箱庫存成本、影響客戶滿意度的逾期懲罰成本。其中,逾期懲罰成本包括未拼箱貨物和需轉(zhuǎn)運(yùn)貨物的逾期懲罰成本。
式(2)表示時(shí)間函數(shù),即每個(gè)貨物的到達(dá)時(shí)間,包括直達(dá)貨物、需轉(zhuǎn)運(yùn)貨物及未拼箱貨物的預(yù)計(jì)到達(dá)時(shí)間。
式(3)表示貨物拼箱約束,即保證本周期的拼箱貨物全部裝箱;式(4)表示貨物裝卸箱限制,即拼箱貨物裝箱與卸箱流程需要對(duì)應(yīng);式(5)表示同一貨主的貨物裝箱約束,即同一貨主的貨物不能分箱包裝;式(6)表示集裝箱貨物數(shù)量約束,即每個(gè)集裝箱中存在至少一票貨物;式(7)表示貨物卸箱限制,即所有拼箱貨物都隨集裝箱卸箱而卸載;式(8)表示貨物的轉(zhuǎn)運(yùn)限制,即貨物僅在卸載節(jié)點(diǎn)處被轉(zhuǎn)運(yùn);式(9)表示貨物到達(dá)的時(shí)間約束,即貨物到達(dá)時(shí)間在顧客能接受的時(shí)間窗內(nèi);式(10)表示集裝箱質(zhì)量約束,即集裝箱內(nèi)質(zhì)量總和不低于最小承載量,且不超過最大承載量;式(11)表示集裝箱體積約束,即集裝箱內(nèi)體積總和不低于最小容積,且不超過最大容積;式(12)表示貨運(yùn)量約束,即貨物的運(yùn)量不超過線路的運(yùn)輸能力;式(13)-(18)表示0-1約束。
集結(jié)點(diǎn)零擔(dān)貨物拼箱運(yùn)輸優(yōu)化模型包含貨物的裝卸分配以及站點(diǎn)轉(zhuǎn)運(yùn)問題,因此是一個(gè)具有復(fù)雜條件的組合優(yōu)化問題,屬于NP-hard問題。本文針對(duì)拼箱運(yùn)輸?shù)幕旌险麛?shù)規(guī)劃問題,基于遺傳算法,求解出整個(gè)過程中總成本最小的拼箱運(yùn)輸方案。
步驟1 初始化種群Chrom,每條染色體代表每個(gè)貨物序號(hào)對(duì)應(yīng)的拼箱分配編號(hào);
步驟2 解碼染色體,計(jì)算每個(gè)染色體對(duì)應(yīng)的適應(yīng)度值,即拼箱運(yùn)輸過程中的總成本;
步驟3 判斷是否滿足迭代停止條件:最大的遺傳代數(shù),若滿足,則結(jié)束算法操作,否則轉(zhuǎn)步驟2,進(jìn)行適應(yīng)度值的計(jì)算;
步驟4 選取適應(yīng)度值相對(duì)最大的染色體組成新的種群;
步驟5 以新種群作為父代,按照交叉概率P c,變異概率P m執(zhí)行對(duì)應(yīng)算子,獲得子代,重復(fù)進(jìn)行步驟2的操作。
本文的染色體編碼和解碼過程如圖2所示。編碼采用雙層染色體實(shí)數(shù)編碼方式,第一層編碼為維度可變的貨物編號(hào)序列,第二層編碼為對(duì)應(yīng)貨物的擬定裝箱編號(hào)。解碼過程首先根據(jù)相同的擬定裝箱編號(hào)分類,同編號(hào)的貨物裝入同一集裝箱,其次再按擬定裝箱編號(hào)由0開始重新順序排列,形成最終裝箱編號(hào),其中0號(hào)箱表示未拼箱貨物的集合。
圖2 染色體編碼與解碼方式
根據(jù)目標(biāo)函數(shù)中拼箱運(yùn)輸總成本最小化,計(jì)算適應(yīng)度的步驟如下:
步驟1 對(duì)所有染色體進(jìn)行編碼解碼,形成拼箱方案,包括拼箱貨物的裝箱方案和未拼箱貨物,根據(jù)集裝箱數(shù)量計(jì)算集裝箱固定使用成本C1和拼箱貨物的裝卸成本C2;
步驟2 在拼箱貨物的裝箱方案中,設(shè)置集裝箱質(zhì)量體積、客戶時(shí)間窗以及轉(zhuǎn)運(yùn)次數(shù)的約束條件,對(duì)不符合約束條件的方案,給予一個(gè)較大的懲罰因子,計(jì)算其懲罰成本C p;
步驟3 將每個(gè)集裝箱內(nèi)的貨物按運(yùn)輸目的地進(jìn)行分類,計(jì)算每個(gè)類別的貨物總質(zhì)量,總質(zhì)量最大的貨物目的地為該集裝箱目的地,集裝箱到達(dá)后進(jìn)行卸箱及其他目的地貨物的轉(zhuǎn)運(yùn),計(jì)算集裝箱運(yùn)輸成本C3和貨物轉(zhuǎn)運(yùn)成本C4;
步驟4 對(duì)于未拼箱貨物計(jì)算其庫存成本C5;
步驟5 根據(jù)班列周期及貨物質(zhì)量,計(jì)算總的時(shí)間懲罰成本C6,其中包括未拼箱貨物和拼箱貨物的逾期懲罰成本;
步驟6 計(jì)算拼箱運(yùn)輸總成本C=C1+C2+C3+C4+C5+C6+C p,種群的適應(yīng)度值為f it=1/C,計(jì)算種群的適應(yīng)度值。
為了考察模型與算法的有效性,本文以“義新歐”班列的義烏-馬德里線路為例,并假設(shè)集結(jié)點(diǎn)現(xiàn)有50個(gè)貨主的貨物等待拼箱作業(yè)。班列由阿拉山口出境,根據(jù)貨主需求將貨物分別發(fā)往4個(gè)目的站點(diǎn),按途徑順序分別為馬拉舍維奇、杜伊斯堡、巴黎、馬德里。使用40英尺國際標(biāo)準(zhǔn)通用集裝箱,規(guī)定集裝箱承載量范圍為13~26t,裝載容積范圍為27~54m3,且班列發(fā)車間隔時(shí)間為3d,班列運(yùn)輸速度為120km/h,轉(zhuǎn)運(yùn)速度為75km/h。貨物相關(guān)信息和單位成本信息見表1、表2。
表1 貨物信息
表2 單位成本信息
表3表明了客戶時(shí)間窗與逾期懲罰的相關(guān)性。班列集結(jié)點(diǎn)根據(jù)不同客戶的時(shí)間窗要求,得出客戶能接受的延遲天數(shù),因此判斷出客戶能接受的逾期程度以設(shè)定相對(duì)應(yīng)的不同客戶能接受延遲的天數(shù)對(duì)應(yīng)的逾期懲罰系數(shù)。
表3 客戶滿意度相關(guān)變量對(duì)應(yīng)關(guān)系
3.2.1 模型有效性驗(yàn)證。優(yōu)化算法通過Python語言編寫,設(shè)置其種群規(guī)模為300,迭代次數(shù)為300代,其中到達(dá)50代時(shí),曲線趨于收斂趨勢(shì),其后相對(duì)收斂緩慢,此時(shí)的滿意成本是301 915.35元,需要安排6個(gè)集裝箱,以滿足整體作業(yè)要求,迭代曲線圖如圖3所示,貨物拼箱運(yùn)輸方案見表4。
圖3 迭代曲線
根據(jù)表4的貨物拼箱運(yùn)輸方案,未拼箱的貨物于下一周期班列貨物進(jìn)行拼箱運(yùn)輸,該貨物對(duì)逾期的影響較小,且能接受延遲天數(shù)為3,與發(fā)車間隔時(shí)間相同,滿足該客戶時(shí)間窗;所有轉(zhuǎn)運(yùn)貨物的到達(dá)時(shí)間也均滿足客戶時(shí)間窗。因此,通過對(duì)貨物拼箱運(yùn)輸方案的分析,驗(yàn)證了算法的有效性及可行性。
表4 集裝箱目的地及貨物裝箱分布
零擔(dān)貨物拼箱運(yùn)輸優(yōu)化前后各成本及集裝箱平均利用率見表5。根據(jù)50件貨物的原始拼箱方案,以目的地分類進(jìn)行全體拼箱,共需8個(gè)集裝箱。而進(jìn)行優(yōu)化的拼箱方案僅需6個(gè)集裝箱,且優(yōu)化后的集裝箱噸位利用率和容積利用率均增長(zhǎng)了21%。
表5 優(yōu)化前后各成本及利用率對(duì)比
從各成本對(duì)比來看,集裝箱使用數(shù)量的減少對(duì)各成本均有不同程度的影響。其中,集裝箱運(yùn)輸成本占總成本約94%,優(yōu)化后增加的轉(zhuǎn)運(yùn)成本、未拼箱貨物的庫存成本及影響客戶滿意度的逾期懲罰成本之和占總成本約4%。因此,集裝箱個(gè)數(shù)的減少能夠有效的減少總體運(yùn)輸成本。
根據(jù)資料中歐班列出口需求旺盛,常出現(xiàn)“一箱難求”現(xiàn)象;然而境外攬貨能力不足,“重去空回”現(xiàn)象突出。因此,零擔(dān)貨物拼箱運(yùn)輸優(yōu)化后集裝箱使用減少,不僅可以在中歐班列去程時(shí)提高集裝箱裝載率和減少運(yùn)輸成本,而且對(duì)于返程時(shí)集裝箱利用率提高及運(yùn)輸成本降低有很大程度影響,實(shí)現(xiàn)資源的極大利用。
3.2.2 模型參數(shù)敏感性分析。優(yōu)化后的拼箱運(yùn)輸方案增加了貨物轉(zhuǎn)運(yùn)成本、未拼箱庫存成本及影響客戶滿意度的逾期懲罰成本。其中,班列發(fā)車間隔天數(shù)是影響客戶滿意度的逾期懲罰成本的主要因素;同時(shí),轉(zhuǎn)運(yùn)速度和單位轉(zhuǎn)運(yùn)成本主要影響需中轉(zhuǎn)貨物的轉(zhuǎn)運(yùn)成本和逾期懲罰成本,因此,本文對(duì)其相關(guān)變量進(jìn)行敏感性分析。
(1)班列周期變化分析。班列發(fā)車間隔天數(shù)對(duì)貨物裝卸成本、貨物轉(zhuǎn)運(yùn)成本、未拼箱庫存成本以及逾期懲罰成本有影響。通過圖4可以看出,班列周期變化對(duì)貨物轉(zhuǎn)運(yùn)成本、未拼箱庫存成本和未拼箱逾期成本有較大影響,隨著班列發(fā)車間隔天數(shù)減少,待轉(zhuǎn)運(yùn)的貨物可以在規(guī)定時(shí)間窗內(nèi)跟隨下一班列進(jìn)行拼箱運(yùn)輸,能夠減少一定的轉(zhuǎn)運(yùn)成本;同時(shí)通過圖5可以看出,總成本的變化曲線和轉(zhuǎn)運(yùn)成本的變化曲線較為相似,這意味著,增加轉(zhuǎn)運(yùn)貨物可以有效減少集裝箱的使用,同時(shí)減少總運(yùn)輸成本,在班列周期時(shí)間減少時(shí),可以有效減少轉(zhuǎn)運(yùn)成本同時(shí)減少總運(yùn)輸成本。因此,在中歐班列的零擔(dān)貨物數(shù)量足夠多時(shí),中歐班列運(yùn)行班次根據(jù)需求隨之增加時(shí),發(fā)車間隔時(shí)間越短,可以在客戶規(guī)定時(shí)間窗內(nèi)將待轉(zhuǎn)運(yùn)貨物跟隨下一周期班列進(jìn)行拼箱運(yùn)輸,能夠有效減少貨物轉(zhuǎn)運(yùn)成本,提升班列運(yùn)輸?shù)慕?jīng)濟(jì)效益。
圖4 班列發(fā)車間隔天數(shù)對(duì)各成本影響圖
圖5 總成本及各成本占成本比例圖
圖6 轉(zhuǎn)運(yùn)速度/單位轉(zhuǎn)運(yùn)成本影響圖
國家“一帶一路”倡議為鐵路國際聯(lián)運(yùn)發(fā)展和物流化轉(zhuǎn)型帶來了良好機(jī)遇,同時(shí)跨境電商及中小型企業(yè)的迅猛發(fā)展,中歐班列的拼箱需求增多,拼箱運(yùn)輸是大量零擔(dān)貨物運(yùn)輸?shù)闹饕緩?。本文?duì)中歐班列的零擔(dān)貨物拼箱運(yùn)輸優(yōu)化問題進(jìn)行分析,通過分析拼箱方案、是否轉(zhuǎn)運(yùn)及客戶滿意度,提供了一種基于班列集結(jié)點(diǎn)的拼箱運(yùn)輸優(yōu)化機(jī)制。通過設(shè)計(jì)改進(jìn)的遺傳算法進(jìn)行優(yōu)化計(jì)算,得出以下結(jié)論:(1)針對(duì)班列集結(jié)點(diǎn)零擔(dān)貨物的拼箱運(yùn)輸優(yōu)化,在考慮客戶時(shí)間窗及班列周期的基礎(chǔ)上,同時(shí)綜合考慮復(fù)雜的零擔(dān)貨物是否拼箱以及拼箱貨物在各目的節(jié)點(diǎn)是否轉(zhuǎn)運(yùn),可以提高集裝箱利用率,減少運(yùn)輸總成本,對(duì)資源進(jìn)行合理分配利用;(2)班列發(fā)車間隔天數(shù)減少、班次的增加,能夠有效減少轉(zhuǎn)運(yùn)費(fèi)用以及總運(yùn)輸成本;(3)轉(zhuǎn)運(yùn)速度的提升,可以有效減少轉(zhuǎn)運(yùn)成本及運(yùn)輸時(shí)間,提高客戶滿意度,優(yōu)化班列全程運(yùn)輸效率。