柔性物流調(diào)度高空載率規(guī)避策略

鄭 翔 ，孫 霞 ，許彤彤

(1.安徽理工大學(xué) 電氣與信息工程學(xué)院，安徽 淮南 232001；2.阜陽師范大學(xué) 商學(xué)院，安徽 阜陽 236037)

數(shù)據(jù)顯示占我國70%以上的貨物是通過公路運(yùn)輸?shù)模锪髫涇嚳蛰d率高達(dá)40%[1]，這就使得物流運(yùn)輸效率低下。物流供應(yīng)鏈的負(fù)載是產(chǎn)品，因而對(duì)其追蹤非常重要[2]。

針對(duì)文獻(xiàn)[1]中提出的問題，本文提出一種基于NBIOT技術(shù)的物流調(diào)度系統(tǒng)。用智能云平臺(tái)實(shí)現(xiàn)終端設(shè)備監(jiān)控，以及數(shù)據(jù)分析，這一過程可大大降低物流車空載率。降低空載率的思想是當(dāng)物流車卸貨后就給其裝入貨物使物流車保持滿載狀態(tài)。當(dāng)物流車到達(dá)中轉(zhuǎn)站后卸下一定量的貨物，立即前往各個(gè)貨源地裝貨。在這一過程中使用蟻群算法為物流車設(shè)計(jì)遍歷貨源地路線，因?yàn)樗惴ū旧矶即嬖谧陨淼娜毕?，倘若使用基本蟻群算法，得到的路線并不是最優(yōu)的。在此對(duì)蟻群算法進(jìn)行優(yōu)化，文獻(xiàn)[3-7]提出的優(yōu)化方法中均沒有考慮到一個(gè)關(guān)鍵點(diǎn)，即在蟻群算法實(shí)現(xiàn)的初期，路徑上存在的信息素量很少，這樣就加大了蟻群算法搜索的盲目性，很容易使算法陷入局部最優(yōu)。本文先對(duì)蟻群算法進(jìn)行預(yù)迭代若干次，通過學(xué)習(xí)知道哪條路徑上存在信息素。在正式迭代的過程中，路徑上加入一定量的信息素。這樣就可解決算法迭代初期的盲目性問題。實(shí)驗(yàn)證明該方法可以規(guī)避局部最優(yōu)的情況，尋找到更優(yōu)路徑。

1 系統(tǒng)總體設(shè)計(jì)方案

傳統(tǒng)的物流行業(yè)采取的方式是給每個(gè)物流車事先規(guī)定好行駛路線，到每個(gè)中轉(zhuǎn)站后卸下一部分貨物，待貨物卸空以后空車返回。這樣就造成了極高的物流空載率。或者是從起點(diǎn)到終點(diǎn)物流車是直達(dá)的，中途不停車卸貨，這樣就會(huì)占用過多的物流車資源。

作為本物流系統(tǒng)重要一環(huán)的物流車可看做系統(tǒng)終端，許多終端構(gòu)成龐大的終端網(wǎng)。每個(gè)終端作為感知層都會(huì)采集物流車的位置信息。然后將此信息上傳給華為云平臺(tái)。華為云平臺(tái)又可與私有云平臺(tái)通信進(jìn)行相應(yīng)的信息交流。私有云平臺(tái)通過Apache服務(wù)器、MySQL，和PHP來搭建，它將對(duì)從華為云平臺(tái)獲取的信息進(jìn)行數(shù)據(jù)庫構(gòu)建[8-12]。當(dāng)買家提交訂單以后，賣家就會(huì)將買家和賣家的位置信息以及物流包裹的體積值提交至私有云平臺(tái)建立數(shù)據(jù)庫，當(dāng)物流車到達(dá)一個(gè)中轉(zhuǎn)站以后卸下相應(yīng)的貨物。這時(shí)私有云平臺(tái)會(huì)根據(jù)卸下包裹的體積值計(jì)算出當(dāng)前物流車空著的體積，然后在數(shù)據(jù)庫檢索與該物流車當(dāng)前位置最近的幾個(gè)賣家發(fā)貨點(diǎn)，并且買家所處的位置也在該物流車途經(jīng)的中轉(zhuǎn)站內(nèi)，即對(duì)賣家發(fā)貨包裹的體積值進(jìn)行累加,當(dāng)總體積值剛好大于此物流車空著的體積時(shí)，選取累加最后一次之前所有的包裹（不含最后一次），這些包裹所處的位置就是物流車的取貨點(diǎn)。為了對(duì)每個(gè)賣家點(diǎn)進(jìn)行高效遍歷，采用蟻群算法設(shè)計(jì)好物流車的遍歷路線，私有云平臺(tái)將此路線發(fā)送給物流車司機(jī)的移動(dòng)終端。當(dāng)遍歷一圈以后回到中轉(zhuǎn)站位置，此時(shí)物流車恢復(fù)滿載狀態(tài)。接著駛往下一個(gè)中轉(zhuǎn)站，重復(fù)上一個(gè)中轉(zhuǎn)站的過程，當(dāng)?shù)竭_(dá)終點(diǎn)時(shí)，將物流車卸空以后以相同的方式讓物流車滿載。物流車從終點(diǎn)到起點(diǎn)重復(fù)從起點(diǎn)到終點(diǎn)的過程。圖1為系統(tǒng)總體設(shè)計(jì)圖。

