基于神經(jīng)網(wǎng)絡(luò)的煙草物流配送路徑優(yōu)化研究

萬(wàn)貴華，陳昌明，徐 方，高向東，武長(zhǎng)征，曾 蕾， 甘 露，李小峰，許軍華，鄧 敏 ，徐 瓊

(1. 湖北省煙草公司孝感市公司 物流中心，湖北 孝感 432000； 2. 湖北工程學(xué)院 計(jì)算機(jī)與信息科學(xué)學(xué)院，湖北 孝感 432000)

隨著我國(guó)煙草物流的不斷發(fā)展，其規(guī)模逐年遞增，物流建設(shè)也越來(lái)越受到行業(yè)的重視，對(duì)煙草物流也有了更多的投資。當(dāng)今煙草物流的建設(shè)工作按照“由小到大、由內(nèi)到外、由商流到物流”的原則逐步開(kāi)展[1]。影響煙草行業(yè)經(jīng)濟(jì)效益的因素眾多，其中，煙草物流這一因素對(duì)煙草行業(yè)總體經(jīng)濟(jì)效益影響最為顯著。近年來(lái)，國(guó)家越來(lái)越重視煙草物流的建設(shè)工作，煙草物流的信息化和智能化有了長(zhǎng)足的進(jìn)展。同時(shí)，國(guó)家政策也給行業(yè)物流提供了大力支持，使得煙草商業(yè)交易的網(wǎng)絡(luò)化、智能化不斷完善[2]。

然而，國(guó)內(nèi)煙草物流行業(yè)仍存在許多不足。首先，物流環(huán)節(jié)獨(dú)立管理和運(yùn)作無(wú)法形成大規(guī)模的統(tǒng)一管理模式，從而不能獲得大規(guī)模物流效益，因此難以由量到質(zhì)的改變。其次，物流基礎(chǔ)設(shè)施總體布局不科學(xué)、不統(tǒng)一，影響物流效率[3]。最后，長(zhǎng)遠(yuǎn)規(guī)劃不足，缺少科學(xué)的管理，需要有合理的系統(tǒng)管理軟件來(lái)搭配硬件設(shè)施進(jìn)行高效管理。

物流配送路徑優(yōu)化是國(guó)內(nèi)外學(xué)者競(jìng)相研究的熱點(diǎn)問(wèn)題?；谧疃搪窂降牡辖芩固乩?Dijkstra)算法是較早提出的著名路徑優(yōu)化算法[4]，該算法是求解圖中的一個(gè)頂點(diǎn)到圖中其他各點(diǎn)的最短路徑，使用貪心算法策略最終解決有權(quán)圖的路徑優(yōu)化問(wèn)題[5]?；谙伻旱膬?yōu)化算法是模仿螞蟻尋找食物時(shí)進(jìn)行路徑發(fā)現(xiàn)的方法[6]，是一種概率型路徑優(yōu)化算法。基于遺傳算法[7]的多目標(biāo)路徑優(yōu)化方法根據(jù)生物在自然界中的進(jìn)化規(guī)律而設(shè)計(jì)[8]，通過(guò)模擬自然選擇和生物進(jìn)化的過(guò)程搜尋最優(yōu)路徑?；趧?dòng)態(tài)規(guī)劃思想的Floyd算法可以在加權(quán)圖中搜尋給定節(jié)點(diǎn)到多源點(diǎn)之間的最短路徑[9]。但是上述算法都有各自的不足之處，存在學(xué)習(xí)效率低、收斂速度慢，或者容易陷入局部最優(yōu)解等問(wèn)題。為了在煙草物流配送路徑規(guī)劃中克服上述不足，尋找最優(yōu)配送路徑，本文提出了改進(jìn)的神經(jīng)網(wǎng)絡(luò)路徑優(yōu)化算法，提高優(yōu)化效率，避免算法陷入局部最優(yōu)解。

1 煙草物流配送概述

煙草物流中最重要的是配送路徑的優(yōu)化問(wèn)題。主要存在車(chē)輛路徑問(wèn)題、旅行商問(wèn)題、路徑優(yōu)化問(wèn)題，還需要考慮貨物量、車(chē)輛的裝載量、車(chē)輛行駛時(shí)間等因素。

1.1 車(chē)輛路徑問(wèn)題

