李海濤

（四川省郵電職業(yè)技術(shù)學(xué)院，四川 成都 610067）

1 引言

經(jīng)濟全球化步伐的加快以及現(xiàn)代化信息技術(shù)的不斷發(fā)展進一步促進了專業(yè)化分工的深化，伴隨著這一趨勢的加強，物流活動也逐漸走向信息化、系統(tǒng)化和專業(yè)化。從上個世紀(jì)開始，逐漸涌現(xiàn)出了各種專業(yè)化的物流服務(wù)，形成了現(xiàn)代化的物流產(chǎn)業(yè)鏈。與此同時，現(xiàn)代信息技術(shù)也得到了長足的發(fā)展和提升，尤其是3G無線通信技術(shù)的出現(xiàn)，大大提高了社會生產(chǎn)力和物流服務(wù)水平，3G技術(shù)在物流領(lǐng)域的應(yīng)用尤其是在配送環(huán)節(jié)的引入，實現(xiàn)了配送環(huán)節(jié)的可視化管理，提高了配送作業(yè)的效率，大大降低了配送中心的作業(yè)成本。配送作業(yè)中的車輛調(diào)度問題一直以來都是該環(huán)節(jié)一個比較核心的問題，也是直接影響配送服務(wù)水平的核心環(huán)節(jié)，因此利用3G無線通信技術(shù)實現(xiàn)對配送車輛的優(yōu)化調(diào)度，對于提高優(yōu)化配送作業(yè)、進一步提高配送服務(wù)水平具有重要的現(xiàn)實意義。

2 基于3G無線通信技術(shù)的物流配送監(jiān)控系統(tǒng)整體結(jié)構(gòu)設(shè)計

3G無線網(wǎng)絡(luò)通信技術(shù)是一種以互聯(lián)網(wǎng)為核心，借助RFID無線射頻識別技術(shù)、紅外感應(yīng)技術(shù)、GPS全球定位系統(tǒng)和GIS地理信息系統(tǒng)以及GSM數(shù)字蜂窩移動通信系統(tǒng)等現(xiàn)代化通信技術(shù)，實現(xiàn)互聯(lián)網(wǎng)上的信息互聯(lián)的一種信息共享和交互技術(shù)，3G無線網(wǎng)絡(luò)技術(shù)具有傳輸速度快、帶寬大等特點。借助3G技術(shù)，有利于實現(xiàn)物流活動的智能化和一體化、社會操作。

2.1 系統(tǒng)整體設(shè)計

根據(jù)對現(xiàn)代物流業(yè)務(wù)流程的分析，結(jié)合3G無線技術(shù)的特點，基于3G無線通信技術(shù)的物流配送監(jiān)控系統(tǒng)整體結(jié)構(gòu)如圖1所示。其中，無線視頻監(jiān)控模塊主要借助現(xiàn)場前段視頻等設(shè)備對現(xiàn)場的作業(yè)信息進行采集，經(jīng)壓縮處理后利用3G網(wǎng)絡(luò)傳回至移動辦公平臺；在物流定位模塊中，利用配置在配送車輛上的車載終端并結(jié)合GPS和GIS技術(shù)實現(xiàn)對車輛實時位置信息的采集，并將信息回傳至移動辦公平臺；對于RFID射頻信息讀取模塊，主要利用RFID閱讀器采集儲存于RFID標(biāo)簽上的商品信息并利用3G無線網(wǎng)絡(luò)上傳至移動辦公平臺。通過移動辦公平臺，可以實現(xiàn)對物流信息和視頻信息的實時監(jiān)控。

2.2 基于3G無線通信的物流配送車輛定位實現(xiàn)

圖1 基于3G無線通信的物流配送實時監(jiān)控系統(tǒng)總體結(jié)構(gòu)圖

物流配送車輛的實時調(diào)度作業(yè)中，配送車輛的實時定位是關(guān)鍵，物流配送中心要實時把握配送車輛的實時位置才能制定有效的調(diào)度措施。基于3G無線通信的車輛定位主要應(yīng)用的技術(shù)包括3G無線通信技術(shù)、GPS技術(shù)、GIS技術(shù)等。對于物流配送車輛的實時定位，根據(jù)其功能以及對定位車輛定位處理的獨立性，主要包括GPS管理及定位模塊、GIS模塊以及3G通信模塊，通過3G通信模塊能夠?qū)PS和GIS模塊所采集到的配送車輛實時位置信息傳遞給移動控制平臺或者物流調(diào)度中心。基于3G的物流配送車輛定位功能框圖及物流配送車輛定位模塊總體拓撲結(jié)構(gòu)如圖2和圖3所示。

圖3 基于3G無線通信的物流配送車輛定位模塊總體拓撲結(jié)構(gòu)圖

基于3G的物流配送車輛定位模塊的主要功能包括配送車輛的定位和配送車輛的車載終端管理兩部分，具體包括車輛終端設(shè)備信息資料的處理、車載終端編號、駕駛員信息、3G通信地址管理、利用衛(wèi)星定位技術(shù)實現(xiàn)車輛實時位置信息傳輸?shù)取?/p>

