配送車輛優化調度系統隨機數產生及仿真方法研究

摘要：隨著經濟發展，現代物流快速發展，現已然成為企業的第三利潤源泉。因此，其在這以環節降低成本、增大效益、提高速度變得日益重要。配送作為物流中的重要環節，其效率得到越來越多的關注，在配送車輛優化調度模型、算法的研究豐富的同時，關于該方面系統仿真的研究卻比較缺乏。本文旨在探討VSP問題的模型和算法，針對具有時間約束的整數規劃模型給出計算機仿真參數生成方案，并進一步給出仿真系統的步驟進而設計思路。

關鍵詞：配送車輛優化調度 VSP 時間窗 整數規劃模型 隨機數生成 計算機仿真

一、引言

隨著我國經濟的發展，現代物流已成為社會和企業的生產、供應是否能夠高效運作的關鍵。配送是將貨物從物流結點送達收貨人的過程，是物流的一個重要環節，直接與消費者或客戶溝通連接。配送需要按照客戶要求，按照需求貨物的種類、數量、時間等方面要求進行運送，是“配”和“送”的有機結合。配送的線路、車輛規劃是否合理將很大程度上影響配送的成本、效益、速度和服務質量。當前，物流網絡覆蓋范圍較大、客戶較多、時間要求精確對于配送提出了更高的要求，對于及時性、準確性更加苛刻。因此，采用科學、合理、高效的方法確定配送線路和車輛調度計劃，變得至關重要。

國內外許多研究對于配送線路安排問題（VRP）和配送車輛優化調度問題（VSP）都有了深入的探討，建立了相關的模型和算法。但將模型與日常配送系統的運作相結合更為關鍵，在構建計算機配送優化系統前，需要對于模型和系統進行試驗、確認，以保證系統模型對解決目標問題的匹配性和高效性。因此，需要建立一個合理的計算機模擬環境對系統模型進行驗證和確認，以及對系統未來運行狀況的模擬、評估。

物流配送車輛路徑問題的仿真研究，即是將對解決車輛線路安排、車輛調度問題與計算機系統仿真技術相結合，達到將系統模型與現實需求目標相匹配的目的。

本文將對物流配送規劃模型加以討論，并且以具有時間窗的整數規劃模型為例對其中模型的參數的計算機仿真生成和系統仿真方法進行針對性的探討。

二、配送車輛優化調度問題研究

（一）配送車輛優化調度問題研究概況

一般認為，不考慮時間要求，僅根據空間安排線路時稱為VRP（Vehicle Routing Problem）問題，當引入時間等約束時成為VSP（Vehicle Scheduling Problem）問題。由于Scheduling比Routing范圍大，因此一般統稱為車輛優化調度問題VSP。

VSP的算法國內外有大量的研究，主要分為精確算法和啟發式算法兩類。因為VSP問題是NP-困難問題，采用精確算法如：分支定界法、割平面法等運籌學算法時計算量隨需規劃的規模成指數增長，在現實中無法實現或很不經濟。專家們致力于研究近似的得出較優解得算法，即啟發式算法。該類研究成果很多主要包括：

1、構造算法（Constructive Algorithm）

包括：節約法（C-W）、插入法等

2、兩階段算法（Two Phase Algorithm）

包括：先路徑后分組法、先分組后路徑法等

3、亞啟發式算法（Met heuristics Algorithm）

包括：退火算法、遺傳算法和神經網絡算法等

本文重點討論系統仿真方法，對各模型算法不做詳細的討論，僅以具有時間窗的整數規劃模型為例針對性的給出系統仿真隨機數產生方法及仿真方法。其他模型及算法可根據其原理進行推廣。

（二）配送車輛優化調度問題的模型建立

建立的數學模型一般有整數規劃模型和集合劃分模型兩種，這里主要討論整數規劃模型。為了具有一定代表性和適用性，因此建立帶有時間窗的整數規劃模型為范例：

目標：車輛總運輸費用最低；

假設：使用的車輛全部相同，搬運作業時間相同，不能早于或晚于預約時間一定時間，搬運成本不計入運輸費用

增加采用硬時間窗約束，建立模型如下：

s.t.

其中：

N——區域中需求點集合，N={0，1，2，……，n}；

——需求點i需求量；

——車輛k服務的需求點集；

——車輛k的容量；

——i到j的單位運輸費用；

——需求點i預約最早時間；

——需求點i預約最晚時間；

——車輛k抵達需求點i的時刻；

——由點i到j之的間隔時間，包括行程時間和搬運作業時間，即：，為ij間距，v為車速（取校內限速）；

M——較大的正整數；

三、配送車輛優化調度模型的數據仿真

（一）仿真隨機數的生成

