基于貪婪算法的跨境物流系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

李業(yè) 王世華 胡傳華 吳思瑩

（1.深圳市格布領(lǐng)客信息科技有限公司 廣東省深圳市 518000）

（2.廣東石油化工學(xué)院理學(xué)院 廣東省茂名市 525000）

1 引言

隨著全球經(jīng)濟(jì)不斷朝著一體化方向發(fā)展和“一帶一路”倡議的深入推進(jìn)，我國對(duì)外貿(mào)易發(fā)展迅猛，跨境物流的發(fā)展在跨境交易中起著重要的紐帶作用。根據(jù)國家郵政局2021年5月郵政行業(yè)運(yùn)行情況顯示：國際/港澳臺(tái)業(yè)務(wù)達(dá)1.86 億件，同比增長26.9%。我國跨境運(yùn)輸物品不斷增多，而我國跨境物流服務(wù)體系不完善、數(shù)字化和智能化程度低，導(dǎo)致我國物流行業(yè)的發(fā)展相對(duì)落后。物流成本高成為跨境物流行業(yè)發(fā)展的痛點(diǎn)之一?？缇车钠奉愒龆?，重量大、體積大的物品也越來越多，各類物品打包成本也大大增加。優(yōu)化物流服務(wù)模式，加快搭建信息系統(tǒng)化平臺(tái)，能夠更好地促進(jìn)我國跨境物流服務(wù)的轉(zhuǎn)型與發(fā)展。如何優(yōu)化包裹，降低物流成本成為了亟需解決的問題。

由于跨境運(yùn)輸中存在商品種類局限性大、物流時(shí)效慢、運(yùn)輸成本高等問題，而現(xiàn)有的跨境物流企業(yè)服務(wù)中出現(xiàn)服務(wù)效率底，服務(wù)模式零散，服務(wù)功能單一的狀況。國內(nèi)外學(xué)者對(duì)相關(guān)的問題作出了研究。

國外學(xué)者主要在物流成本以及物流分揀上的做的研究有：文探討了受物品數(shù)量影響的一體化運(yùn)輸成本和需求呈下降趨勢的價(jià)格策略，同時(shí)構(gòu)造了一個(gè)能夠確定最佳物品數(shù)量和物流最優(yōu)價(jià)格的決策模型。文認(rèn)為配送中心的布局對(duì)物流系統(tǒng)的設(shè)計(jì)產(chǎn)生重要影響，因此提出了一個(gè)綜合上述因素的模型和方法。國外在物流方面物品的分揀早在20 世紀(jì)60年代開始，國外就已經(jīng)開始著手研究檢測，分揀系統(tǒng)模型等。20 世紀(jì)80年代后，國外將分揀系統(tǒng)與不同的輸送帶有機(jī)結(jié)合起來，形成了一個(gè)高效的分揀系統(tǒng)。國外對(duì)于跨境物流網(wǎng)絡(luò)環(huán)境的優(yōu)化以及相關(guān)信息平臺(tái)技術(shù)的研究搭建主要在路徑優(yōu)化、基礎(chǔ)設(shè)施的搭建、貨物存儲(chǔ)轉(zhuǎn)運(yùn)的設(shè)計(jì)。文通過建立更加符合現(xiàn)實(shí)需求的跨境物流網(wǎng)絡(luò)，將本土物流網(wǎng)絡(luò)與跨境物流網(wǎng)絡(luò)整合起來，使得境內(nèi)物流管理與跨境物流更好的復(fù)合在一起。將自適應(yīng)權(quán)重遺傳算法作為該文研究問題的主解決方法。探討了海運(yùn)、內(nèi)陸等不同網(wǎng)絡(luò)物流背景下的進(jìn)出口貨物的組織優(yōu)化問題。文作者通過分析第四方物流、海外倉儲(chǔ)和物流聯(lián)盟三種不同的跨境物流模式的優(yōu)缺點(diǎn)等，設(shè)計(jì)提出了新的跨境企業(yè)物流模式的選擇原則。文作者認(rèn)為為了實(shí)現(xiàn)跨境電商物流模式的轉(zhuǎn)型與發(fā)展，采用跨境電商物流樞紐園區(qū)模式和保稅區(qū)、保稅區(qū)物流綜合服務(wù)模式這兩種模式是較為有效的。文作者從社會(huì)、政策角度上，提倡政府和相關(guān)的跨境物流企業(yè)出臺(tái)相關(guān)的現(xiàn)實(shí)物流問題應(yīng)對(duì)策略，雙管齊下以挑戰(zhàn)目前跨境物流的短板和突破物流瓶頸，提出可以從建立各國家之間的商業(yè)戰(zhàn)略聯(lián)盟以降低物流成本，加強(qiáng)對(duì)跨境物流信息系統(tǒng)的構(gòu)建以及加大對(duì)物流行業(yè)人才的培養(yǎng)等。文對(duì)于跨境物流信息平臺(tái)的研究主要在平臺(tái)的搭建、路線的優(yōu)化、政策的頒布等方面，對(duì)于跨境物流平臺(tái)中包裹優(yōu)化，跨語種，跨技術(shù)技術(shù)標(biāo)準(zhǔn)等方面處于空白。

