裝箱算法在卷煙配載驗(yàn)證系統(tǒng)中的應(yīng)用

王 瑋，張潔華，張菡子，李景舒，季靖寒

（上海煙草集團(tuán)有限責(zé)任公司上海煙草儲(chǔ)運(yùn)公司，上海 200439）

1 研究背景和意義

隨著上海煙草集團(tuán)產(chǎn)銷規(guī)模的擴(kuò)大，客戶對(duì)卷煙的需求朝著多樣化、小批量、多頻次和個(gè)性化方向發(fā)展，不僅花式煙品種規(guī)格增加，拼車訂單也逐年遞增，導(dǎo)致卷煙配載業(yè)務(wù)的復(fù)雜程度與日俱增。在卷煙單車配載環(huán)節(jié)，長(zhǎng)期以來都是依賴人工經(jīng)驗(yàn)進(jìn)行的，對(duì)于是否已經(jīng)達(dá)到運(yùn)輸車輛使用率的最大化、配載效益的最大化無從評(píng)估，同時(shí)這種配載方式強(qiáng)烈依賴員工的個(gè)人能力和經(jīng)驗(yàn)，不利于大規(guī)模推廣[1–2]。在面臨日益復(fù)雜的配載要求時(shí)，人工耗時(shí)變長(zhǎng)，單車滿載率降低，若是導(dǎo)致翻箱，會(huì)極大浪費(fèi)人力成本、時(shí)間成本。因此，有必要設(shè)計(jì)一種煙草配載驗(yàn)證系統(tǒng)，根據(jù)煙草訂單信息、車輛信息以及各類件煙規(guī)格信息等，對(duì)人工設(shè)計(jì)的配載方案進(jìn)行驗(yàn)證并生成裝車圖，指導(dǎo)工作人員進(jìn)行裝車，用于替代目前基于經(jīng)驗(yàn)的人工配載方式，達(dá)到有效減少裝車時(shí)間、提高裝車效率，提高單車滿載率和裝車一次成功率，從而達(dá)到降低物流成本，提高經(jīng)濟(jì)效益的目的。

2 卷煙自動(dòng)配載及驗(yàn)證系統(tǒng)

卷煙自動(dòng)配載及驗(yàn)證系統(tǒng)可以根據(jù)煙草訂單信息、車輛信息、各類件煙規(guī)格信息等生成卷煙裝車圖，也可以輸入人工配載方案進(jìn)行驗(yàn)證并生成裝車圖，以指導(dǎo)工作人員進(jìn)行現(xiàn)場(chǎng)裝車。系統(tǒng)功能框圖如圖1所示，文章重點(diǎn)介紹了配載驗(yàn)證功能模塊中的卷煙裝車驗(yàn)證算法。

圖1 卷煙自動(dòng)配載及驗(yàn)證系統(tǒng)功能框圖

3 卷煙裝車驗(yàn)證算法

裝車驗(yàn)證算法是對(duì)人工設(shè)計(jì)的配載方案，即人工選出需要運(yùn)輸?shù)呢浳锖瓦\(yùn)輸這批貨物的車輛，在正式運(yùn)輸之前驗(yàn)證其準(zhǔn)確率，降低翻箱率。這在本質(zhì)上是三維裝箱問題，給定一些不同類型的箱子和不同規(guī)格的容器，如何將所有的箱子裝入最少數(shù)量的容器中[3–4]。

裝車驗(yàn)證算法的核心是啟發(fā)式擬人裝箱算法。解決這類利用計(jì)算機(jī)幫助人工或優(yōu)化人工操作的實(shí)際問題，通常借鑒豐富的人工經(jīng)驗(yàn)，使計(jì)算機(jī)通過擬人的方式解決問題是非常有效的[5]。在實(shí)際的裝箱過程中，人們通常會(huì)在車廂內(nèi)一角開始放置，先裝滿一行，再在一行的基礎(chǔ)上向上放置裝滿一面，最后從車廂內(nèi)側(cè)到外側(cè)依次裝滿整個(gè)車廂。受人工裝箱方式的影響，在算法的裝箱過程中，通過設(shè)定初始放置點(diǎn)放置箱子，下一個(gè)箱子的放置位置通過查找放置點(diǎn)集合進(jìn)行確定，并通過對(duì)放置點(diǎn)集合進(jìn)行排序完成從車廂內(nèi)側(cè)到外側(cè)的放置過程。

3.1 放置點(diǎn)