為了測試配送車輛優化調度模型的合理性和系統整體性能，需要進行計算機仿真。此時由于沒有真實的預約信息和用戶信息，需要對用戶的預約細節信息進行計算機生成，應采用隨機數產生的方法產生預約的用戶編號（位置）、每個用戶的預約量、預約時間，以便對模型進行參數的輸入和賦值，即對關鍵參數：、，進行仿真數據生成。

由于沒有系統中沒有實際的訂單，需要模擬預約生成的情況，而且客戶的分布、預約數量和時間要有一定得合理性，即符合系統預測的情況或歷史數據。鑒于本系統沒有歷史數據，只有預測的用戶分布和預約服務的情況，客戶預約情況都服從由調查結果和預測值得出的一定概率分布。

從理論上，服從某一分布的隨機數都可以通過對IID[0，1]均勻分布的隨機數進行適當的轉換得到，因此正確生成[0，1]上的均勻分布的隨機數就想得尤其重要。但計算機無法生成完全隨機的數字，需要借用一定方法進行隨機數的生成，方法大致可以分為三類：

1、專用的隨機數表

用已制作好的隨機數表進行提取。但由于本系統需要的隨機數量較大，且需要把隨機數表輸入系統，將占用大量的內存，所以不采用該方法。

2、物理方法

利用電子管、放射粒子計數器或晶體管噪聲發生器等物理隨機數發生器直接產生。考慮經濟性和延展性，本系統不可能采用該方法。

3、數學方法

應用數學公式在計算機上產生。該方法可以實現隨機數的產生和檢驗，產生速度快、占內存少、對仿真問題可進行復算。因此仿真采用該方法。

由于利用數學方法產生的不是真正的隨機數，但具有均勻性和獨立性，類似于真正的隨機數序列，稱作“偽隨機數”。隨機數必須滿足下列要求：

（1）分布上的均勻性；

（2）統計上的獨立性

（3）產生速度足夠快

（4）產生隨機數可以復現

采用混合線性同余法（LCG），按下列公式計算隨機數：

其中，C、D為常數；為種子；M為模。

由種子開始，可計算整數序列：，再依次算出，得到[0，1]隨機數列U。因為M只能取有限數，隨機數將會出現周期性重復，且周期，與參數C，M的取值相關。這里取正整數：。當滿足：

（1）D與M互質；

（2）若k是一個能整除M的質數，則k能整除C-1；

（3）若M能被4整除，C-1也能被4整除。

設定預計的預約數n，即為總的隨機數產生量。

（二）客戶預約信息的生成

以某物流配送中心車輛系統為例。系統需要接收客戶的訂單，根據客戶的訂貨量、預約時間、位置等信息合理安排車輛的配送路線及數量。為了能夠進行系統仿真，對實際的運行進行預測和系統評估，需要在沒有實際數據的情況下，生成符合客戶特征的數據，輸入系統模型（參見2.2），從而進行計算機模擬。以下討論預約客戶編號、預約服務時間、預約量幾個重要參數隨機數生成方法。

1、預約客戶編號的生成

客戶編號為系統在客戶注冊時按一定編碼規則生成的整數列，屬于離散分布的隨機數，采用表搜索法對已產生的[0，1]隨機數列U進行轉化。設總客戶數為m，各用戶預約的概率均等，則每個客戶k預約概率為，進而累計概率：

根據進行搜索，取的最小值k作為對應的序號，從而給出客戶的編號。

若有歷史數據或根據預測客戶各個類別預約的概率有所不同，調整以上的計算方法，根據數據分布的特征確定概率的分布，從而得到相對應的累計概率，再用同樣的方法進行計算得編號。

2、預約服務時間的生成

假定能夠提供服務的時間為每天的9：00-17：00（包括周末），則預約服務日期跨度為4周（期末時段），即連續的28天。則每個（即每個預約用戶）對應的服務時間隨機數需要確定日期d和時刻t兩個參數。設預約的概率對日期和時刻都服從一定得分布，而該分布由調查預測或歷史數據得到，則此時對于日期d，隨機數為離散的經驗分布，對于t為連續的經驗分布。此時服務時間的隨機數由生成分為兩個階段：

首先，生成日期d。仍然采用表搜索法（方法同上）。根據預測或歷史數據求得、，進而由，得到日期d；

令，

而后，生成時刻t。再次應用表搜索法。根據預測或歷史數據求得，進而由，得到時刻t；

此時，對應的特定客戶被賦予了一個特定預約日期和時刻，即系統應該提供服務的時間。再根據系統模型的規定，給出（客戶i預約最早時間），（客戶i預約最晚時間）。