車(chē)輛路徑問(wèn)題通常是指貨物由一個(gè)點(diǎn)或者配送中心的一輛或多輛運(yùn)輸車(chē)分配到多個(gè)需求點(diǎn)的過(guò)程(如圖1所示)。此過(guò)程可能存在時(shí)間窗口、負(fù)載限制等制約因素。經(jīng)過(guò)合理規(guī)劃車(chē)輛后，能使整個(gè)配送過(guò)程滿(mǎn)足一些目標(biāo)，例如成本最少或者時(shí)間最少等。近年來(lái)，車(chē)輛路徑的優(yōu)化是各國(guó)研究者競(jìng)相研究的熱點(diǎn)問(wèn)題，其研究成果有著廣泛的應(yīng)用領(lǐng)域，適用于許多行業(yè)的車(chē)輛路徑規(guī)劃。該研究成果可以有效降低企業(yè)的運(yùn)輸成本，提高運(yùn)行效率和經(jīng)濟(jì)效益，具有較高的研究?jī)r(jià)值和很好的經(jīng)濟(jì)效益。

圖1 車(chē)輛路徑問(wèn)題示意圖

1.2 旅行商問(wèn)題

旅行商問(wèn)題的定義可描述為一個(gè)商人需要前往多個(gè)目的地，其中每個(gè)目的地都必須且只能路過(guò)一次，當(dāng)該商人最終返回出發(fā)點(diǎn)時(shí)，本次旅行結(jié)束。而待解決的問(wèn)題便是如何使該商人的旅行總路徑最少，或者花費(fèi)的時(shí)間最短，或者是產(chǎn)生的費(fèi)用開(kāi)銷(xiāo)最少。

下面對(duì)這一問(wèn)題進(jìn)行數(shù)學(xué)建模，商人要去的地點(diǎn)集合可以記為C={C1，C2，…，Cn}，地點(diǎn)Ci與地點(diǎn)Cj之間的距離可以表示為d(Ci，Cj)∈Z+，要求集合C中的每個(gè)地點(diǎn)被經(jīng)過(guò)一次，則路徑可以表示為(Ck1，Ck2，…，Ckn)，該路徑要滿(mǎn)足如下表達(dá)式的值最小，表達(dá)式如下：

(1)

式中：k1，k2，…，kn是1，2，…，n的一個(gè)置換。

1.3 路徑優(yōu)化問(wèn)題

目前的車(chē)輛路徑優(yōu)化算法可分為兩類(lèi)，分別是精確算法和啟發(fā)式算法。啟發(fā)式算法是目前研究的熱點(diǎn)，它又可以細(xì)分為傳統(tǒng)啟發(fā)式算法和現(xiàn)代啟發(fā)式算法。對(duì)于精確算法來(lái)說(shuō)，它的主要優(yōu)點(diǎn)在于，處理較小規(guī)模問(wèn)題，能較快獲得最優(yōu)解。然而在處理大規(guī)模問(wèn)題時(shí)，這種類(lèi)型的算法需要大量的運(yùn)算時(shí)間，不能應(yīng)用于實(shí)時(shí)性要求高的場(chǎng)景。這種類(lèi)型的算法主要有切平面法、Dijkstra算法、動(dòng)態(tài)規(guī)劃法和和分支定界法。

啟發(fā)式算法是相對(duì)于精確算法而提出的，是根據(jù)工作經(jīng)驗(yàn)的積累或受到自然現(xiàn)象的啟發(fā)來(lái)尋求解決方案，采用全局概率搜索法求解問(wèn)題。傳統(tǒng)啟發(fā)式算法的主要特點(diǎn)是更傾向于在可接受范圍內(nèi)尋求最優(yōu)解。這些算法主要有：兩階段法、插入算法、節(jié)約算法、掃描算法等。然而，現(xiàn)代啟發(fā)式算法在階段計(jì)算的結(jié)果中允許次優(yōu)解。這方面的典型算法有遺傳算法[10]、模擬退火算法[11]、蟻群算法[12]、禁忌搜索算法[13]和比較流行的神經(jīng)網(wǎng)絡(luò)算法。啟發(fā)式算法雖然不能保證問(wèn)題的最優(yōu)解，但在大規(guī)模問(wèn)題的場(chǎng)景求解時(shí)可以快速找到較好的解。

2 神經(jīng)網(wǎng)絡(luò)路徑優(yōu)化算法

