面向任務(wù)的物資供應(yīng)路徑優(yōu)化決策建模研究

艾云平

(安徽外國語學(xué)院 國際商務(wù)學(xué)院，合肥 231201)

面向任務(wù)的物資的物流，應(yīng)視有利的前送時機(jī)，把客戶需求的物資及時、準(zhǔn)確地運送到位，這要求指揮決策人員合理組織運輸力量、科學(xué)選擇運輸路線，滿足客戶的物資需求時間要求，以達(dá)到最大效益。一般來說，運輸路線的不合理因素主要包括同種物資在同一段運輸路線上“相對運送”或“迂回運輸”等這種不符合節(jié)約里程的運輸，不僅增加了物資的物流費用，還浪費了運力，也降低了物資流轉(zhuǎn)速度。科學(xué)合理的運輸，不僅要求物資物流的噸公里最低，而且要求去掉不必要的裝卸工作量。研究各種物資物流問題的相關(guān)文獻(xiàn)很多，需要根據(jù)物資的供應(yīng)保障運輸問題特點進(jìn)行選擇。目前，理論研究的熱點是物流最短路徑，即節(jié)約里程問題，也就是從運輸起點到運輸終點的里程最短的問題，但該問題涉及大規(guī)模的路網(wǎng)節(jié)點，而運輸起點到運輸終點不存在有很多路網(wǎng)節(jié)點的情況，且小范圍內(nèi)的運輸路線一般都是確定的，故研究面向任務(wù)的物資供應(yīng)物流路徑優(yōu)化決策問題具有重要的理論意義和現(xiàn)實意義。本文采用運籌學(xué)方法，建立面向任務(wù)的物資供應(yīng)路徑問題的優(yōu)化模型，并設(shè)計智能求解算法對模型進(jìn)行求解。

1 面向任務(wù)的物資供應(yīng)物流路徑問題分析

面向任務(wù)的物資供應(yīng)路徑優(yōu)化問題可簡單理解為：只有一個被選物資倉庫，已知物流任務(wù)，車輛從物資倉庫出發(fā)，如何選擇物流路徑，在服務(wù)若干個物資需求客戶后回到物資倉庫。問題輸出是確定所需的運輸車輛數(shù)以及每輛車的運輸路線。車輛作為運輸保障的主要運輸工具，物資供應(yīng)路徑的優(yōu)化決策需要達(dá)到最大的經(jīng)濟(jì)效益，即以一定的優(yōu)化目標(biāo)，確定所需的運力(車輛數(shù))和每輛車的運輸路線，滿足運輸任務(wù)要求。

本研究可詳細(xì)表述為：已知需要運送給各需求客戶的物資數(shù)量，物資倉庫可組織若干輛同類型的運輸車輛來完成此次運輸任務(wù)，每輛車都有容量限制，所載物資總量不得超過其容量。開始時刻所有車輛都停放在倉庫中，有需求用戶在空間內(nèi)任意分布，需要確定所需的車輛數(shù)和每輛車的行駛路線，使車輛有序地把物資運送到各需求客戶，最后所有車輛返回物資倉庫。需要滿足的假設(shè)如下：

(1)所有運輸車輛以物資倉庫為起點并最終返回物資倉庫；

(2)每個需求客戶只被一輛車訪問一次且每輛車只能服務(wù)一條路線；

(3)在每條運輸路徑上，運送給各需求客戶的物資數(shù)量之和不能超過車輛的載重數(shù)量。

一般來說，客戶對物資的運輸?shù)竭_(dá)時間有一定限制，故車輛路徑問題具有時間約束，這就要求運輸過程中必須考慮先滿足急需，再滿足一般需求。為了深入研究，這里引入帶時間窗的車輛物流路徑問題(VRPTW)。

VRPTW問題是在傳統(tǒng)的車輛物流路徑問題的基礎(chǔ)上增加時間窗這一約束條件，時間窗約束一般情況下可分為三種，即混合時間窗、硬時間窗和軟時間窗[1]。VRPTW問題需要根據(jù)路徑查找、裝載量限制、物資需求客戶的服務(wù)次序這三項關(guān)鍵問題進(jìn)行決策。帶時間窗的車輛路徑問題，由于首要任務(wù)就是各個需求客戶對時間要求的問題，所以對客戶服務(wù)次序的確定是帶時間窗的車輛物流路徑問題中關(guān)鍵問題。

在物資運輸過程中，各個物資需求客戶對物資運達(dá)時間的要求很高，如果不能在規(guī)定的時間內(nèi)把物資送達(dá)客戶，將直接影響客戶的經(jīng)濟(jì)效益，因而本文研究帶硬時間窗的車輛路徑優(yōu)化問題。

