三階段越庫(kù)車(chē)輛排序及算法研究

李 欣，孫 軍，陳 欣 （大連工業(yè)大學(xué)，遼寧 大連 116034）

0 引言

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

1 越庫(kù)車(chē)輛排序問(wèn)題現(xiàn)狀分析

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

2 越庫(kù)車(chē)輛排序算法探究

2.1 算法簡(jiǎn)介。約翰遜算法是一種基礎(chǔ)的作業(yè)排序方法，雖然在越庫(kù)車(chē)輛排序問(wèn)題中的應(yīng)用較少，但在求解以加工時(shí)間最短為目標(biāo)的工件順序問(wèn)題上被廣泛運(yùn)用，已經(jīng)發(fā)展成為一種相當(dāng)成熟的算法，并且應(yīng)用簡(jiǎn)單，容易得到最優(yōu)解，對(duì)于解決車(chē)輛排序問(wèn)題更具有實(shí)踐意義。它強(qiáng)調(diào)只有當(dāng)n個(gè)工件要經(jīng)過(guò)二、三個(gè)機(jī)器（必須是有限個(gè)機(jī)器）進(jìn)行加工，并且所有工件在有限個(gè)機(jī)器上加工的順序都是相同時(shí)才可以被使用到越庫(kù)車(chē)輛排序問(wèn)題中。當(dāng)工件要經(jīng)過(guò)兩個(gè)機(jī)器即經(jīng)過(guò)兩道工序時(shí)，使用約翰遜算法解決問(wèn)題的一般順序?yàn)椋阂皇钦页龉r(shí)表中最小的數(shù)字。如果該數(shù)字在第一道工序，則將對(duì)應(yīng)的工件放在最開(kāi)始加工；如果該數(shù)字在第二道工序，則將對(duì)應(yīng)的工件放在最末尾加工。二是將第一步已經(jīng)確定了順序的工件劃去。三是重復(fù)上述兩道工序，直至確定工時(shí)表中所有工件的順序。

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

為了更好地將約翰遜算法運(yùn)用到越庫(kù)模式的車(chē)輛排序問(wèn)題中，需要將整個(gè)越庫(kù)作業(yè)分成三個(gè)階段，對(duì)應(yīng)約翰遜算法的三道工序。商品從入庫(kù)車(chē)輛卸載至?xí)捍鎱^(qū)，等候進(jìn)入分揀帶的過(guò)程看成第一階段，記做M1；第二階段則是商品從暫存區(qū)出來(lái)經(jīng)過(guò)分揀帶，按照訂單分揀到各個(gè)門(mén)店對(duì)應(yīng)的暫存區(qū)等待重新裝箱，記做M2；商品從暫存區(qū)再打包到達(dá)站臺(tái)上車(chē)的過(guò)程看做是第三階段，記做M3。如圖1所示。

圖1

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

2.3 相關(guān)數(shù)據(jù)的確立。假設(shè)有3家供應(yīng)商向4家門(mén)店供貨的客戶(hù)訂單表如表1所示，每一格的數(shù)據(jù)代表了對(duì)應(yīng)門(mén)店所需商品數(shù)量。假設(shè)Si表示各個(gè)供應(yīng)商，本假設(shè)中有3個(gè)供應(yīng)商可分別表示為S1、S2、S3，同時(shí)由于各個(gè)供應(yīng)商只供應(yīng)唯一一種商品，所以Si還可用于表示各個(gè)供應(yīng)商供應(yīng)的商品S1、S2、S3，其中S1的體積最小，S3的體積最大；Zi：Zi表示各個(gè)站臺(tái)，如2個(gè)站臺(tái)分別表示為Z1、Z2；Di：Di代表各個(gè)門(mén)店即需求方，如 4個(gè)門(mén)店可分別表示為 D1、D2、D3、D4。

