三階段越庫車輛排序及算法研究

李 欣，孫 軍，陳 欣 （大連工業大學，遼寧 大連 116034）

0 引言

根據我國國家標準《物流術語》中給出的定義，可以知道越庫模式是指物流環節中的產品和商品，不經過中間站點和倉庫，直接從一個交通運輸工具換載到另一個交通運輸工具的物流承接方式。隨著越庫管理模式在實踐中的廣泛運用，越庫中的各類問題也引起了學者的研究興趣。例如毛道曉、徐克林等[1]以總成本最小為目標，從長期戰略角度利用混合整數規劃模型研究了越庫模式的中心選址問題.。強瑞、繆朝煒、吳為民[2]則從中期策略角度出發探討帶有時間窗口的倉門分配問題，將貪婪算法、遺傳算法以及禁忌算法的思想整合、衍生出了混合啟發式算法來解決問題，并將其結果與這3種算法各自的結果進行對比，驗證了該混合啟發式算法在問題解決中的優勢。同樣研究倉門分配問題的還有李敬峰[3]。除了倉門、選址等問題之外，在總施工時間最短的目標下，對配送中心車輛入庫卸貨順序的優化問題也是學者關注的一個部分。高晶、高舉紅[4]把越庫作業流程分成兩個階段，利用約翰遜算法解決了配送中心內部越庫車輛排序問題，為服務連鎖零售企業的發展提供指導。馬東彥、陳峰[5]考慮現實情況，對越庫作業的流程、類型和實施所需的條件進行分析研究，在此基礎上研究了對配送中心內部的作業順序優化。在多位學者的研究基礎上，本文研究了越庫車輛排序問題發展現狀并解析原因，再運用約翰遜算法解決問題，并提出相關建議。

1 越庫車輛排序問題現狀分析

從越庫的定義看出，整個越庫流程起點是各大供貨商，車輛從供應商處取得商品到達越庫中心，經過越庫中心，再由出庫車輛運送至各大門店?？此坪芎唵蔚牧鞒蹋趯嶋H工作過程中卻存在著大量的問題，總要有以下幾點。（1）排序不當導致配送中心倉儲壓力增大。隨著電子商務的高速發展，例如雙十一、雙十二等購物節日的出現，使得物流行業會出現階段性訂單量暴增。盡管物流公司提前備車，但是激增的訂單量還是難以消化，除了運輸路途問題，當車輛來到各個配送中心，按照什么樣的順序出入庫可以實現效率最高也是一個艱巨的問題。不當的排序，可能導致各個環節之間配合不當，商品滯留，最后堆積的商品必然會為配送中心帶來巨大的倉儲壓力，更有可能導致運送時間和運輸成本的增加。（2）相關物流企業關注度不夠。對于越庫模式的研究國外在80年代就已經有所提及，并且國外很多企業例如沃爾瑪、UPS、豐田等都已將越庫模式融入自己的企業生產中，但是這并沒有引起國內企業的重視，更不要說越庫車輛排序的問題了。主要原因在于中國大多數物流企業尚處于發展階段，企業沒有多余的精力投放到物流作業的優化中，再加上越庫模式對企業自身的要求也較高，自然導致對車輛排程問題的關注度不夠，想要解決這一類問題，還有很長一段路需要探索。（3）缺乏切實可行地解決配送中心越庫車輛排序問題的方法。對車輛排序問題的研究，在研究算法上，學者主要集中于常規的算法如遺傳算法、禁忌搜索算法等，并針對這些算法的缺陷進行改進以更適應實際問題。例如蔣鵬、佘艷[6]以遺傳算法為基礎考慮了越庫車輛排程問題，并利用完善之后的配送模型對接駁車輛配送排程方案進行了優化設計。黃尚[7]研究的則是在如今電子商務的整體大環境下，物流發展情況的新特點，分析研究了遺傳算法在物流配送中，尤其是在如何確定越庫配送車輛出入庫順序中的使用。經過這些學者的研究，確實證明了這些高級算法在問題解決中的可行性，但同時這些算法自身對問題的約束條件較多，加上算法自身存在的缺陷都為其日常企業實踐帶來了一定的障礙。為了解決上述問題，本文提出運用簡單易行的約翰遜算法幫助企業確定車輛進出的最佳順序。

2 越庫車輛排序算法探究

2.1 算法簡介。約翰遜算法是一種基礎的作業排序方法，雖然在越庫車輛排序問題中的應用較少，但在求解以加工時間最短為目標的工件順序問題上被廣泛運用，已經發展成為一種相當成熟的算法，并且應用簡單，容易得到最優解，對于解決車輛排序問題更具有實踐意義。它強調只有當n個工件要經過二、三個機器（必須是有限個機器）進行加工，并且所有工件在有限個機器上加工的順序都是相同時才可以被使用到越庫車輛排序問題中。當工件要經過兩個機器即經過兩道工序時，使用約翰遜算法解決問題的一般順序為：一是找出工時表中最小的數字。如果該數字在第一道工序，則將對應的工件放在最開始加工；如果該數字在第二道工序，則將對應的工件放在最末尾加工。二是將第一步已經確定了順序的工件劃去。三是重復上述兩道工序，直至確定工時表中所有工件的順序。