國內(nèi)學(xué)者主要從宏觀經(jīng)濟(jì)管理方面對(duì)降低物流成本提出對(duì)應(yīng)之策。文通過定量分析、模擬物流系統(tǒng)等方式得出減低物流成本的決策方案。文從整合企業(yè)內(nèi)部物流資源和選用優(yōu)秀的第三方物流供應(yīng)商這兩方面進(jìn)行解析；文分析B2C 電子商務(wù)企業(yè)可從合理選擇物流模式、加強(qiáng)電子商務(wù)供應(yīng)鏈整合、締結(jié)電商企業(yè)與物流地產(chǎn)聯(lián)盟等幾方面入手降低物流成本。文研究了一個(gè)考慮成組分揀的雙層分揀設(shè)備目的地指派問題，設(shè)計(jì)了一種高效的變鄰域禁忌搜索算法，采用“成組分揀”方法與考慮目的地指派問題可有效提高分揀設(shè)備的分揀效率。文提出通過政府出臺(tái)專項(xiàng)政策減少物流成本中的制度成本、構(gòu)建第四方聯(lián)盟、為顧客制定專屬的跨境物流服務(wù)從而提高其競爭力等三個(gè)方式降低相應(yīng)的物流成本。文為我們表明了運(yùn)輸成本是物流成本中比重高的項(xiàng)目，但是我們不能忽略存儲(chǔ)和存貨等成本，減低物流成本既要改革物流成本管理制度也要提高為客戶服務(wù)的質(zhì)量，同時(shí)現(xiàn)代企業(yè)也應(yīng)創(chuàng)新改革，提高競爭力。文運(yùn)用Flexsim 三維系統(tǒng)仿真軟件, 展現(xiàn)物流分揀過程、利弊以及瓶頸問題，根據(jù)數(shù)據(jù)分析相應(yīng)的問題，在設(shè)備資源、人力資源、資金資源的利用率上進(jìn)行調(diào)整，進(jìn)而提高整體效益。我國對(duì)于物品分揀的研究，是簡單的對(duì)于貨物進(jìn)行取出、分類、集中打包等操作，有人工分揀系統(tǒng)、半自動(dòng)化分揀系統(tǒng)、自動(dòng)分揀系統(tǒng)等，對(duì)于分揀系統(tǒng)方面的優(yōu)化，其主要目的在于減少物品搬運(yùn)次數(shù)、搬運(yùn)距離，從而提高勞動(dòng)效率，降低作業(yè)成本。設(shè)計(jì)智能識(shí)別物品信息系統(tǒng)，依靠機(jī)械裝送帶對(duì)運(yùn)往相同地點(diǎn)的物品進(jìn)行分類，降低作業(yè)人員的勞動(dòng)強(qiáng)度，降低人工操作時(shí)挑選的錯(cuò)誤率，節(jié)省作業(yè)空間等。尚未未從單獨(dú)物流成本方面考慮，如何更好的將物品合理分揀打包的問題。

