聯(lián)合配送車輛調(diào)度及算法實現(xiàn)

李偉+鄧紅濤+陳紅莉+戴建國

摘 要：現(xiàn)代物流業(yè)配送模式由單一配送向聯(lián)合配送、動態(tài)配送、大規(guī)模跨區(qū)域配送轉(zhuǎn)化。針對這一變化，提出了一種多維協(xié)同條件下的大規(guī)模車輛調(diào)度方法，構(gòu)建面向多重約束條件的車輛調(diào)度數(shù)學(xué)模型，研究了針對大規(guī)模協(xié)同配送的車輛調(diào)度算法，以達到物流調(diào)度實時化、高效化和智能化目的。

關(guān)鍵詞：車輛調(diào)度；現(xiàn)代物流；聯(lián)合配送；調(diào)度算法

DOIDOI：10.11907/rjdk.162229

中圖分類號：TP319

文獻標識碼：A文章編號：1672-7800（2016）012-0107-02

0 引言

現(xiàn)代物流業(yè)著眼于供應(yīng)鏈體系發(fā)展，帶動新型工業(yè)化、農(nóng)業(yè)產(chǎn)業(yè)化和流通現(xiàn)代化，逐漸成為國民經(jīng)濟的基礎(chǔ)產(chǎn)業(yè)。各種物流信息應(yīng)用技術(shù)如GPS、北斗導(dǎo)航等技術(shù)已廣泛應(yīng)用于各種物流活動過程。同時，隨著物聯(lián)網(wǎng)技術(shù)和電子商務(wù)的快速發(fā)展，傳統(tǒng)單一的物流模式逐漸被聯(lián)合配送、動態(tài)配送和大規(guī)?？鐓^(qū)域配送取代，傳統(tǒng)單一的車輛調(diào)度模式已經(jīng)難以支持現(xiàn)代物流業(yè)配送需求。

現(xiàn)實物流調(diào)度中需求各異，涉及的車輛調(diào)度因素眾多，甚至相互沖突，在客戶滿意度和調(diào)度成本上需要相互平衡，特別是隨著大數(shù)據(jù)計算、物聯(lián)網(wǎng)技術(shù)、智能通訊以及電子商務(wù)評價模式的出現(xiàn)，車輛調(diào)度需要綜合考慮車輛、客戶、貨源、路況、用戶評價等各種因素[1-2]。

鑒于此，本文從系統(tǒng)工程角度分析資源、車輛、客戶需求，對跨區(qū)域配送中關(guān)鍵要素進行分析，研究構(gòu)建基于聯(lián)合配送的調(diào)度模式，構(gòu)建面向多方用戶需求的需求池和調(diào)度池，對面向不同約束的調(diào)度需求以及聯(lián)合配送車輛調(diào)度進行建模并設(shè)計相關(guān)算法，以實現(xiàn)在多約束條件下的最優(yōu)調(diào)度算法。

1 研究現(xiàn)狀

1959年由Dantzig和Ramser首次提出[3]的調(diào)度問題來自于公路交通運輸管理。隨著電子商務(wù)和信息技術(shù)的發(fā)展，傳統(tǒng)大批量、少批次的物流模式已經(jīng)不能適應(yīng)復(fù)雜多變的調(diào)度需求，小批量、多批次、客戶需求的動態(tài)性使得配送區(qū)域更加模糊，區(qū)域間交叉配送和聯(lián)合配送現(xiàn)象日趨頻繁[4]。Hariklis和Powell[5]首次提出開放式車輛調(diào)度問題，Arantilis[6]對鮮肉配送的車輛調(diào)度問題進行了研究；有學(xué)者采用混合遺傳算法和禁忌算法對開放式車輛調(diào)度問題模型進行求解，提出了開放式車輛調(diào)度問題最優(yōu)解的檢驗方式；李延暉等研究了沿途多點的開放式車輛調(diào)度問題，并設(shè)計帶有補貨控制因子的蟻群算法進行求解[7，8]。上述文獻主要是對需求穩(wěn)定的開放式車輛調(diào)度問題展開研究，但對優(yōu)化目標選擇、多配送中心、車輛共享管理等核心問題沒有詳細分析。因此，本文針對國內(nèi)物流配送現(xiàn)狀，從節(jié)約成本角度出發(fā)，提出將配送資源、客戶轉(zhuǎn)化為資源池概念，通過充分聯(lián)合，轉(zhuǎn)化為聯(lián)合配送的車輛調(diào)度問題。