人工神經(jīng)網(wǎng)絡(luò)采用許多電子元器件模擬生物神經(jīng)網(wǎng)絡(luò)中的神經(jīng)元，這些電子元器件進(jìn)行大規(guī)模的連接以適應(yīng)于并行處理模式，并組建神經(jīng)網(wǎng)絡(luò)模擬人腦的運(yùn)行方式，實(shí)現(xiàn)人腦的部分功能。由于它可以通過(guò)大量樣本的學(xué)習(xí)訓(xùn)練來(lái)處理復(fù)雜事物關(guān)系，特別適合解決各類(lèi)預(yù)測(cè)、分類(lèi)、評(píng)估匹配、識(shí)別等問(wèn)題，因此在金融、 航空、醫(yī)學(xué)、環(huán)保等領(lǐng)域都有應(yīng)用的前景。

2.1 Hopfield神經(jīng)網(wǎng)絡(luò)

在上世紀(jì)80年代，美國(guó)科學(xué)家霍普菲爾德將能量函數(shù)相關(guān)的內(nèi)容引入到對(duì)稱(chēng)網(wǎng)絡(luò)的研究中，進(jìn)而研究出了Hopfield模型。這種方式對(duì)網(wǎng)絡(luò)的穩(wěn)定性有較大的改善，對(duì)于當(dāng)前神經(jīng)網(wǎng)絡(luò)的發(fā)展有非常大的促進(jìn)作用。下面的圖2為離散Hopfield神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖。

圖2 三層離散Hopfield神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖

圖2中的第0層是網(wǎng)絡(luò)的輸入，并非神經(jīng)元，因此不參與計(jì)算；真實(shí)的神經(jīng)元是從圖中第1層開(kāi)始，因此從該層開(kāi)始根據(jù)第0層的輸入信息執(zhí)行函數(shù)處理產(chǎn)生輸出。該模型將會(huì)比較其輸出結(jié)果與閾值函數(shù)f，如果輸出結(jié)果大于閾值θ，則模型輸出值等于1；否則，模型輸出值等于0。

對(duì)于二值神經(jīng)元，它的計(jì)算公式如下

(2)

式中：Xj為外部輸入，且

(3)

2.2 神經(jīng)網(wǎng)絡(luò)與路徑優(yōu)化

區(qū)域物流網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)有著許多相同之處，在神經(jīng)網(wǎng)絡(luò)模型中，神經(jīng)元是區(qū)域物流網(wǎng)絡(luò)中的節(jié)點(diǎn)，而神經(jīng)網(wǎng)絡(luò)中的邊則是各節(jié)點(diǎn)之間的關(guān)系，輸入是商戶(hù)地理位置信息和車(chē)輛信息，輸出則是配送路徑和時(shí)間預(yù)測(cè)信息。因此，本文利用神經(jīng)網(wǎng)絡(luò)的高容錯(cuò)性和智能處理能力，采用改進(jìn)的人工神經(jīng)網(wǎng)絡(luò)模型來(lái)推理優(yōu)化物流配送路徑，將有效提高物流配送效率，帶來(lái)更大的經(jīng)濟(jì)效益。

當(dāng)前已有一些神經(jīng)網(wǎng)絡(luò)模型被應(yīng)用于物流配送路徑優(yōu)化中，Caulfield等學(xué)者成功的將脈沖耦合神經(jīng)網(wǎng)絡(luò)模型應(yīng)用于解決迷宮中的最短路徑問(wèn)題，但這種求解方式需要每個(gè)節(jié)點(diǎn)都與神經(jīng)元一一對(duì)應(yīng)，但是神經(jīng)元數(shù)量龐大；為了克服這一問(wèn)題，提出了時(shí)延脈沖耦合神經(jīng)網(wǎng)絡(luò)[14]，它既保持了脈沖耦合神經(jīng)元的優(yōu)點(diǎn)，又能減少神經(jīng)元數(shù)量；多輸出脈沖耦合神經(jīng)網(wǎng)絡(luò)[15]采取線(xiàn)性閾值和多輸出，有效減少了迭代頻率，從而降低計(jì)算復(fù)雜度，使它僅僅和最短路徑的長(zhǎng)度有關(guān)；三態(tài)級(jí)聯(lián)脈沖耦合神經(jīng)網(wǎng)絡(luò)[16]通過(guò)并行方式且有效的處理了信號(hào)在神經(jīng)元之間的傳輸方向，增加了神經(jīng)網(wǎng)絡(luò)的計(jì)算速度[17]。上述方法都不太適合于煙草物流的特定場(chǎng)景，但受上述研究基礎(chǔ)的啟發(fā)，本文提出了改進(jìn)的神經(jīng)網(wǎng)絡(luò)的路徑優(yōu)化算法。

