基于啟發(fā)式算法的貨物裝配策略研究

藍(lán)機(jī)滿 （惠州工程職業(yè)學(xué)院，廣東 惠州 516001）

0 引 言

在一般貨物的二次流通的運(yùn)輸環(huán)節(jié)中，貨物的裝配運(yùn)送工作是中間最復(fù)雜、費(fèi)時(shí)與費(fèi)力最小的一部分，直接影響著各運(yùn)輸相關(guān)部門(mén)間的協(xié)作活動(dòng)的質(zhì)量與時(shí)間成本。隨著運(yùn)輸信息技術(shù)的不斷發(fā)展，貨物運(yùn)輸工具的裝配設(shè)計(jì)方案將完全可以通過(guò)計(jì)算機(jī)仿真模擬來(lái)自動(dòng)生成，并將以此直接指導(dǎo)裝配工作人員之間的裝配運(yùn)送活動(dòng)，以準(zhǔn)確提升運(yùn)輸貨物操作環(huán)節(jié)的協(xié)調(diào)效率和質(zhì)量并最終達(dá)到降低成本的目的。

本文旨在試圖系統(tǒng)構(gòu)建能自動(dòng)生成車輛裝配運(yùn)輸方案的算法，該自動(dòng)算法可以實(shí)現(xiàn)將裝載貨物快準(zhǔn)狠且有效安全地自動(dòng)裝入車輛車廂系統(tǒng)中，而且可同時(shí)滿足任何給定的車輛車廂系統(tǒng)，自動(dòng)裝配完車上所有余留的貨物。為了有效驗(yàn)證該算法中生成的自動(dòng)裝配工藝方案的整體可行性，本文利用了SharpGL圖形包來(lái)對(duì)生成工藝的整體方案的正確性做了進(jìn)一步驗(yàn)證，實(shí)驗(yàn)最終結(jié)果表明，該算法可以較為合理、高效、經(jīng)濟(jì)地設(shè)計(jì)完成自動(dòng)化裝配。

國(guó)內(nèi)學(xué)者提出了以下觀點(diǎn)：張游天等（2021）提出，在美國(guó)時(shí)下比較廣泛流行使用的對(duì)貨物進(jìn)行自動(dòng)化裝配問(wèn)題的分類研究方法[1]；江峰等（2020）提出，大規(guī)模貨物列車，在運(yùn)行階段需要通過(guò)編制啟發(fā)式的算法，對(duì)物流運(yùn)輸方式進(jìn)行優(yōu)化整合[2]；王張峰等（2017）提出，基于啟發(fā)式算法的托盤(pán)貨物優(yōu)化裝載方法，依據(jù)貨物數(shù)量進(jìn)行自動(dòng)裝配繼而將所有可能同時(shí)出現(xiàn)的車輛車廂的貨物進(jìn)行自動(dòng)化裝配[3]；鄭煒等（2016）提出，在貨物混裝模式中，可以通過(guò)啟發(fā)式的算法，對(duì)貨物裝載問(wèn)題進(jìn)行研究，提高貨物運(yùn)輸質(zhì)量[4]；宿偉偉等（2007）提出，多品種貨物混裝配載模型可以通過(guò)啟發(fā)式的算法，對(duì)貨物的運(yùn)輸方法進(jìn)行計(jì)算與整合[5]；徐海東等（2004）提出，啟發(fā)式算法在非滿載貨物運(yùn)輸優(yōu)化調(diào)度中的應(yīng)用，需要通過(guò)對(duì)啟發(fā)式算法進(jìn)行預(yù)判，進(jìn)而優(yōu)化物流運(yùn)輸中的路徑，對(duì)風(fēng)險(xiǎn)起到一定的規(guī)避作用[6]。

1 貨物自動(dòng)化裝配問(wèn)題

1.1 貨物自動(dòng)化裝配概述