由于資金有限，越庫(kù)中心只有有限個(gè)站臺(tái)，并且每個(gè)站臺(tái)對(duì)應(yīng)著特定的線(xiàn)路，每個(gè)線(xiàn)路可以配送多于1家門(mén)店，因此站臺(tái)與門(mén)店之間的對(duì)應(yīng)關(guān)系，如表2所示。Z1站臺(tái)對(duì)應(yīng)著D1、D2兩個(gè)門(mén)店，即將D1、D2的貨物集中在Z1站臺(tái)，當(dāng)貨物搜集完畢之后，由1輛車(chē)進(jìn)行配送。而Z2站臺(tái)對(duì)應(yīng)的是D3、D4，就是將D3、D4的貨物集中在Z2，裝車(chē)后由1輛車(chē)完成運(yùn)送。這樣可以最大限度地提高車(chē)輛的利用率，減少循環(huán)取貨帶來(lái)的時(shí)間和成本上的浪費(fèi)。

表1 客戶(hù)信息表 單位：個(gè)

表2 站臺(tái)與門(mén)店之間的對(duì)應(yīng)關(guān)系

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

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

3 解決越庫(kù)車(chē)輛排序問(wèn)題的相應(yīng)對(duì)策

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

4 結(jié)論

本文探討了越庫(kù)模式和越庫(kù)車(chē)輛排序問(wèn)題的發(fā)展現(xiàn)狀，發(fā)現(xiàn)并分析了其中存在的一些問(wèn)題及其產(chǎn)生的原因，對(duì)于每個(gè)問(wèn)題都針對(duì)性的給出了建議。為了實(shí)現(xiàn)總的作業(yè)時(shí)間最短，提出了使用約翰遜算法解決越庫(kù)車(chē)輛排序的問(wèn)題，同時(shí)還能得到對(duì)應(yīng)的入庫(kù)順序。相較于高級(jí)算法，約翰遜算法更具有實(shí)踐性，操作性更強(qiáng)，更符合大多數(shù)中國(guó)企業(yè)的現(xiàn)狀，對(duì)企業(yè)實(shí)踐操作具有一定的指導(dǎo)意義。

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

[2] 強(qiáng)瑞，繆朝煒，吳為民.供應(yīng)網(wǎng)絡(luò)中越庫(kù)轉(zhuǎn)運(yùn)中心倉(cāng)門(mén)分配問(wèn)題研究[J].管理工程學(xué)報(bào)，2011(25):209-215.

[3] 李敬峰.面向貨物裝卸需求的越庫(kù)倉(cāng)門(mén)分配和車(chē)輛調(diào)度問(wèn)題研究[D].廣州：廣東工業(yè)大學(xué)（碩士學(xué)位論文），2016.

[4] 高晶，高舉紅.服務(wù)連鎖零售企業(yè)的配送中心內(nèi)越庫(kù)車(chē)輛調(diào)度研究[J].技術(shù)與方法，2012(2):113-115.

[5] 馬東彥，陳峰.以總加權(quán)完工時(shí)間為目標(biāo)的兩臺(tái)機(jī)越庫(kù)排序的動(dòng)態(tài)規(guī)劃算法[J].上海交通大學(xué)學(xué)報(bào)，2007(5):852-856.

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

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

[8] 趙輝，張紅云.約翰遜—貝爾曼法則在流水作業(yè)中的應(yīng)用[J].河南城建高等專(zhuān)科學(xué)校學(xué)報(bào)，2001(10):62-63.

[9] 陳杰，陳峰.非對(duì)稱(chēng)不確定性越庫(kù)調(diào)度算法[J].上海交通大學(xué)學(xué)報(bào)，2010,44(9):1302-1306.

[10] 王剛.基于排隊(duì)和排序理論的兩階段越庫(kù)作業(yè)調(diào)度算法研究[D].北京：北京交通大學(xué)（碩士學(xué)位論文），2008.

[11] 宋凱雷.越庫(kù)物流的兩階段混合調(diào)度模型及優(yōu)化算法[D].上海：上海交通大學(xué)（碩士學(xué)位論文），2008.