2.3 改進(jìn)的神經(jīng)網(wǎng)絡(luò)路徑優(yōu)化算法

圖3 神經(jīng)網(wǎng)絡(luò)模型基本結(jié)構(gòu)

在該神經(jīng)網(wǎng)絡(luò)模型中，網(wǎng)絡(luò)的輸入為：

x(k-1)=[x1(k-1)，…，xn(k-1)，xn+1(k-1)，…，xni(k-1)]Tni=n+m+1

(4)

輸出為：

(5)

式中：N1，N2是第1、2層神經(jīng)元數(shù)；wij為第一層到第二層的權(quán)值系數(shù)，w1j1是第2層到第3層的權(quán)值系數(shù)；θij和θ2是偏置值。

神經(jīng)網(wǎng)絡(luò)根據(jù)樣本的輸入來(lái)調(diào)節(jié)權(quán)值，使輸出值更接近期望值，以此獲得最優(yōu)路徑。實(shí)驗(yàn)結(jié)果表明該算法在優(yōu)化性能方面取得了較好的預(yù)測(cè)效果，具有一定的有效性和實(shí)用性。在上世紀(jì)50年代，研究者提出了模擬退火算法。在組合優(yōu)化領(lǐng)域，后來(lái)的研究者引入了模擬退火算法，并成功進(jìn)行應(yīng)用。模擬退火算法是一種基于迭代求解策略的、有效的隨機(jī)尋優(yōu)算法。它利用了物理中固體物質(zhì)的退火過(guò)程和一般組合優(yōu)化問(wèn)題之間具有的某種相似性特征，能夠使用求解過(guò)程大概率的跳出局部最優(yōu)解，盡可能地向全局最優(yōu)解趨近。模擬退火算法可以作為一種通用的優(yōu)化算法，具有較高的實(shí)用價(jià)值，目前已經(jīng)廣泛的應(yīng)用于工業(yè)控制和工程技術(shù)領(lǐng)域。

本文結(jié)合神經(jīng)網(wǎng)絡(luò)和經(jīng)典的模擬退火算法的優(yōu)勢(shì)，提出了一種改進(jìn)的神經(jīng)網(wǎng)絡(luò)算法，用于進(jìn)行煙草物流中的路徑規(guī)劃，優(yōu)化原有煙草物流配送路徑。

本文在傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)算法中引入模擬退火算法的思想形成了一種改進(jìn)的神經(jīng)網(wǎng)絡(luò)算法。模擬退火算法思想有利于改進(jìn)算法結(jié)果的反饋方式。另一方面，利用Hopfield的能量函數(shù)來(lái)優(yōu)化原模擬退火算法的初始值，將兩種算法的優(yōu)勢(shì)加以融合來(lái)彌補(bǔ)各自的缺點(diǎn)。相比于傳統(tǒng)神經(jīng)網(wǎng)絡(luò)，該算法具有較高的收斂速度和求解速度。其改進(jìn)的神經(jīng)網(wǎng)絡(luò)流程圖如圖4所示，其中Ek為退火算法的初始值，Ek退火算法得了的另一計(jì)算值，p為程序設(shè)定的概率閾值，Tk為k時(shí)刻的溫度，exp表達(dá)式為模擬退火算法中的經(jīng)典表達(dá)式。

圖4 改進(jìn)的神經(jīng)網(wǎng)絡(luò)算法流程圖

改進(jìn)的神經(jīng)網(wǎng)絡(luò)算法在自學(xué)習(xí)和自適應(yīng)方面有著較強(qiáng)的能力。因此，在非可控因素(例如路段、車(chē)流量、送貨時(shí)限等)對(duì)物流配送造成影響的問(wèn)題上能進(jìn)行自我調(diào)節(jié)。該算法的實(shí)現(xiàn)降低物流配送成本、提高效率，從而獲得更高的經(jīng)濟(jì)效益。

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