3 物流配送中心車輛優(yōu)化調(diào)度模型構(gòu)建

目前國內(nèi)關(guān)于配送車輛調(diào)度問題的研究主要集中于單配送中心、多確定位置客戶以及單車型非滿載問題，且客戶對于配送服務(wù)具有明確的時間要求，一般為軟時間窗問題，即如果配送車輛未能在客戶規(guī)定時間范圍內(nèi)送達，則客戶將對配送中心采取一定的懲罰措施，基于此，本文構(gòu)建帶軟時間窗約束的物流配送車輛優(yōu)化調(diào)度模型并引入交通流量因素對車輛調(diào)度決策的影響，為了便于模型構(gòu)建和求解，首先對模型作如下假設(shè)：（1）假設(shè)配送中心擁有車輛數(shù)足夠多，能夠滿足配送高峰時的需求；（2）配送物資可混裝；（3）客戶需求點以及各節(jié)點裝卸效率已知；（4）各客戶點對配送時間要求以及單位時間懲罰費用已知；（5）配送區(qū)域路網(wǎng)路段長度已知；（6）路網(wǎng)中各個路段的最小出行速度以及自由流速度已知。

基于上述假設(shè)，可構(gòu)建帶軟時間窗約束的物流配送車輛調(diào)度優(yōu)化模型如下：

目標(biāo)函數(shù)：

其中：

約束條件

模型相關(guān)參數(shù)解釋如下：N表示某時段范圍內(nèi)需要提供配送服務(wù)的顧客數(shù)量；Nl表示某時段范圍內(nèi)由車輛l提供配送服務(wù)的顧客數(shù)量；Rl表示車輛l的配送路徑集合，Rl={rl,k|rl,k∈{1,2,...,N},k=1,2,...,Nl}；rl,k表示車輛l服務(wù)的第k客戶；cl,d表示車輛l執(zhí)行配送作業(yè)的單位時間操作成本；La表示路網(wǎng)中路段a的長度；ra(t)表示某時刻t路段a上的車流速度；xa(t)表示某時刻t路段a上的車輛承載量；va表示路網(wǎng)中路段a的平均離開率；ka(t)表示某時刻t路段a上的車流密度；分別表示路網(wǎng)中路段a上車輛的最小出行速度和自由流出行速度；ka,jam表示路網(wǎng)中路段a上的阻塞密度；cd,rl,k表示如果為客戶rl,k提供配送服務(wù)出現(xiàn)延期所產(chǎn)生的單位時間懲罰費用；ce,rl,k表示客戶rl,k提供配送服務(wù)提前到達所產(chǎn)生的單位時間等待費用；trl,k表示車輛l到達客戶rl,k開始服務(wù)的時間；分別表示客戶rl,k要求的配送服務(wù)開始的最晚和最早時間；wrl,k表示客戶rl,k需要的配送作業(yè)量；ηrl,k表示在客戶rl,k處裝卸作業(yè)的效率；表示車輛在客戶點rl,k處的作業(yè)時間；ql表示車輛l的載重量；

上述模型中，Cf(trl,0,rl,k)為系統(tǒng)總成本，trl,0表示車輛l離開配送中心的時間，式（1）表示車輛l在執(zhí)行配送作業(yè)時不能超載；式（2）表示車輛l執(zhí)行配送作業(yè)時最大客戶訪問量不能超過客戶總數(shù)；Nl=0表示車輛l未執(zhí)行配送作業(yè)；式（3）表示所有客戶都要被提供配送服務(wù)；式（4）表示每個客戶均只能被一輛車提供配送服務(wù)；式（5）和式（6）為車輛閉回路約束，表示車輛執(zhí)行完配送作業(yè)以后需要返回配送中心；式（7）為時間窗約束；式（8）表示車輛到達當(dāng)前客戶的時間=車輛到達上一客戶開始服務(wù)的時間+車輛在上一客戶的卸貨時間+車輛從上一客戶到達當(dāng)前客戶的運輸時間+車輛在上一客戶提前到達的等待時間；式（9）為路段流量約束。

4 基于自適應(yīng)遺傳算法的模型求解算法設(shè)計及實例分析

4.1 自適應(yīng)遺傳算法求解流程設(shè)計

在求解諸如上述非線性規(guī)劃問題時，常用啟發(fā)式算法對其進行求解。在實際應(yīng)用中，傳統(tǒng)的遺傳算法步驟容易使最優(yōu)解的搜索過程陷入早熟，從而使得到的最優(yōu)解并非全局最優(yōu)，為避免此現(xiàn)象，本文采用自適應(yīng)遺傳算法對上述問題進行求解。自適應(yīng)遺傳算法在進行最優(yōu)解搜索過程中，其交叉率和變異率設(shè)置為隨染色體適應(yīng)度值變化而自適應(yīng)變化，見式（10）和式（11）。