可以看出約翰遜算法的應用十分簡單，但是隨著設備數量的增加，優化難度也隨之增加。為了求解三階段問題，必須對算法進行改進。當有n項工件且要經過三道工序時，可以使用下述方法求得最優解：一是將工時表中第一道工序的施工時間和第二道工序的施工時間相加；二是將工時表中第三道工序的施工時間和第二道工序的施工時間相加；三是將上兩步得到的時間當成兩個獨立的工序的施工時間，然后重復機器數目為2時的處理方法，得出正確的工件加工順序。根據趙輝、張紅云[8]的論證，要想使用上述方法，必須要滿足下面兩種情況中的其中一個：即第一道或是第三道工序中的最小施工期≥第二道工序中的最大施工期。

為了更好地將約翰遜算法運用到越庫模式的車輛排序問題中，需要將整個越庫作業分成三個階段，對應約翰遜算法的三道工序。商品從入庫車輛卸載至暫存區，等候進入分揀帶的過程看成第一階段，記做M1；第二階段則是商品從暫存區出來經過分揀帶，按照訂單分揀到各個門店對應的暫存區等待重新裝箱，記做M2；商品從暫存區再打包到達站臺上車的過程看做是第三階段，記做M3。如圖1所示。

圖1

2.2 相關假設。為了方便理解約翰遜算法的實際運用，首先制定相關假設條件，一是假設配送中心只有一個門口，車輛入庫、出庫都要從這里經過，并且每一次只能經過1輛車倆。二是假設有3家供應商向4家門店供貨，每輛車輛對應1個供應商，并且每家供應商供應的商品是獨一無二的，即每輛車輛只負責1種商品。三是假設配送中心一共有2個站臺，每個站臺都對應著特定的車輛，每輛車輛都對應著特定的一條路線，且每條線可以配送不止1家門店。四是配送中心內部只有一條分揀帶，分揀帶的傳輸速度是一定的，物品在分揀帶上的時間只與物品的體積和分揀口的距離有關并且暫存區的數量是不限的，每個暫存區必須等所需商品分揀結束之后才重新包裝、裝車。五是當各個階段開始正式工作之后就不允許中斷。

2.3 相關數據的確立。假設有3家供應商向4家門店供貨的客戶訂單表如表1所示，每一格的數據代表了對應門店所需商品數量。假設Si表示各個供應商，本假設中有3個供應商可分別表示為S1、S2、S3，同時由于各個供應商只供應唯一一種商品，所以Si還可用于表示各個供應商供應的商品S1、S2、S3，其中S1的體積最小，S3的體積最大；Zi：Zi表示各個站臺，如2個站臺分別表示為Z1、Z2；Di：Di代表各個門店即需求方，如 4個門店可分別表示為 D1、D2、D3、D4。

由于資金有限，越庫中心只有有限個站臺，并且每個站臺對應著特定的線路，每個線路可以配送多于1家門店，因此站臺與門店之間的對應關系，如表2所示。Z1站臺對應著D1、D2兩個門店，即將D1、D2的貨物集中在Z1站臺，當貨物搜集完畢之后，由1輛車進行配送。而Z2站臺對應的是D3、D4，就是將D3、D4的貨物集中在Z2，裝車后由1輛車完成運送。這樣可以最大限度地提高車輛的利用率，減少循環取貨帶來的時間和成本上的浪費。

表1 客戶信息表 單位：個

表2 站臺與門店之間的對應關系

2.4 計算步驟及結果。商品在各階段所需時間受不同因素影響，如：第一階段：M1階段要完成商品拆包卸貨到暫存區的工作，因此所需要的時間主要是受商品自身的體積和門口與卸貨區之間距離的影響，而不會受到車輛入庫順序的影響。第二階段：M2則是商品從暫存區出來經過分揀帶，按照訂單進行分揀到達每個門店所對應的各個暫存區，由于配送中心內部只有一條分揀帶，分揀帶的傳輸速度是一定的，因此這一階段所需的時間會受到物品的體積、分揀口的距離、暫存區與分揀帶之間距離的影響。第三階段：M3是商品依據訂單重新包裝好再裝車的過程，由于只有當所有的貨物都收集完畢之后才能打包，并且打包之后立即就能進入站臺上車，因此這個階段所需要的時間主要受到各個門店所需商品的體積和商品入庫順序以及各個暫存區與站臺之間距離的影響，并且商品的體積與各階段停留時間成正比。因此根據表1客戶信息表和表2站臺與門店之間的對應關系的數據，再結合工人日常分揀經驗以及機器的運作效率，可以大致估算出各個貨物在每個程序中所需的時間，如表3.所示。