國內(nèi)外的學(xué)者都比較關(guān)注目前跨境物流的發(fā)展現(xiàn)狀并針對(duì)相關(guān)問題進(jìn)行分析并提出見解，鼓勵(lì)相關(guān)的跨境物流企業(yè)加大創(chuàng)新力度，融合時(shí)代背景需求，對(duì)跨境物流企業(yè)模式進(jìn)行改革。國內(nèi)外對(duì)于跨境物流研究趨向不同點(diǎn)是在：國外學(xué)者更加注重跨境物流領(lǐng)域相關(guān)技術(shù)的研發(fā)。智能算法、數(shù)據(jù)挖掘技術(shù)、人工智能等流行的工具被熟練的運(yùn)用到跨境物流平臺(tái)的搭建中。國外主要從理工科的領(lǐng)域方面研究問題。國內(nèi)學(xué)者更加熱衷于對(duì)跨境物流相關(guān)理論政策方面提出建議，對(duì)物流模式情況分析，特別是從“一帶一路”倡議提出以來，針對(duì)于“一帶一路”的跨境物流研究文獻(xiàn)也越來越多。但是國外學(xué)者對(duì)于這方面的研究較少。

包裝標(biāo)準(zhǔn)化能夠提高物品的保管效率，降低運(yùn)輸費(fèi)用，減少運(yùn)輸過程中的破損率，減少貨物的損耗費(fèi)用。加快完成物流標(biāo)準(zhǔn)化和包裝標(biāo)準(zhǔn)化，是物流行業(yè)的發(fā)展趨勢。國內(nèi)外降低跨境物流的方法主要為優(yōu)化運(yùn)輸途徑、企業(yè)結(jié)構(gòu)調(diào)整、業(yè)務(wù)流程優(yōu)化等，對(duì)于物流包裹主要是對(duì)快遞包裹外觀設(shè)計(jì)、包裹材質(zhì)的研究。而本文通過利用貪婪算法原理得到物品分揀打包最優(yōu)方案，降低物流費(fèi)用，以提高整體效益，推動(dòng)物流行業(yè)的發(fā)展。

2 跨境物流貪婪算法

貪婪算法也叫貪心算法，它是通過優(yōu)化局部解得到局部最優(yōu)解，進(jìn)而得到近似的全局最優(yōu)解。對(duì)所有局部解做貪婪選擇，將大問題分割為若干個(gè)小問題求最優(yōu)解，當(dāng)經(jīng)過多次貪婪選擇后最終求得整體的最優(yōu)解。貪婪算法具有自頂向下的處理問題方式，采取分而治之的思想通過局部最優(yōu)解，是一種啟發(fā)式算法。貪婪算法容易理解也易于實(shí)現(xiàn)，同時(shí)也極大的提高了運(yùn)行效率并節(jié)省了時(shí)間，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測度做出最優(yōu)選擇。在實(shí)際問題中，運(yùn)用貪婪算法解決問題時(shí)，主要有三個(gè)中心點(diǎn)，第一點(diǎn)是根據(jù)不同的問題實(shí)際情況，設(shè)置初始條件，該初始條件應(yīng)該具有合理性，是求得局部最優(yōu)解的基礎(chǔ)。第二點(diǎn)是通過設(shè)定一個(gè)優(yōu)化函數(shù)，優(yōu)化每一次的局部解，通過貪婪算法迭代，得到局部最優(yōu)解。第三點(diǎn)是判斷該算法的終止條件。

2.1 分類打包問題的本質(zhì)與特性

在物品分類打包過程中涉及到了各類因素，包括：物品種類、物品重量、物品數(shù)量、物品體積、包裹數(shù)量、運(yùn)輸路線等。各類因素對(duì)于物流費(fèi)用的影響因子不同，綜合多方面因素，本文對(duì)于分類打包問題研究的本質(zhì)是要合理、合規(guī)、安全將物品送達(dá)，優(yōu)化打包方案，同時(shí)得到物流費(fèi)用相對(duì)較低。打包方案的最基本特征是多樣性。不同的打包方式，可能得到的是相同物流費(fèi)用。因此無法明確的規(guī)定那個(gè)方案最優(yōu)，通過貪婪算法的計(jì)算后，得到的是一個(gè)相對(duì)最優(yōu)解。

通過對(duì)物品分來挑揀打包問題的研究，分類打包問題包括以下五個(gè)特性：

（1）多樣性：分類打包的方案有多重多樣，且每個(gè)方案在不同的條件下都可能得到相對(duì)最低的物流費(fèi)用。不同的打包方式可能出現(xiàn)相同的物流費(fèi)用。

（2）約束性：在物品打包過程中，受到了包裹體積大小的約束，運(yùn)輸方式的約束、特殊的物品種類的約束、物品性質(zhì)的約束等等。