2 聯(lián)合配送調(diào)度算法

2.1 聯(lián)合配送含義

聯(lián)合配送指共同配送、協(xié)同配送。在一個規(guī)?；膮^(qū)域內(nèi)存在多個配送中心、多批次的貨物資源，為了降低物流成本，打破單個車輛物流調(diào)度的局限性，多公司合作實現(xiàn)大范圍的合理化配送，通過集中配送來提高物流使用效率，進而提高配送車輛利用率，達到共享物力資源和車輛資源效果。聯(lián)合配送還存在分區(qū)配送和跨區(qū)域配送，區(qū)別在于配送中心是否聯(lián)合響應(yīng)。

以PN代表配送中心，UN代表用戶需求，分區(qū)配送策略建立“1-N”模式，一個配送中心負責(zé)所在區(qū)域內(nèi)的所有用戶需求，各配送出于利益關(guān)系互不關(guān)聯(lián)，調(diào)度車輛負責(zé)所在區(qū)域的用戶需求，區(qū)域配送模式如圖1所示。在聯(lián)合配送模式中，不同配送中心可根據(jù)用戶需求相互調(diào)度車輛，實現(xiàn)跨區(qū)域內(nèi)車輛、資源協(xié)同和共享，配送中心可從整個區(qū)域范圍內(nèi)考慮車輛調(diào)度問題，解決了物流能力不平衡問題，滿足了小批量、多批次的物流需求，節(jié)約了成本，這種模式使得更大規(guī)模的區(qū)域配送調(diào)度成為可能。聯(lián)合配送模式如圖2所示。

2.2 聯(lián)合配送業(yè)務(wù)需求分析

聯(lián)合配送過程中需要綜合考慮多項業(yè)務(wù)需求因素，這些因素包括配送中心基礎(chǔ)信息、車輛信息、貨物信息、位置信息等，由此產(chǎn)生幾大功能需求，包括車輛管理、貨物管理、調(diào)度管理、地圖可視化、基礎(chǔ)數(shù)據(jù)管理等功能。因此，物流調(diào)度系統(tǒng)必須根據(jù)業(yè)務(wù)需求制定科學(xué)合理的功能需求，利用調(diào)度算法進行快速優(yōu)化，產(chǎn)生實時調(diào)度計劃，以提高聯(lián)合物流調(diào)度系統(tǒng)效率和效益。聯(lián)合配送算法必須將問題進行分解及簡化，并抽象出相應(yīng)的數(shù)學(xué)模型，再通過各種優(yōu)化算法運算出最優(yōu)解。算法首先需要根據(jù)初始化資源狀態(tài)統(tǒng)計出車輛到貨物的最短距離，通過區(qū)域優(yōu)化算法，計算出為每個客戶提供配送服務(wù)所屬的配送區(qū)域；然后系統(tǒng)將客戶需求整合以確定各配送中心要服務(wù)的客戶。因此，聯(lián)合配送調(diào)度問題分解為各個獨立的單區(qū)域配送問題。分解后的各個獨立問題可以綜合運用遺傳算法求解，最終求出最優(yōu)解和車輛配送路線。

2.3 聯(lián)合配送算法設(shè)計

車輛調(diào)度算法中最早的遺傳算法由Holland提出，其核心思想是在任意一個群中優(yōu)秀個體都會出現(xiàn)指數(shù)增長的方向，其中優(yōu)化對象可以是連續(xù)型的，使用隨機選擇策略經(jīng)過交叉繁殖和變異等遺傳行為，直至算法實現(xiàn)收斂。聯(lián)合調(diào)度算法需要預(yù)估車輛的配送條件，資源約束條件包括貨物資源、車輛資源、需求資源等，車輛調(diào)度中的資源約束條件越多，車輛調(diào)度線路的安排就越復(fù)雜，每臺車輛在資源約束下的任務(wù)量就越小，同時車輛跨區(qū)域調(diào)度越頻繁，配送中心整體成本就越低。