對于模型中的參數，考慮到服務質量最高，應使抵達時間等于預約時間。于是將第k輛車服務的第一個客戶的服務日期d和時間t賦值。其他的可根據依次求得。

3、預約量的生成

由于預約量也是一個可以由調查預測或歷史統計得到的數據，進而可以得到預約量的經驗分布。因此可以同樣采取上述的方法對應每一個進行客戶預約量的生成。

若客戶的地址在本系統中為注冊的基本信息，則客戶編號與地址為一一對應關系，編號生成的同時也就完成了對于客戶地理位置的生成。

針對路線生成模型而言，需要對于每個需求點的需求量這一參數進行賦值。每個需求點包含若干個用戶，因此這時對于需求點j則有需求量：

其中，為客戶i的預約量，為需求點j所包含的客戶i的集合，j為需求點編號。

四、配送車輛優化調度問題的計算機仿真實現

物流系統是一個復雜的離散事件動態系統，具有復雜性、遞階性、并發性、隨機性等特點。而計算機面向對象的技術具有分解、抽象、遞階等特性，較適合于上述問題的求解和優化。

目前，配送車輛優化調度系統仿真方面的研究成果較少。Taniguchi E， T Yamada， T Hosokawa提出了有時間窗約束的車輛路徑問題和動態交通仿真的集成模型，對于整數模型進行了進一步的拓展，并針對現實仿真需要加以改進。模型有兩個子模型，一是有時間窗的車輛路徑問題模型，二是在道路網絡中集/送貨車輛的動態交通仿真模型。

（一）系統仿真的步驟

一般而言，系統仿真需要經過問題描述和系統定義、建立系統模型、收集和整理數據資料、建立仿真模型及編制程序、調試程序及確認模型、試驗設計、計算機仿真運行、輸出結果分析、建立文檔、實施仿真決策等步驟，如圖4.1所示：

圖4.1 系統仿真步驟

其中，需要特別注意數據和資料得出的需求預測的客觀性和代表性。進而，該預測應該能夠體現客戶的類型、數量，需求的時空分布等具體信息，并能用一定的概率分布進行表示，從而為系統仿真的參數生成提供有效參考。

在模型確認階段，可以依據Naylor和Finger的“三步法”從：直觀考察模型有效性，檢驗模型的假設、模型的輸出數據與實際數據的比較，三個方面來進行。其中，若仿真目標為系統預測時，當有歷史數據可以將輸出數據與之比較，當沒有歷史數據時則應確認與預測的一致性和相關系統進行類比分析，此時仿真重點在前兩步。

（二）系統仿真優化的設計思路

仿真優化的基本單元包括仿真器和優化器。優化過程即為仿真器和優化器相互作用協調，不斷交互產生最優結果的過程（兩者關系如圖4.2）。因此，配送車輛優化調度優化系統主要包括兩個模塊的設計：仿真模塊、優化模塊。前者的主要功能為對模型參數的仿真生成、系統模型運行、結果的輸出等，后者包括對于問題分析、結果的分析、系統模型評價與決策和改進策略等。這一過程實質上即為，仿真步驟中的模型確認和調試過程的具體化。

圖4.2 系統仿真模塊關系

五、總結

本文首先探討計算機仿真在物流配送系統優化中的必要性，再對物流配送車輛優化調度理論模型、算法的研究進行闡述，結合計算機仿真的方法原理，對VSP問題仿真參數生成進行討論。以具有時間約束的整數規劃模型為例建立模型，并針對模型，考慮了對客戶調查預測和歷史數據的情況，對其離散分布的數據信息給出計算機仿真關鍵參數的生成方法。由此，解決了在虛擬條件下，與實際預測或歷史相匹配的模型參數輸入問題，并進一步給出了整體仿真系統的設計步驟和思路。為物流車輛優化調度系統仿真的一個關鍵環節提出具體的解決方案和對于整體仿真系統的理論描述。

參考文獻：

[1]現代物流導論 孫有望

[2]現代物流管理技術——建模理論及算法設計 孫焰

[3]交通運輸系統規劃 任科社

[4]運輸與物流系統仿真 徐瑞華

[5]計算機基礎課實驗教學的實踐與探索 侯整風，王麗華

[6]物流中心貨物調度分配的最優規劃及算法研究 陳向陽

[7]Taniguchi E，T Yamada，T Hosokawa.Dynamic Traffic Simulation with Optimal Truck Routing and Scheduling，Transportation and Traffic Theory[C] //Abbreviated Presentation Sessions of the 14th International Symposium on Transportation and Traffic Theo ry. Jerusalem，1999:419- 439

[8]物流配送系統中車輛路徑問題仿真優化及其進展 李永先，胡祥培，熊英

[9]物流配送管理教學系統分析與設計 常瀾瀟，曾傳華