（3）復(fù)雜性：物品打包方式不唯一，無法套用固定的打包方案，物品的數(shù)量、性質(zhì)、大小等多變，導(dǎo)致打包方案千變?nèi)f化。

（4）目標(biāo)性：物品打包組合最優(yōu)的原則是在同一條件下以物流費(fèi)用達(dá)到相對(duì)最低為目標(biāo)，為寄件人提供一個(gè)費(fèi)用相對(duì)較低的方案。

（5）靈活性：分類打包能夠適用于許多不同特性的物品分類組合。

2.2 分類打包準(zhǔn)則

物品組合優(yōu)化打包問題是一個(gè)基于物品屬性、運(yùn)輸路線和運(yùn)輸時(shí)間等多維屬性的組合優(yōu)化問題。在符合寄件人所提出的寄件需求的情況下，綜合考慮各類因素限制，通過設(shè)計(jì)合理的打包方案，降低物流公司整體的物流費(fèi)用。在物品打包過程中需遵守的基本原則如下：

（1）保證打包過程中貨物的安全性：易碎物品打包所需要的軟性緩沖包裝材料，防水包裝等包裝材料。

（2）進(jìn)行環(huán)保打包、合理打包：使用環(huán)保紙箱、環(huán)保編織袋等節(jié)能環(huán)保材料。

（3）特殊物品僅能被歸類特殊物流通道：比如食品類物品必須走食品專用航線，帶電物品或敏感類物品需要從特殊的運(yùn)輸航線進(jìn)行運(yùn)輸?shù)取?/p>

2.3 物品包裹優(yōu)化模型的可行性研究

綜合考慮跨境物流運(yùn)輸中存在商品種類局限性大、物流時(shí)效慢和運(yùn)輸成本高等問題，本文重點(diǎn)研究如何對(duì)物品進(jìn)行優(yōu)化打包，在滿足物流運(yùn)輸要求下，能夠有效的解決跨境物流中存在的運(yùn)輸成本高的問題。同時(shí)，由于物流費(fèi)用的降低，符合大眾的心理預(yù)期，能夠較好的被人們所接受。因此系統(tǒng)在未來跨境物流發(fā)展中有較大的市場前景。

2.4 基于貪婪算法的物品包裹優(yōu)化模型

2.4.1 物品類型和包裹類型

物品包裹優(yōu)化首先需要明確物品的類型、物品重量、包裹大小以及運(yùn)輸?shù)暮骄€都關(guān)乎打包方案的設(shè)計(jì)。不同物品類型的組合也會(huì)引起打包方案的變化從而產(chǎn)生不同的物流費(fèi)用。通過移動(dòng)物品組合，運(yùn)用貪婪算法對(duì)包裹進(jìn)行不斷的組合優(yōu)化，進(jìn)而得到一個(gè)相對(duì)滿意的包裹組合。

如表1 所示，根據(jù)運(yùn)輸航線對(duì)物品的要求，物品類型可分為普通型、帶電型、敏感型、液體型和食品型五種類型，分別標(biāo)記為I,I,I,I,I。五種物品類型的優(yōu)先等級(jí)I<

表1 ：物品類型和優(yōu)先等級(jí)

用P,P,…,P表示某個(gè)顧客所郵寄的最小拆分物品，共計(jì)n 個(gè)，其重量分別用M,M,…,M表示。用B、B、B、B和B分別表示五類包裹，其中包裹B可以存放打包I類型物品，B可以存放打包I和I兩種類型物品，B可以存放打包I、I和I三種類型物品，B可以存放打包I、I、I和I四種類型物品，B可以存放打包I、I、I、I和I五種類型物品。

以上是對(duì)郵寄物品的類型、物品重量、物品類型的優(yōu)先級(jí)別以及包裹類型進(jìn)行了描述。接下來討論討論物品組合優(yōu)化的貪婪算法的步驟及系統(tǒng)設(shè)計(jì)。

2.4.2 包裹優(yōu)化貪婪算法的步驟和流程

2.4.2.1 包裹優(yōu)化貪婪算法的基本步驟

步驟1：初始化包裹。包裹B僅存放I物品，包裹B僅存放I物品，包裹B僅存放I物品，包裹B僅存放I物品，包裹B僅存放I物品，當(dāng)沒有該類型的物品，則包裹為空；