為了實現(xiàn)車輛調(diào)度最優(yōu)化，根據(jù)配送網(wǎng)絡(luò)中客戶的需求量建立資源池，預(yù)先估計完成調(diào)度所需要的車輛數(shù)為m，建立模型如下：

其中Qmaxr表示區(qū)域范圍內(nèi)可調(diào)度車輛最大需求量，Qmaxr表示區(qū)域范圍內(nèi)車輛最小需求量，0<<1表示資源約束條件，資源需求越多約束條件越多。聯(lián)合配送信息發(fā)生在配送計劃的執(zhí)行過程中，算法設(shè)計“資源池建立+區(qū)域配送階段+聯(lián)合配送階段”的三階段求解策略，對聯(lián)合配送模型進行求解，算法設(shè)計思想如下：

第一階段：根據(jù)現(xiàn)有配送中心基礎(chǔ)信息、車輛信息、貨物信息、位置信息等建立調(diào)度資源池，并生成現(xiàn)有靜態(tài)狀態(tài)；第二階段：根據(jù)已知需求信息制定初始優(yōu)化階段的調(diào)度計劃。該階段利用遺傳算法進行全局優(yōu)化，產(chǎn)生初始調(diào)度計劃；第三階段：根據(jù)需求信息變化情況優(yōu)化。該階段將在執(zhí)行第二階段制定的配送計劃過程中，通過需求信息變化更新資源池。在資源池變動情況下分析新需求，利用遺傳算法快速優(yōu)化，產(chǎn)生實時調(diào)度計劃。具體流程如圖3所示。

3 結(jié)語

聯(lián)合車輛調(diào)度及路線的優(yōu)化決策涉及眾多因素，比如配送中心位置、客戶分布及需求、成本因素、時間因素等。本文針對跨區(qū)域多配送中心聯(lián)合配送車輛調(diào)度問題展開研究，分析了現(xiàn)階段聯(lián)合配送調(diào)度算法現(xiàn)狀，對現(xiàn)有遺傳算法進行了改進，建立了“資源池建立+區(qū)域配送階段+聯(lián)合配送階段”的三階段求解方案，以實現(xiàn)車輛調(diào)度優(yōu)化策略，實現(xiàn)物流調(diào)度的實時化、高效化和智能化，為物流工作人員優(yōu)化車輛調(diào)度業(yè)務(wù)提供技術(shù)支持。

參考文獻：

[1] 劉云忠，宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學(xué)報，2005，19（1）：124-130.

[2] 張景玲，趙燕偉.多車型動態(tài)需求車輛路徑問題建模及優(yōu)化[J].計算機集成制造系統(tǒng)，2010，16（3）：543-550.

[3] DANTZIG G B， RAMSER J H. The truck dispatching problem[J]. Management Science，1959，4（6）：80-91.

[4] 葛顯龍.面向云配送模式的車輛調(diào)度問題及算法研究[D].重慶：重慶大學(xué)，2011.

[5] LI SARIKLIS D， POWELL S. A heuristic method for the open vehicle routing problem[J]. Journal ofthe Operational Research Society，2000，51（5）：564-573.

[6] TARANTILIS C D， KIRANOUDIS C T. Distribution of fresh meat[J]. Journal of Food Engineering，2002，51（1）：85-91.

[7] 陶胤強，?；菝?帶時間窗的多車型多費用車輛路徑問題的模型和算法[J].交通運輸系統(tǒng)工程與信息，2008，8（1）：113-117.

[8] 霍佳震，王新.基于約束規(guī)劃求解車輛調(diào)度問題[J].物流技術(shù)，2005（9）：110-112.

[9] 施朝春，王旭，葛顯龍.帶有時間窗的多配送中心車輛調(diào)度問題研究[J].計算機工程與應(yīng)用，2009，45（34）：21-24.

（責(zé)任編輯：杜能鋼）