在優(yōu)化目標(biāo)的選擇上，運輸時間和運輸距離是必須優(yōu)先考慮的決策因素。由于各需求客戶的硬時間窗要求將在建模時予以考慮，從運輸距離的角度來看，運輸時間、運輸保管及損毀、運輸成本等因素都與其有一定的比例關(guān)系，所以優(yōu)化運輸路徑、節(jié)約運輸里程無論是從微觀還是從宏觀角度，都有利于提高物資的物流效益。因此，以總的運輸距離最短作為優(yōu)化目標(biāo)，在滿足軍事效益的同時，對經(jīng)濟(jì)效益也有兼顧，有利于提高物資的綜合運輸效益。

2 面向任務(wù)的物資供應(yīng)路徑優(yōu)化問題建模

2.1 參數(shù)定義

假設(shè)現(xiàn)有一運輸任務(wù)，要求運送給需求客戶i的物資數(shù)為qi，需求客戶i有一個時間窗口[0，bi]，這個時間窗口表示車輛必須在時間bi之前到達(dá)需求客戶i。設(shè)需求客戶集合為C，需要的運輸車輛數(shù)集合為V，每輛運輸車的裝載容量為Q，且qi

2.2 數(shù)學(xué)模型構(gòu)建

對于每條弧(i,j)(ij，in+1，j0)和車輛k定義變量xijk：

則需設(shè)計一條所有車輛的總運輸距離最小的路徑，此路徑開始于頂點0，終止于頂點n+1。同時，還要保證計劃供應(yīng)給每個需求客戶的物資得到滿足，且不能違背各需求客戶的硬時間窗口和車輛的運能約束。經(jīng)上述參數(shù)描述，該VRPTW 的數(shù)學(xué)模型就可以表示為：

(式1)

(式2)

(式3)

Rk={rki|rki∈{1,2,…,n},i=1,2,…,nk}

(式4)

(式5)

(式6)

(式7)

tik≤bi,?k∈V,?i∈N

(式8)

xijk∈{0,1},?k∈V,?i,j∈N

(式9)

q,bi,dij,qij,tij∈Z+,?i,j∈N

(式10)

式1表示運輸目標(biāo)為所有車輛行駛的總距離最短；

式2表示每條路徑服務(wù)的需求客戶數(shù)量不超過需求客戶總數(shù)；

式3表示運輸給每條路徑上的各需求客戶物資總量不超過車輛的容量限制；

式4表示第k輛車的路徑組成；

式5、式6和式7表示每輛車始于物資倉庫，訪問需求客戶后回到物資倉庫；

式8表示車輛行駛過的時間窗約束；

式9和式10為取值約束。

3 基本蟻群算法的物資供應(yīng)路徑優(yōu)化模型求解

帶硬時間窗的車輛路徑問題已被證實是NP難問題。目前，關(guān)于解決此類問題的算法已經(jīng)很多，對于大型的車輛路徑問題，常用的有禁忌搜索算法、遺傳算法等。本文基于常用的傳統(tǒng)算法，設(shè)計了基于蟻群算法的模型算法，該模型算法的主要優(yōu)點在于針對大型車輛的路徑問題具有一定的實用性。

3.1 參數(shù)設(shè)定

m表示蟻群中螞蟻的數(shù)量；

a表示信息因子，即信息素的重要程度；

b表示期望因子，即能見度的重要程度；

r表示信息在時間間隔(t,t+n)內(nèi)衰減的比例，其中0

tij表示e(vi,vj) 上信息素的強(qiáng)度；

hij表示e(vi,vj)的能見程度，通常情況下取hij= 1/Disij；

Dtij表示螞蟻k在e(vi,vj)上單位長度的信息增量；

Disij表示節(jié)點vi與vj連接所成邊的的距離，vi，vjV。

3.2 算法求解流程

在蟻群系統(tǒng)中，螞蟻具有下面幾個特征：

(1)概率決定轉(zhuǎn)移路線。依據(jù)節(jié)點之間距離和路徑上信息量的函數(shù)，即用概率來決定轉(zhuǎn)移路線。

(2)信息素積累原則。每完成一次循環(huán)后，路徑上留的信息素逐漸遞增。

(3)信息素時間衰減規(guī)律。螞蟻留在路徑上的信息素量隨時間逐漸揮發(fā)，增量逐漸衰減。

蟻群算法求解的一般流程如圖1所示。

首先，各個路徑上的信息素量相等，且螞蟻可隨機(jī)選擇轉(zhuǎn)移路徑，并留下一定量的信息素；其次，螞蟻根據(jù)信息素的分布和可行路徑的能見度進(jìn)行路徑轉(zhuǎn)移決策；最后，依據(jù)路徑信息素強(qiáng)度的不斷積累情況尋求最優(yōu)或近似最優(yōu)路徑。

(1) 初始化。設(shè)置各個參數(shù)的初始值，即：信息素tij(0) =c(c為常數(shù))；信息素增量Dt(0) =c；能見度權(quán)重因數(shù)hij，且一般取hij= 1/Disij。