步驟2：構(gòu)造物品組合。在初始化包裹后，根據(jù)算法的數(shù)據(jù)結(jié)構(gòu)定義，將所有的物品分組。例如：將P，P，P這三個(gè)物品分組，物品組合有：單個(gè)物品組合P、P和P，兩物品組合PP、PP和PP，三物品組合PPP；

步驟3：迭代。計(jì)算所有物品組合移動(dòng)引起的費(fèi)用變化（移動(dòng)前減移動(dòng)后），并將費(fèi)用變化最大且大于0 的物品進(jìn)行移動(dòng)，改變包裹間物品的重新組合；

終止條件：若所有物品組合移動(dòng)引起運(yùn)費(fèi)變化都小于等于0，則算法終止。并返回一個(gè)相對(duì)最優(yōu)的打包方案。

2.4.2.2 包裹優(yōu)化算法的流程圖包裹優(yōu)化算法的流程圖如圖1 所示。先初始化包裹，判斷是否滿足終止條件，若是則輸出最優(yōu)打包方案。否則將按照物品組合優(yōu)先級(jí)向后尋求合并包裹，計(jì)算物品合并前后所產(chǎn)生的運(yùn)費(fèi)差，若運(yùn)費(fèi)差小于或等于零，即包裹合并后方案的運(yùn)費(fèi)大于合并前的或者合并前后運(yùn)費(fèi)沒有變，這種情況將繼續(xù)重新合并求運(yùn)費(fèi)差，直到運(yùn)費(fèi)差大于0，即合并后的運(yùn)費(fèi)比合并前低，將更新包裹，再次判斷是否滿足終止條件，若是則返回最優(yōu)解，否則重新進(jìn)行包裹合并、貪婪迭代操作。

圖1 ：分類打包算法流程圖

3 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

3.1 系統(tǒng)設(shè)計(jì)

針對(duì)用戶的需求，在用戶模塊設(shè)計(jì)包含寄送物品類型選擇和物品重量輸入等信息輸入模塊，待所有物品相關(guān)數(shù)據(jù)輸入完成，通過后臺(tái)運(yùn)算可以得出最優(yōu)費(fèi)用的包裹打包組合方案，反饋給用戶參考，用戶模塊使用流程圖如圖2 所示。系統(tǒng)編碼設(shè)計(jì)上利用MATLAB 可以簡潔處理非常復(fù)雜的數(shù)學(xué)計(jì)算問題和Java 具有多變的應(yīng)用場景（如Web 開發(fā)），將兩者充分結(jié)合起來，采用MATLAB 編寫核心算法并將其打包成jar 包供Java 程序調(diào)用。

圖2 ：用戶模塊使用流程圖

3.2 系統(tǒng)實(shí)現(xiàn)

系統(tǒng)前端界面采用HTML 頁面實(shí)現(xiàn)，結(jié)合Element 框架進(jìn)行開發(fā)，開發(fā)過程中代碼簡潔，界面實(shí)現(xiàn)效果簡潔且易操作，能兼容市面上絕大部分的瀏覽器進(jìn)行訪問。在運(yùn)費(fèi)計(jì)算模塊，用戶將物品信息輸入界面，可定義添加刪除物品數(shù)量，可通過點(diǎn)擊或輸入即可實(shí)現(xiàn)數(shù)據(jù)的輸入。最后通過點(diǎn)擊立即提交按鈕，系統(tǒng)將運(yùn)算獲取最優(yōu)打打包方案，最終將最優(yōu)打打包方案顯示在用戶界面，如圖3 所示。

圖3 ：最優(yōu)打打包方案顯示界面

4 結(jié)語

本文利用貪婪算法在跨境物流包裹優(yōu)化中應(yīng)用解決了包裹組合優(yōu)化NP 難題，得到了一組較優(yōu)化的滿意解。在保障運(yùn)輸物品完整完好的同時(shí)，減少物流成本，同時(shí)方便從事跨境物品挑件打包工作人員對(duì)于物品的分類打包，在未來的發(fā)展中具有廣泛的應(yīng)用前景。通過對(duì)信息技術(shù)的靈活運(yùn)用，加快促進(jìn)跨境物流服務(wù)的個(gè)性化發(fā)展！