貨物集裝箱的計(jì)算機(jī)自動(dòng)化的裝配及設(shè)計(jì)問(wèn)題，就是指怎樣利用現(xiàn)代工業(yè)計(jì)算機(jī)通過(guò)自動(dòng)編程把各種型號(hào)、不同規(guī)格的一些大型特殊包裝貨物自動(dòng)、合理、準(zhǔn)確地安裝到專用車廂系統(tǒng)內(nèi)的裝配系統(tǒng)方案。貨物方面的綜合裝配設(shè)計(jì)技術(shù)問(wèn)題實(shí)際上已經(jīng)不是某一類最原始、簡(jiǎn)單的技術(shù)設(shè)計(jì)理論問(wèn)題，而是由許多不同形式和種類各異的技術(shù)裝配和工藝問(wèn)題所共同組成的關(guān)于裝配設(shè)計(jì)的綜合理論問(wèn)題。根據(jù)不同層次的研究?jī)?nèi)容和約束限制條件，可以適當(dāng)?shù)貙⑵溲芯考?xì)分為兩個(gè)不同階段的分支。貨物裝配最優(yōu)化是一類多目標(biāo)組合的優(yōu)化完全問(wèn)題，其理論本質(zhì)仍然是NP-HARD問(wèn)題，而目前解決NP問(wèn)題的較為傳統(tǒng)的方法就是利用元啟發(fā)算法模式不斷地去找尋算法，不斷地在不同的空間中找尋最優(yōu)解。

1.2 貨物自動(dòng)化裝配問(wèn)題的分類

一個(gè)三維空間的裝配問(wèn)題是貨物的自動(dòng)化裝配。近些年來(lái)有較多的分類方法。將裝配問(wèn)題大致劃分為兩類：裝配多的車輛車廂問(wèn)題；集裝箱車輛車廂問(wèn)題。

1.3 貨物自動(dòng)化裝配問(wèn)題的技術(shù)難點(diǎn)

實(shí)際上，在運(yùn)輸過(guò)程中，貨物的形狀、數(shù)量復(fù)雜，并且在整個(gè)貨物車廂的尺寸不確定的情況下，解決好對(duì)整體貨物的準(zhǔn)確自動(dòng)裝配，并且同時(shí)又要能滿足在貨物自動(dòng)準(zhǔn)確裝配作業(yè)時(shí)存在著的許多約束性條件和可控制性技術(shù)條件是當(dāng)前面臨著的重要技術(shù)難點(diǎn)。

在實(shí)際進(jìn)行貨物的組裝與擺放或運(yùn)輸活動(dòng)時(shí)，貨物可能就存在著以下7種不同類型的實(shí)際裝配、擺放及運(yùn)輸活動(dòng)狀態(tài)，在貨物的包裝結(jié)構(gòu)的實(shí)際幾何形狀是長(zhǎng)方體的情況下，仍然有6種不同類型的實(shí)際裝配狀態(tài)。見(jiàn)圖1。

圖1 長(zhǎng)方體6種貨物擺放圖

2 核心算法

2.1 算法的基本思想

本文的目的主要是在求解貨物的自動(dòng)裝配法約束原則下，尋求到一種以劃分平面理論為基礎(chǔ)的求解貨物在自動(dòng)化裝配下的誤差的方法。將車廂的底部分為20個(gè)等面積的小格。如果想要提高自動(dòng)化裝配系統(tǒng)的標(biāo)準(zhǔn)度，可將車廂劃分為若干個(gè)更多數(shù)量的小格子。

假設(shè)貨物的裝配層數(shù)要求為NumLayer，貨物將只有圖1所示的第一種和第二種放置狀態(tài)。將當(dāng)前被選擇到的貨物號(hào)碼的長(zhǎng)記為L(zhǎng)i，寬記為Wi，高記為Hi；由原點(diǎn)出發(fā)，然后沿著X軸正方向不斷疊加查找，找到第一個(gè)空白小格子，再開(kāi)始依次累加長(zhǎng)，記小格子的累加長(zhǎng)為L(zhǎng)sum，當(dāng)Lsum≥Wi，從找到的第一個(gè)空白小格子的位置開(kāi)始順著Y軸正方向依次不斷累加小格子的寬，直至到達(dá)車廂內(nèi)的底面邊緣或小格子上已經(jīng)填上順序編號(hào)，則停止累加。記小格子的累加寬為Wsum，當(dāng)Wsum≥Li，就可以判斷出車廂長(zhǎng)度與貨物長(zhǎng)度之間的關(guān)系，在累加過(guò)程中，若不能同時(shí)滿足Lsum≥Wi、Wsum≥Li的條件時(shí)， 就需要變換到圖一貨物的放置狀態(tài)，經(jīng)過(guò)不斷操作得出貨物高度小于車廂內(nèi)高。