本文以湖北省煙草公司孝感市公司與湖北工程學(xué)院合作的研發(fā)項(xiàng)目為實(shí)例進(jìn)行研究。通過(guò)對(duì)湖北省煙草公司孝感市公司煙草物流中心的配送路徑進(jìn)行研究，充分了解現(xiàn)有車(chē)輛信息、配送路徑、送貨時(shí)長(zhǎng)等情況，對(duì)目前煙草物流中的安排調(diào)度和配送路徑進(jìn)行了研究，最終應(yīng)用在項(xiàng)目組開(kāi)發(fā)的煙草物流配送路徑優(yōu)化系統(tǒng)上。該系統(tǒng)實(shí)現(xiàn)了煙草物流配送的智能優(yōu)化，可根據(jù)當(dāng)前客戶(hù)的訂貨量和客戶(hù)的地理位置分布動(dòng)態(tài)生成最優(yōu)配送路徑。該項(xiàng)目改變了原先利用經(jīng)驗(yàn)的人工線(xiàn)路規(guī)劃，利用計(jì)算機(jī)輔助，使得煙草物流路徑規(guī)劃更加科學(xué)合理，從而起到提高效率、減低成本、方便配送的作用。

下面以孝感市孝昌縣的煙草物流配送為例。研究者組織人員對(duì)該縣的煙草物流進(jìn)行調(diào)研。首先，了解現(xiàn)有物流配送的運(yùn)行情況以及存在的問(wèn)題；其次，采集每個(gè)客戶(hù)的地理位置，記錄其對(duì)應(yīng)的經(jīng)度和緯度；最后，調(diào)研進(jìn)行路徑優(yōu)化時(shí)的約束條件，如對(duì)配送時(shí)間的要求、線(xiàn)路條數(shù)的要求、配送車(chē)輛的數(shù)量和裝載量，等等。通過(guò)前期大量的調(diào)研，研究者采集到了進(jìn)行路徑優(yōu)化的所有數(shù)據(jù)。最后將客戶(hù)位置信息映射到地理信息系統(tǒng)中，為算法的研究做好準(zhǔn)備。將本文提出的算法應(yīng)用于物流配送的前后進(jìn)行對(duì)比，具體數(shù)據(jù)如表1所示。

表1 算法應(yīng)用前后的相關(guān)數(shù)據(jù)對(duì)比

從表1中的數(shù)據(jù)可以看出，在配送客戶(hù)數(shù)和配送周期相同的情況下，在使用本文提出的算法后，孝昌縣煙草物流配送的車(chē)輛數(shù)、配送里程、線(xiàn)路條數(shù)都有所減少，其中車(chē)輛數(shù)減少了25%，配送里程減少了31.8%，線(xiàn)路條數(shù)減少了25%。從總體上看，基于本文所提出的路徑優(yōu)化算法開(kāi)發(fā)的系統(tǒng)達(dá)到了預(yù)期的目的，能為企業(yè)降低成本，增加效益。在系統(tǒng)中提供了相關(guān)參數(shù)的修改模塊，以適應(yīng)不同應(yīng)用場(chǎng)景的要求，提供系統(tǒng)的可維護(hù)性和使用范圍。

4 小結(jié)

本文首先分析了煙草物流行業(yè)的發(fā)展背景和趨勢(shì)，然后描述了煙草物流配送中的三個(gè)關(guān)鍵問(wèn)題，分別是車(chē)輛路徑問(wèn)題、旅行商問(wèn)題和路徑優(yōu)化問(wèn)題。接著利用神經(jīng)網(wǎng)絡(luò)建立了煙草物流路徑優(yōu)化的模型，并引入模擬退火算法對(duì)其進(jìn)行了改進(jìn)。改進(jìn)的算法能夠避免陷入局部最優(yōu)解，具有很好的全局收斂性。本文以煙草配送為應(yīng)用場(chǎng)景，每個(gè)配送點(diǎn)都是固定的，線(xiàn)路的起點(diǎn)和終點(diǎn)也都是固定的，在路徑生成中使用初始點(diǎn)采用固定值，初始點(diǎn)不參加路徑的交換活動(dòng)。這樣使得算法具有較好的可用性。目前算法中的一些參數(shù)主要是根據(jù)經(jīng)驗(yàn)進(jìn)行確定，下一步將利用相關(guān)理論和實(shí)驗(yàn)分析進(jìn)行參數(shù)的調(diào)優(yōu)，使算法能夠輸出更好的結(jié)果。