可以將車廂看成一個(gè)三維坐標(biāo)系，將車廂內(nèi)側(cè)右下角坐標(biāo)（0，0，0）作為初始放置點(diǎn)并存入放置點(diǎn)集合，放置一個(gè)貨物后會(huì)生成3個(gè)新的放置點(diǎn)，并存入放置點(diǎn)集合中。設(shè)車廂的長(zhǎng)寬高分別為H，W，D，貨物的長(zhǎng)寬高分別為h，w，d，則生成的3個(gè)放置點(diǎn)分別為（h，0，0），（0，w，0），（0，0，d），如圖2所示。

圖2 貨物產(chǎn)生的三個(gè)放置點(diǎn)

因?yàn)樾枰獙⒇浳锇凑諒能噹麅?nèi)側(cè)到外側(cè)的順序放置，則需要對(duì)放置點(diǎn)集合進(jìn)行排序。通過對(duì)放置點(diǎn)按照先y 軸從低到高，再z 軸從低到高，最后x 軸從低到高的順序完成對(duì)放置點(diǎn)的排序，完成實(shí)際的裝箱效果。

3.2 裝箱約束條件

3.2.1 方向約束

貨物在車廂內(nèi)部一共有6種放置方向，但是根據(jù)人工的裝箱經(jīng)驗(yàn)，為了保證煙草在運(yùn)輸過程中不會(huì)出現(xiàn)倒絲的現(xiàn)象，實(shí)際貨物的放置過程中只會(huì)出現(xiàn)4種方向，分別是方向1（h，w，d），方向2（w，h，d），方向3（h，w，d），方向4（d，h，w）如圖3 所示。方向1是將貨物的長(zhǎng)邊作為h也就是長(zhǎng)，而短邊作為寬w，這樣的放置方向可以保證車廂的寬度得到最大利用。當(dāng)方向1放置貨物在車廂內(nèi)長(zhǎng)度無法滿足時(shí)，則使用方向2調(diào)轉(zhuǎn)貨物長(zhǎng)和寬，使得車廂內(nèi)的長(zhǎng)度得到最大利用。當(dāng)方向1放置貨物在車廂內(nèi)高度無法滿足時(shí)，使用方向3或方向4，將貨物水平放置，使得車廂內(nèi)的高度得到最大利用。

圖3 四種放置方向

3.2.2 重疊約束

每一個(gè)貨物的放置位置是根據(jù)之前放置貨物產(chǎn)生的放置點(diǎn)確定的。但是同一車廂內(nèi)會(huì)運(yùn)輸不同種類的貨物，其規(guī)格是不一致的。這樣貨物在放置過程中會(huì)出現(xiàn)間隙，從而導(dǎo)致計(jì)算機(jī)在放置貨物時(shí)會(huì)出現(xiàn)重疊的情況。如果兩個(gè)貨物沒有發(fā)生重疊，這兩個(gè)貨物之間的相交面的個(gè)數(shù)是0代表不相交或者是1代表相鄰放置，但是如果兩個(gè)貨物之間發(fā)生重疊，則這兩個(gè)貨物之間的相交面的個(gè)數(shù)一定會(huì)超過兩個(gè)。利用這一規(guī)則設(shè)計(jì)重疊檢測(cè)條件，當(dāng)貨物之間的相交面?zhèn)€數(shù)小于等于1時(shí)允許放置，否則認(rèn)為其相交取消放置。

3.2.3 懸空約束

計(jì)算機(jī)在計(jì)算貨物的放置位置過程中，某些放置點(diǎn)可能會(huì)因?yàn)樨浳镏g發(fā)生重疊或其他原因而取消放置，導(dǎo)致接下來的貨物可能會(huì)出現(xiàn)懸空的情況，這是違反實(shí)際物理?xiàng)l件的。因此，需要設(shè)置懸空檢測(cè)條件。通過計(jì)算放置點(diǎn)和貨物規(guī)格以及之前已經(jīng)放置的貨物之間的高度信息來判斷貨物是否懸空，滿足條件則放置，否則會(huì)計(jì)算懸空貨物與其底部最近貨物之間的高度，在不違反約束條件的情況下將懸空貨物落到離其底部最近的貨物上。

3.2.4 行間約束