假設(shè)車廂內(nèi)長(zhǎng)為L(zhǎng)carriage，寬為Wcarriage，高為Hcarriage。通過(guò)公式（1）與公式（2）將貨物放置狀態(tài)設(shè)置為圖 1 所示的第一種和第二種放置狀態(tài)時(shí)，單個(gè)貨物進(jìn)行裝配時(shí)的一般約束條件為公式（1）（2）。

2.2 改進(jìn)思想

上述計(jì)算模型提供了最終貨物裝配的另一個(gè)基本思路，但是算法仍然存在著以下三個(gè)顯著缺陷：算法在對(duì)最后的貨物和最終裝配的設(shè)計(jì)進(jìn)行處理時(shí)，只先考慮了如圖1所展示的狀態(tài)；算法有貪婪性，讓算法無(wú)法實(shí)現(xiàn)最優(yōu)解；在一定的車輛數(shù)量下，會(huì)要求其裝配貨物的數(shù)量、體積等，但是此算法下對(duì)此要求無(wú)法達(dá)到百分之百符合，而且還存在問(wèn)題。啟發(fā)式的算法需要將貨物運(yùn)輸?shù)捏w積與運(yùn)行方式計(jì)算進(jìn)去，套用啟發(fā)式算法公式，對(duì)之后的模型建設(shè)進(jìn)行相關(guān)處理，以提高物流運(yùn)輸?shù)男省?/p>

3 實(shí)驗(yàn)仿真與分析

3.1 實(shí)驗(yàn)配置

本文作者擬嘗試選用一種基于微軟C語(yǔ)言平臺(tái)環(huán)境下所開(kāi)發(fā)出的OpenGL函數(shù)庫(kù)仿真軟件SharpGL來(lái)仿真模擬以及對(duì)裝配的算法結(jié)果進(jìn)行仿真模擬和驗(yàn)證。SharpGL開(kāi)發(fā)者們應(yīng)該可以比較輕松地使用微軟視窗的Windows操作系統(tǒng)中的Forms或WPF，應(yīng)用中能夠輕松實(shí)現(xiàn)使用OpenGL函數(shù)庫(kù)來(lái)開(kāi)發(fā)出圖形可視化設(shè)計(jì)。借助SharpGL，可以保證在較短期范圍內(nèi)迅速實(shí)現(xiàn)和建立出對(duì)裝配算法效果的模擬分析及仿真。

3.2 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)對(duì)算法進(jìn)行了操作與驗(yàn)證，該實(shí)驗(yàn)具有三個(gè)約束條件如下：先尋找一批貨物和卡車，要求都為長(zhǎng)方形，需要將給定貨物裝配到給定的車輛車廂中；貨物可以分為4類，其中第一、二、三類不可以混裝，第四類可以混裝；要求貨物底面接地，按照表1的車廂尺寸放置貨物，當(dāng) NumLayer 為 1 時(shí)，1 層就是貨物裝配 ，并且采用表2的貨物尺寸。表1和表2分別是給定的車輛車廂尺寸和給定的貨物尺寸。

表1 給定的車輛車廂尺寸mm

表2 給定的貨物尺寸mm

4 結(jié) 論

三維貨物中的裝配約束問(wèn)題是另一個(gè)難以完全被有效的方法解決的NP-HARD問(wèn)題，當(dāng)對(duì)三維貨物中裝配的各種約束條件和限制條件都給定很多遍時(shí)，很難得到一個(gè)完全滿意的結(jié)果。

本文擬利用研究結(jié)果提出來(lái)另一種基于平面分割的設(shè)計(jì)算法方案，提供給廣大用戶一種基于集裝箱貨物的自動(dòng)化裝配的算法方案，但研究發(fā)現(xiàn)目前本方法設(shè)計(jì)及算法模型設(shè)計(jì)仍存在很多局限，如尚不能很充分合理地利用車廂內(nèi)的面積和空間，對(duì)于各種異構(gòu)貨物集裝箱的自動(dòng)裝配，尚還不能很充分地滿足車廂空間布置需求以及實(shí)現(xiàn)集裝箱貨物自動(dòng)化裝配系統(tǒng)的基本約束條件和設(shè)計(jì)條件?；诖嬖诘母鞣N問(wèn)題，本文已分別提出了對(duì)其改進(jìn)的舉措和一些新想法，預(yù)計(jì)今后將會(huì)在進(jìn)一步的研究調(diào)查工作中給出一些相關(guān)的數(shù)據(jù)以支持和證明。