圖1 系統(tǒng)總體設(shè)計(jì)圖

2 終端設(shè)計(jì)方案

終端作為本系統(tǒng)至關(guān)重要的一部分，它是系統(tǒng)正常運(yùn)行的關(guān)鍵。終端位于每個(gè)物流車上，它負(fù)責(zé)采集物流車位置信息。終端的控制中心采用ST公司設(shè)計(jì)的一款具有低功耗特性的開發(fā)板STM32L476RGT6。GPS模塊采用 Air530，并將其天線置于車廂外。圖2為終端硬件框圖。

圖2 終端硬件框圖

3 為物流車遍歷貨源地設(shè)計(jì)行駛路線

3.1 用蟻群算法解旅行商（TSP）問題

蟻群算法（ant colony optimization，ACO）是由Marco Dorigo在1992年提出的[13]。它是一種自適應(yīng)算法，其動(dòng)態(tài)更新特性能很好解決TSP（traveling salesman problem）問題[14-16]。具體過程：首先可以把m個(gè)螞蟻隨機(jī)放置在n個(gè)貨源地，根據(jù)（1），（2）式算出狀態(tài)轉(zhuǎn)移函數(shù)從而確定行駛路線，將每條路徑上的起始信息素定為τij(0)，并且將遍歷過的貨源地裝入禁忌表tabuk中，將所有需要遍歷的貨源地放在一個(gè)集合C中，螞蟻在一次周游貨源地過程中，待訪問貨源地屬集合allowed。

v為揮發(fā)因子，Δτij(t)表示所有在一次遍歷過程中經(jīng)過i→j路徑的螞蟻釋放的信息素量，表示第k只螞蟻在一次遍歷中經(jīng)過i→j路徑釋放的信息素量，具體如（4）式所示。

Q為信息素素總量，Lk為第k只螞蟻循環(huán)一周走的路徑長度，隨著信息素矩陣迭代更新，逐漸收斂于最短路徑。

3.2 粒子群算法

1995年提出了粒子群算法(particle swarm optimization，PSO)[17]是一種基于群體智能理論的全局優(yōu)化方法[18-20]。他們通過觀察鳥群的飛行行為，以此受到啟發(fā)。通過搜索自身的最佳位置和群體最佳位置，使自身不斷向最佳位置靠攏，從而達(dá)到尋優(yōu)的目的。粒子一般有兩種狀態(tài)，運(yùn)動(dòng)速度和位置。PSO進(jìn)化規(guī)則如（5）所示。

其中：d表示粒子維度；xid表示第i個(gè)粒子位置；vid表示第i個(gè)粒子速度；pbest表示粒子自身最優(yōu)狀態(tài)；gbest表示整個(gè)粒子群最優(yōu)狀態(tài)；w表示粒子的慣性權(quán)重；c1,c2分別為學(xué)習(xí)因子；r1,r2均為[0,1]的隨機(jī)數(shù)。

4 算法改進(jìn)

在蟻群算法中起關(guān)鍵性因素的就是信息素，而在迭代的初期路徑上的信息素很少，這時(shí)在路徑尋優(yōu)的過程中信息素指導(dǎo)意義就不大，螞蟻在很大程度上還是在隨機(jī)摸索。為了凸顯粒子群算法的學(xué)習(xí)作用，采用粒子群算法優(yōu)化蟻群算法可以得到好的效果，將蟻群算法中的螞蟻也變成會(huì)學(xué)習(xí)的螞蟻，在迭代初期就給其加入一定量的信息素，避免路徑尋優(yōu)的盲目性。優(yōu)化思想如下：

（ⅰ）先取一個(gè)螞蟻數(shù)量較大的螞蟻總?cè)?，螞蟻?shù)量為M，將其分成n個(gè)數(shù)量均為m的螞蟻?zhàn)尤海ㄉ釛壎嘤嗟奈浵仯Ｃ總€(gè)螞蟻?zhàn)尤嚎闯闪Ｗ尤旱囊粋€(gè)粒子，這些粒子可記為δ1,δ2,……,δn。