(2) 釋放蟻群。隨機(jī)給定起始節(jié)點，并記錄螞蟻的起始點，用來作為后續(xù)判斷螞蟻是否搜索完所有路徑的標(biāo)志。

(3) 依據(jù)概率選擇移動方向。節(jié)點vi上的螞蟻選擇下一節(jié)點vj的概率由信息素濃度tij和能見度因數(shù)hij共同確定，其尋優(yōu)過程依據(jù)概率進(jìn)行，其轉(zhuǎn)移概率的表達(dá)形式為：

(式11)

其中，allowedk= {V-tabuk}表示螞蟻k在有聯(lián)通路徑的點中下一步可以選擇的節(jié)點；tabuk表示第k只螞蟻已經(jīng)走過的路徑集合；V為螞蟻可以選擇的目標(biāo)節(jié)點集合； a 、b 兩參數(shù)反映信息素強(qiáng)度與能見度信息的相對重要性，其值一般通過實驗的方法來確定。

(4) 更新信息素。一次循環(huán)完成后，所得路徑上的信息素量根據(jù)下式進(jìn)行調(diào)整，表達(dá)式為:

τij(t+1)=Δτij(t,t+1)+(1-ρ)τij(t)

(式12)

(式13)

3.3 求解算法的改進(jìn)

3.3.1 可行點集allowedk的動態(tài)調(diào)整

在VRPTW問題中，由于每只螞蟻需要遍歷所有路網(wǎng)節(jié)點，且每只螞蟻的移動次數(shù)是不確定的，因此，在求解VRPTW問題的每次迭代過程中，只能將是否已經(jīng)回到出發(fā)的原點(倉庫)作為路徑構(gòu)造完成的標(biāo)志,即包括兩個相同的原點(倉庫)節(jié)點。在基于蟻群算法求解VRPTW問題中，本文將路徑構(gòu)造過程分為以下兩個階段：

(1)如果螞蟻的初始節(jié)點位置不是物資倉庫時，第一個階段就是由初始節(jié)點出發(fā)尋找物資倉庫的過程，稱為“過程Ⅰ”。在尋找中，可行點集allowedk中一定要包括物資倉庫，而不能包括初始節(jié)點。在到達(dá)物資倉庫后，接下來就是從物資倉庫出發(fā)找尋一條返回初始節(jié)點的路徑，該過程稱為“過程Ⅱ”。在此過程中，allowedk中通常應(yīng)包含初始節(jié)點等相關(guān)信息，但不能包含物資倉庫等相關(guān)信息。

(2)如果螞蟻的初始位置節(jié)點是物資倉庫，“過程Ⅰ”就是螞蟻的首步移動，即由物資倉庫移動到任意其他節(jié)點的過程。“過程Ⅱ”就是螞蟻回到物資倉庫的過程。因此,在“過程Ⅱ”中,allowedk必須包含物資倉庫，而在“過程Ⅰ”中，allowedk又不能包含物資倉庫。

可見，為滿足路徑搜索的需要，可行點集allowedk需要不斷地進(jìn)行動態(tài)調(diào)整。

3.3.2 選擇概率優(yōu)化

螞蟻在選擇下一個物資需求客戶時，應(yīng)考慮滿足兩個基本前提，即時間窗和車輛容量約束。除此之外，還必須考慮時間窗和路徑的擇優(yōu)這兩個因素。

(1)時間窗優(yōu)選問題。時間窗因素優(yōu)選的原則為：等待時間較短優(yōu)先和時間窗較小優(yōu)先。由于受下一個物資需求客戶j的時間窗和當(dāng)前節(jié)點到需求客戶j的時間等因素影響，在當(dāng)前節(jié)點i，將第k條路徑上的螞蟻物流路徑的轉(zhuǎn)移概率進(jìn)行改進(jìn)，即選擇下一物資需求客戶j的概率計算公式改進(jìn)為:

(式14)

其中，a和b為權(quán)重系數(shù)，

(2)路徑擇優(yōu)問題。主要考慮通往下一個物資需求客戶的路徑信息量和路徑長度。

3.3.3 參數(shù)優(yōu)化

將信息素的取值限制在區(qū)間[tmin,tmax]，其目的就是為最大限度地減少陷入搜索停滯，同時確保某條路徑上的信息素濃度極端化問題，即遠(yuǎn)大于其他路徑，進(jìn)而導(dǎo)致算法癱瘓或進(jìn)入死循環(huán)。

在蟻群算法的初始路徑尋優(yōu)階段，較大的r值具有優(yōu)先級別功能。在一定的范圍內(nèi)，隨著r的不斷增大，算法的整體性越來越好[2]。因此，在路徑優(yōu)選過程中，應(yīng)盡量選用較好的r值進(jìn)行，否則通常按照下式進(jìn)行調(diào)整。