商品在各階段所花費的時間滿足了上述兩個要求，所以可以使用約翰遜算法。一是將工時表中第一道工序的施工時間和第二道工序的施工時間相加，得到M1+M2的數據；二是將工時表中第三道工序的施工時間和第二道工序的施工時間相加，得到M3+M2的數據；三是將上兩步得到的時間當成兩個獨立的工序的施工時間，然后找出后兩行中最小的數字是6，并且在第一道工序中，因此將S1放在最前面，并將S1從表中暫時剔除，發現剩下的數中最小的是10，在第二道工序中，因此將對應的S2放在最后面，最終可以得到最佳的入庫順序是S1-S3-S2。

3 解決越庫車輛排序問題的相應對策

根據約翰遜法則，確定了在上述條件下最佳的入庫順序是S1-S3-S2。這樣的安排不僅能大大提高各個工序之間的契合度，提高了整體效率，同時節約了成本，為企業競爭創造了條件。為了解決文中提出的相關問題，針對性的提出了下面幾種對策。（1）對越庫車輛合理排序可以降低倉儲壓力。如果利用GPS技術實時監控車輛的位置，預估出各個車輛大概的到達時間、有哪些車輛會到達，再依據約翰遜算法合理確定進入順序，這樣可以大大減少配送中心可能產生的臨時庫存，降低倉儲壓力、提高車輛利用率，對降低企業配送成本有益。（2）物流企業應提高對越庫車輛排序問題的關注度。傳統的配送模式被代替是不可避免的，越庫模式作為如今配送模式發展的大方向，已經被越來越多的企業證明了它的有效性，但是由于越庫模式在國內的發展較晚，加上越庫模式對企業自身的要求過高，所以一直發展不快。物流企業應該提高對越庫模式的關注，約翰遜算法作為一個成熟簡單的算法，能夠有效地解決越庫車輛排序的問題，并且符合現階段大多數企業發展狀況，應該大力倡導企業實踐，從實踐中尋找問題，再做出相應的改善。只有大量企業進行實踐，才能發現并解決問題，才能促進物流行業的快速發展。（3）物流企業應對越庫車輛排序方法進行創新。越庫模式的目標是實現“零庫存”，這種模式的實行將為企業節約大量成本，提高作業效率，作為越庫模式的第一道關口，車輛排序問題急需解決。但是現階段集中研究的高級算法的約束條件太多，在實際應用中會受限，再者由于算法本身的局限性，經常只能得到局部最優解，這些都為解決問題帶來了阻礙。對于解決車輛排序問題，運用約翰遜算法的使用要求較低，使用方法也較簡單，對于一些一線工作的員工很容易上手，再者其在流水作業領域的廣泛運用已經使其發展得很成熟，不存在早熟或是局部最優的問題，對于現階段中國企業是適合的。同時，學者們還應當時刻關注企業實踐中存在的問題、物流配送未來的發展方向，針對這些問題，積極探索更多操作性強的方法，促進排序方法的創新。

4 結論

本文探討了越庫模式和越庫車輛排序問題的發展現狀，發現并分析了其中存在的一些問題及其產生的原因，對于每個問題都針對性的給出了建議。為了實現總的作業時間最短，提出了使用約翰遜算法解決越庫車輛排序的問題，同時還能得到對應的入庫順序。相較于高級算法，約翰遜算法更具有實踐性，操作性更強，更符合大多數中國企業的現狀，對企業實踐操作具有一定的指導意義。

[1] 毛道曉，徐克林，張志英,等.越庫中心選址模型與啟發式算法[J].中南大學學報，2013(44):564-570.

[2] 強瑞，繆朝煒，吳為民.供應網絡中越庫轉運中心倉門分配問題研究[J].管理工程學報，2011(25):209-215.

[3] 李敬峰.面向貨物裝卸需求的越庫倉門分配和車輛調度問題研究[D].廣州：廣東工業大學（碩士學位論文），2016.

[4] 高晶，高舉紅.服務連鎖零售企業的配送中心內越庫車輛調度研究[J].技術與方法，2012(2):113-115.

[5] 馬東彥，陳峰.以總加權完工時間為目標的兩臺機越庫排序的動態規劃算法[J].上海交通大學學報，2007(5):852-856.

[6] 蔣鵬，佘艷.基于遺傳算法的接駁轉運車輛排程的分析研究[J].信息與電腦，2011(6):168-170.

[7] 黃尚.遺傳算法在物流配送中的研究與應用[D].廣州：廣東工業大學（碩士學位論文），2013.

[8] 趙輝，張紅云.約翰遜—貝爾曼法則在流水作業中的應用[J].河南城建高等?？茖W校學報，2001(10):62-63.

[9] 陳杰，陳峰.非對稱不確定性越庫調度算法[J].上海交通大學學報，2010,44(9):1302-1306.

[10] 王剛.基于排隊和排序理論的兩階段越庫作業調度算法研究[D].北京：北京交通大學（碩士學位論文），2008.

[11] 宋凱雷.越庫物流的兩階段混合調度模型及優化算法[D].上海：上海交通大學（碩士學位論文），2008.