（ⅱ）現(xiàn)隨機(jī)取一個(gè)螞蟻?zhàn)尤?，?duì)其使用基本蟻群算法，迭代X（此時(shí)X取10）代后得到最優(yōu)路徑?best1，以此類推最優(yōu)路徑分別 ?best2，?best3,…,?bestn再從中挑選出最優(yōu)路徑，記為?best。將每個(gè)螞蟻?zhàn)尤涸诼窂缴厢尫诺男畔⑺乜偭慷级镼，根據(jù)（6），（7）式分別算出子群最優(yōu)和總?cè)鹤顑?yōu)路徑片段上的信息素量。

（ⅲ）將每個(gè)子群最優(yōu)路徑上信息素取平均值

Δτ′ave(i→j)(t)是子群信息素量平均值。

（ⅳ）假設(shè)貨源地的數(shù)量為n，然后從螞蟻總?cè)褐须S機(jī)取數(shù)量為n只螞蟻進(jìn)行蟻群算法。將n只螞蟻隨機(jī)分配至個(gè)n貨源地，然后根據(jù)式（1）計(jì)算i→j的狀態(tài)概率選擇概率，根據(jù)概率大小選擇下一個(gè)訪問的貨源地。i→j路徑上信息素量計(jì)算公式

5 仿真與分析

5.1 實(shí)驗(yàn)中參數(shù)的確定

參數(shù)的選取對(duì)尋優(yōu)結(jié)果影響很大，在這里進(jìn)行合適參數(shù)選取?，F(xiàn)已將蟻群分成數(shù)量為n的小蟻群，即n個(gè)粒子，每個(gè)粒子是一組五維參數(shù)域，可設(shè)為p(α,β,v,c1,c2),分別對(duì)每組參數(shù)進(jìn)行基本蟻群算法，得出單個(gè)粒子的最優(yōu)pbest，和粒子群的最優(yōu)gbest，我們將粒子群最優(yōu)對(duì)應(yīng)的參數(shù)作為該改進(jìn)算法的參數(shù)。如表1所示為具體參數(shù)設(shè)置。

表1 參數(shù)設(shè)置

5.2 實(shí)際場景仿真

在物流車遍歷各個(gè)貨源地的過程中就需要為其設(shè)計(jì)出合適的路線，以使其在用時(shí)最短最高效的情況下遍歷各個(gè)貨源地使物流車達(dá)到滿載的狀態(tài)。本實(shí)驗(yàn)將對(duì)17個(gè)貨源地使用改進(jìn)后的蟻群算法進(jìn)行路線圖設(shè)計(jì)。改進(jìn)前后的最優(yōu)路徑如圖4，而改進(jìn)前后的全局最優(yōu)解隨迭代次數(shù)變化情況如圖5。改進(jìn)前后的路徑長度分別為882.45和874.80。

圖4 最優(yōu)路徑圖 (a)基本蟻群算法；(b)改進(jìn)后算法

5.3 仿真結(jié)果分析

一種算法在迭代次數(shù)足夠大時(shí)，倘若其沒有陷入局部最優(yōu)，它就能夠找到真實(shí)最優(yōu)解。因此實(shí)驗(yàn)中采用極端操作對(duì)改進(jìn)前后的蟻群算法在尋優(yōu)方面作對(duì)比。將兩種算法的迭代次數(shù)都設(shè)置為5 000次。由圖4可以看出基本蟻群算法顯然已經(jīng)陷入了局部最優(yōu)，在迭代足夠大的次數(shù)之后找到的最優(yōu)解和真實(shí)最優(yōu)解相比還是有差別的。從圖5可看出基本蟻群算法迭代2 300次左右找到其最優(yōu)解，而改進(jìn)后的蟻群算法在迭代500次就找到了其最優(yōu)解。所以不論從尋優(yōu)精度還是從收斂速度方面看，改進(jìn)后的蟻群算法都要遠(yuǎn)遠(yuǎn)優(yōu)于基本蟻群算法。

圖5 全局最優(yōu)解隨迭代次數(shù)變化圖

6 小結(jié)

本文提出了一種針對(duì)當(dāng)前公路物流車空載率高的解決辦法，對(duì)文章提及的一整套降低空載率的操作流程做了直觀清晰的闡釋。降低空載率的關(guān)鍵就是物流車在每次卸貨后都會(huì)遍歷貨源地把車裝滿，蟻群算法能很好的滿足這一要求，但是常規(guī)的蟻群算法有很大的局限性，在實(shí)際應(yīng)用中不能使物流始終按照最優(yōu)路線行駛，所以在前人的研究基礎(chǔ)上對(duì)該算法進(jìn)行了改進(jìn)，提出了一種思想，可以在蟻群算法初期給其提供一定量的信息素來避免其路線尋優(yōu)盲目性。文章涉及的物流調(diào)度思想在現(xiàn)實(shí)的物流運(yùn)輸中非常具有應(yīng)用價(jià)值。