(式15)

4 求解過程的算法設(shè)計

基于改進(jìn)的蟻群算法，設(shè)計了對帶硬時間窗的車輛路徑問題求解的基本流程。即：用人工螞蟻代替車輛來服務(wù)物資需求客戶，當(dāng)被選客戶物資需求運載總量超出汽車現(xiàn)有的物資數(shù)量時，則返回至物資倉庫，表示此次運輸已完成，否則一直到完成一次服務(wù)為止。此時，代表車輛的人工螞蟻就完成了一次巡游，當(dāng)全部螞蟻都完成后，記作一次循環(huán)。則所需的車輛數(shù)就是此次循環(huán)中那只所走總路徑最短的螞蟻往返于物資倉庫的次數(shù)。每一次循環(huán)結(jié)束之后，每只螞蟻巡游線路的優(yōu)選分析，必須根據(jù)信息素的增量及其發(fā)展變化進(jìn)行。經(jīng)過多次循環(huán)后，如果大部分螞蟻物流路徑的選擇相同或優(yōu)化完畢，則求解完成。求解具體步驟如下：

Step 1：參數(shù)原始初始化，取t= 0，置迭代次數(shù)NC_max = 0，讀取路網(wǎng)信息，將m只螞蟻放置于代表物資倉庫的節(jié)點，建立蟻群禁忌表tabuk和可行點集allowedk。

Step 2：從節(jié)點列表中搜索遺漏節(jié)點，針對每只螞蟻i而言，按照概率轉(zhuǎn)移公式(式14)計算轉(zhuǎn)移概率，再按照轉(zhuǎn)移概率利用輪盤賭法[3]選擇螞蟻下一個服務(wù)的需求客戶j。

Step 3：考慮路徑(i，j)的目標(biāo)需求客戶j的物資供應(yīng)量后，總的供應(yīng)量為q，如果q

Step 4：求解需求客戶j的到達(dá)時間，如果到達(dá)時間滿足時間窗的要求，則把相應(yīng)節(jié)點j加入tabuk禁忌表中，跳轉(zhuǎn)到Step 2，否則將節(jié)點j重新加入可行點集allowedk中，跳轉(zhuǎn)到Step 5[5]。

Step 5：螞蟻返回物資倉庫，對車輛數(shù)加1(初始為0)，然后對可行點集allowedk進(jìn)行判斷。如果allowedk為空，那么跳轉(zhuǎn)到Step 6，否則從allowedk中獲得未搜索過的節(jié)點，并以此作為起點，跳轉(zhuǎn)到Step 2，搜索下一個節(jié)點[6]。

Step 6：在每次完成一次巡游之后，就需要對螞蟻所走過的路徑按照信息素更新公式(式12和式13)進(jìn)行信息素更新，并記錄巡游路徑總長度。

Step 7：當(dāng)m只螞蟻完成搜索后，搜索得到本次迭代中的車輛最短路徑長度和所需的車輛數(shù)。將全局最優(yōu)解與本次迭代的最優(yōu)解進(jìn)行對比，并選擇最優(yōu)解，爾后根據(jù)需要按Step 6的步驟更新信息素。

Step 8：對最大迭代次數(shù)和全局最優(yōu)解進(jìn)行博弈，即只要兩者達(dá)到一個，則程序結(jié)束，輸出相關(guān)結(jié)論為最優(yōu)路徑解和所需的車輛數(shù)，否則跳轉(zhuǎn)到Step 2，重復(fù)上述步驟。

需要說明的是，如果僅根據(jù)信息素的濃度大小來搜索選擇下一服務(wù)節(jié)點，智能算法很容易較早地收斂于一條路徑，導(dǎo)致不能再去搜索空間中更短的路徑，即出現(xiàn)停滯現(xiàn)象。同時，為了避免過早收斂，在Step 2中使用了輪盤賭法選擇下一個節(jié)點。

5 結(jié)論

主要研究面向任務(wù)的物資供應(yīng)的路徑優(yōu)化決策問題，其成果可直接用于緊急情況下乃至戰(zhàn)時物資的車輛路徑優(yōu)化決策。考慮各個客戶物資需求的硬時間窗要求，以所有車輛運輸總距離最短作為優(yōu)化目標(biāo)，創(chuàng)建了數(shù)學(xué)優(yōu)化模型。從規(guī)模上來說，文中研究的路徑?jīng)Q策問題屬于小型問題的范疇，模型的解用精確解法就可以得出。但是，為了進(jìn)一步擴(kuò)展文中所建模型的適用范圍，根據(jù)所建模型特點，設(shè)計了基于改進(jìn)的蟻群算法，優(yōu)化結(jié)果為輸出車輛數(shù)、每輛車的運輸路徑和運輸總距離。