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

艾云平

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 參數(shù)定義

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

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

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

則需設(shè)計(jì)一條所有車輛的總運(yùn)輸距離最小的路徑，此路徑開始于頂點(diǎn)0，終止于頂點(diǎn)n+1。同時(shí)，還要保證計(jì)劃供應(yīng)給每個(gè)需求客戶的物資得到滿足，且不能違背各需求客戶的硬時(shí)間窗口和車輛的運(yùn)能約束。經(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表示運(yùn)輸目標(biāo)為所有車輛行駛的總距離最短；

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

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

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

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

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

式9和式10為取值約束。

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

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

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

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

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

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

r表示信息在時(shí)間間隔(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é)點(diǎn)vi與vj連接所成邊的的距離，vi，vjV。

3.2 算法求解流程

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

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

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

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

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

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

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

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

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

(式11)

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

(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 可行點(diǎn)集allowedk的動(dòng)態(tài)調(diào)整

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

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

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

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

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

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

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

(式14)

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

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

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

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

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

(式15)

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

基于改進(jìn)的蟻群算法，設(shè)計(jì)了對(duì)帶硬時(shí)間窗的車輛路徑問題求解的基本流程。即：用人工螞蟻代替車輛來服務(wù)物資需求客戶，當(dāng)被選客戶物資需求運(yùn)載總量超出汽車現(xiàn)有的物資數(shù)量時(shí)，則返回至物資倉庫，表示此次運(yùn)輸已完成，否則一直到完成一次服務(wù)為止。此時(shí)，代表車輛的人工螞蟻就完成了一次巡游，當(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é)點(diǎn)，建立蟻群禁忌表tabuk和可行點(diǎn)集allowedk。

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

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

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

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

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

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

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

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

5 結(jié)論

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