f`表示在進行染色體交叉操作時染色體適應(yīng)度值的最大值，f`=max{f1,f2}；favg表示種群所有染色體的平均適應(yīng)度值；f表示需要變異的染色體的適應(yīng)度值；fmax表示種群所有染色體中適應(yīng)度的最大值；k1,k3為交叉概率調(diào)整參數(shù)；k2,k4為變異概率調(diào)整參數(shù)，k1,k2,k3,k4∈(0,1)。

根據(jù)遺傳算法基本流程以及上述對交叉概率和變異概率的調(diào)整，針對上述物流配送中心車輛優(yōu)化調(diào)度模型，應(yīng)用自適應(yīng)遺傳算法對模型進行求解的設(shè)計流程如圖4所示。

圖4 自適應(yīng)遺傳算法流程示意圖

4.2 算例分析

以甘肅省蘭州市某配送中心為例，該配送中心坐標(biāo)為（33,77），單位為km，該配送中心服務(wù)區(qū)域范圍內(nèi)共有20個客戶，配送中心為客戶提供配送服務(wù)，每輛配送車輛的最大載貨量為100箱，配送車輛在執(zhí)行配送作業(yè)時每單位行駛里程配送成本為1元/km，配送車輛車速為1km/min，配送過程中車輛等待費用為0.1元/min。區(qū)域內(nèi)各客戶點位置以及相關(guān)信息見表1。借助GPS和GIS實時傳回的車輛位置信息，利用Arcgis軟件對該地區(qū)路網(wǎng)進行處理，可得到城關(guān)區(qū)路網(wǎng)各路段長度及路段節(jié)點坐標(biāo)，并標(biāo)出配送中心位置、客戶點位置及各配送車輛實時的位置坐標(biāo)。

由于本文模型考慮對配送車輛的實時調(diào)度，在實際執(zhí)行配送作業(yè)時，主要根據(jù)GPS全球定位系統(tǒng)和GIS地理信息系統(tǒng)所提供的各時段實時道路交通流信息，選取某時段作為研究對象，將背景中相關(guān)參數(shù)以及該時段配送車輛運行參數(shù)輸入模型并應(yīng)用自適應(yīng)遺傳算法進行求解，求解結(jié)果見表2。

該配送方案下，配送中心總配送總成本為：Cf=12035（元）。

考慮到道路交通流信息變化較快，上述方案僅為該時段配送中心車輛調(diào)度的最佳方案，隨著時間的不斷推移，3G系統(tǒng)將不斷反饋新的交通流信息，在這種情況下，配送中心應(yīng)不斷更新配送方案并通過GSM數(shù)字蜂窩移動通信系統(tǒng)和配送車輛之間的實時調(diào)度指令，實現(xiàn)總配送成本最低。

5 結(jié)束語

隨著現(xiàn)代信息技術(shù)的不斷發(fā)展和進步，3G無線網(wǎng)絡(luò)通信技術(shù)也得到了快速的發(fā)展和延伸，逐漸成為通信行業(yè)的支撐技術(shù)，憑借移動性和高帶寬性等優(yōu)勢，3G無線網(wǎng)絡(luò)通信技術(shù)在越來越多的行業(yè)里得到了廣泛的應(yīng)用。作為現(xiàn)代物流業(yè)，大量現(xiàn)代通信技術(shù)的引入進一步提高了現(xiàn)代物流信息化、商品化和專業(yè)化的程度，本文主要從物流配送環(huán)節(jié)的車輛調(diào)度優(yōu)化問題入手，借助3G無線通信網(wǎng)絡(luò)，實現(xiàn)了對配送車輛的可視化管理和實時調(diào)度，并構(gòu)建了帶時間窗約束的配送中心配送車輛實時調(diào)度優(yōu)化模型，最后應(yīng)用某實例對模型進行了驗證。

表1 各客戶點位置坐標(biāo)以及相關(guān)信息表

表2 某時段配送中心配送方案

[1]Dantzig G,Ramser J.The truck dispatching problem[J].Management Science,1999,(6):80-91.

[2]Bordin L.Classification in Vehicle Routing and Scheduling[J].Networks,1995,11:71-88.

[3]馬衛(wèi)民.第一方物流配送優(yōu)化問題及其競爭策略田[D].西安:西安交通大學(xué),2012.

[4]馮萍.退火遺傳算法在運輸路線規(guī)劃中的應(yīng)用[D].西安:西安交通大學(xué),2011.

[5]黨國英.基于GIS的物流配送車輛優(yōu)化調(diào)度系統(tǒng)研究與實現(xiàn)[D].西安:西安理工大學(xué),2009.

[6]Demenulemeester L,Laporte G,Loueaux F V.Optimal sequencing of skip collections and deliveries[J].Journal of the Operational Research Society,1997,(1):57-64.

[7]王亦鵬,王紅衛(wèi).GIS在敏捷運輸路徑選擇中的應(yīng)用[J].計算機工程與應(yīng)用,2012,(9):33-35.

[8]李強,黃莎白.GIS環(huán)境下的最佳路徑規(guī)劃[J].信息與控制,2010,29(1):45-47.

[9]陸振波,黃衛(wèi).城市公交問路系統(tǒng)—GIS在城市公交管理中的應(yīng)用[J].公路交通科技,2011,18(5):23-25.