基于3G無線通信技術的物流配送車輛優化調度問題

李海濤

（四川省郵電職業技術學院，四川 成都 610067）

1 引言

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

2 基于3G無線通信技術的物流配送監控系統整體結構設計

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

2.1 系統整體設計

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

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

圖1 基于3G無線通信的物流配送實時監控系統總體結構圖

物流配送車輛的實時調度作業中，配送車輛的實時定位是關鍵，物流配送中心要實時把握配送車輛的實時位置才能制定有效的調度措施。基于3G無線通信的車輛定位主要應用的技術包括3G無線通信技術、GPS技術、GIS技術等。對于物流配送車輛的實時定位，根據其功能以及對定位車輛定位處理的獨立性，主要包括GPS管理及定位模塊、GIS模塊以及3G通信模塊，通過3G通信模塊能夠將GPS和GIS模塊所采集到的配送車輛實時位置信息傳遞給移動控制平臺或者物流調度中心。基于3G的物流配送車輛定位功能框圖及物流配送車輛定位模塊總體拓撲結構如圖2和圖3所示。

圖3 基于3G無線通信的物流配送車輛定位模塊總體拓撲結構圖

基于3G的物流配送車輛定位模塊的主要功能包括配送車輛的定位和配送車輛的車載終端管理兩部分，具體包括車輛終端設備信息資料的處理、車載終端編號、駕駛員信息、3G通信地址管理、利用衛星定位技術實現車輛實時位置信息傳輸等。

3 物流配送中心車輛優化調度模型構建

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

基于上述假設，可構建帶軟時間窗約束的物流配送車輛調度優化模型如下：

目標函數：

其中：

約束條件

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

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

4 基于自適應遺傳算法的模型求解算法設計及實例分析

4.1 自適應遺傳算法求解流程設計

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

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

根據遺傳算法基本流程以及上述對交叉概率和變異概率的調整，針對上述物流配送中心車輛優化調度模型，應用自適應遺傳算法對模型進行求解的設計流程如圖4所示。

圖4 自適應遺傳算法流程示意圖

4.2 算例分析

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

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

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

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

5 結束語

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

表1 各客戶點位置坐標以及相關信息表

表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]馬衛民.第一方物流配送優化問題及其競爭策略田[D].西安:西安交通大學,2012.

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

[5]黨國英.基于GIS的物流配送車輛優化調度系統研究與實現[D].西安:西安理工大學,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]王亦鵬,王紅衛.GIS在敏捷運輸路徑選擇中的應用[J].計算機工程與應用,2012,(9):33-35.

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

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