實(shí)際裝箱過程中因?yàn)樨浳锓N類的不同，若兩種貨物之間不加以約束而直接根據(jù)放置點(diǎn)集合中的位置放置，會(huì)出現(xiàn)貨物放置位置混亂，車廂內(nèi)空間利用率降低，不利于貨物的穩(wěn)定運(yùn)輸。所以需要設(shè)計(jì)行間約束條件，保證貨物放置過程中每一行的整齊。主要約束條件有，若下一批貨物的長(zhǎng)度超過了其底下已經(jīng)放置好的貨物長(zhǎng)度，則會(huì)判斷貨物的寬度和其底下貨物長(zhǎng)度之間的關(guān)系，若小于則按方向2進(jìn)行放置，若還是超過底下貨物的長(zhǎng)度則改變貨物的裝載順序，并且貨物的上方只能放置一件貨物，除非多件貨物的長(zhǎng)度不會(huì)超過其底下的貨物。當(dāng)貨物因行間y軸長(zhǎng)度不一致發(fā)生貨物重疊的情況時(shí)，會(huì)記錄此時(shí)已經(jīng)放置的貨物的y軸最大值和因重疊而無法放置貨物的放置點(diǎn)的x值，并依據(jù)這兩個(gè)值生成新的放置點(diǎn)存入放置點(diǎn)集合中，增大空間利用率，保證接下來貨物放置的整齊。

3.3 裝箱算法

基于上述放置點(diǎn)的生成方法和約束條件，可以得到用于配載驗(yàn)證系統(tǒng)的三維裝箱算法。算法設(shè)貨物集合為B={b1，b2，…，bn}，放置點(diǎn)集合為items，其初始值為（0，0，0）用于確定第一個(gè)貨物的放置位置，算法的返回值是一個(gè)集合output 代表已經(jīng)放置貨物在車廂內(nèi)的坐標(biāo)和貨物種類。算法流程圖如圖4所示。

圖4 裝箱算法流程圖

在該裝箱算法中，首先分別從貨物集合B 和放置點(diǎn)集合items 中取出需要的數(shù)據(jù)，之后根據(jù)取出的貨物bi（i ∈1，…，n）的規(guī)格以及放置點(diǎn)的位置判斷其在方向1的情況下能否裝入車內(nèi)。若可以裝入則判斷貨物bi與其他貨物是否發(fā)生重疊，若發(fā)生重疊但是因?yàn)樾虚g長(zhǎng)度不一致導(dǎo)致的重疊則會(huì)根據(jù)行間約束規(guī)則生成新的放置點(diǎn)并存入集合，否則不對(duì)該放置點(diǎn)進(jìn)行放置。若沒有發(fā)生重疊則判斷貨物bi是否懸空。若不懸空并且bi的長(zhǎng)度小于其底部貨物的長(zhǎng)度則在此放置點(diǎn)進(jìn)行放置并生成新的放置點(diǎn)，再去除下一個(gè)放置點(diǎn)和貨物，判斷貨物集合是否裝完。否則按照相應(yīng)的約束規(guī)則進(jìn)行放置。若方向1無法放置貨物則判斷方向2是否可以裝入，若可以則判斷相關(guān)的約束條件是否成立執(zhí)行操作，否則判斷方向3是否可以裝入。若3個(gè)方向都無法裝入貨物則該放置點(diǎn)不進(jìn)行貨物放置，取出下一個(gè)放置點(diǎn)。當(dāng)貨物集合全部裝完返回貨物在車廂內(nèi)的坐標(biāo)和貨物種類并存入output 中。配載驗(yàn)證系統(tǒng)根據(jù)output 來繪制所需的裝車圖。

4 測(cè)試結(jié)果

使用兩天內(nèi)的實(shí)際訂單裝車數(shù)據(jù)來進(jìn)行配載驗(yàn)證功能模塊的測(cè)試，部分測(cè)試結(jié)果如下表1所示，測(cè)試結(jié)果表明卷煙裝車算法可以成功驗(yàn)證人工配載訂單。

表1 測(cè)試結(jié)果

5 結(jié)束語

文章設(shè)計(jì)了一套基于人工經(jīng)驗(yàn)的卷煙裝車驗(yàn)證算法，裝車時(shí)可以充分利用車廂的長(zhǎng)寬高，提高單車滿載率。通過配載驗(yàn)證功能模塊可以對(duì)人工配載訂單進(jìn)行驗(yàn)證，從而提高卷煙裝車效率，保證裝車一次成功，杜絕翻箱現(xiàn)象。由于考慮裝車過車中卷煙的穩(wěn)定性，導(dǎo)致貨物之間會(huì)產(chǎn)生一定空隙從而浪費(fèi)一定的體積，因此該算法還需要進(jìn)一步研究和優(yōu)化。