何 慧 程鐵信

(天津工業(yè)大學經(jīng)濟與管理學院 天津 300387)

一、問題的背景

雙十一購物節(jié)讓眾多的商家及購物客戶瘋狂，物流業(yè)在這一天承擔超負荷的商品運送任務。隨著城市的快速發(fā)展，越來越多的大型物流公司集結(jié)在城市周邊。城市白天不允許貨車入城，只能限定在夜間24點至凌晨4點入城。城區(qū)按各商業(yè)中心商場為圓心，7km為半徑的總體外包絡為界。城區(qū)外運行不受時間限制。

某城市物流集團有B01～B07等7個物流分公司中轉(zhuǎn)站，各中轉(zhuǎn)站均配備一定數(shù)量的貨車。物流集團需要調(diào)配7個物流公司中轉(zhuǎn)站的貨車夜間進城收集需要運送的商品，每個收貨點收貨裝載平均大約10分鐘。貨車執(zhí)行完任務后需返回原物流公司中轉(zhuǎn)站。貨車裝載參數(shù):I型貨車限裝0.6噸，II型貨車限裝1噸。假設貨車城區(qū)平均車速25km/h。

根據(jù)任務要求，需完成收貨目標有A01～A10等10個商業(yè)區(qū)域，每個商業(yè)區(qū)域包含數(shù)量不等的網(wǎng)銷商家，其中中心商城是該商業(yè)區(qū)域中網(wǎng)銷規(guī)模較大綜合性商場，所有商業(yè)區(qū)域的商家的具體坐標參數(shù)見表1，假設每個網(wǎng)銷商家之間都有道路相連，路長簡化為直線距離。

表1 物流分公司中轉(zhuǎn)站的相關信息

二、文獻綜述

鄧先瑞、于曉慧、李春艷等人提出一種基于種群分類粒子群算法的物流區(qū)域配送中心車輛運輸路徑調(diào)度優(yōu)化方法，建立配送中心車輛運輸路徑調(diào)度的數(shù)學模型，目標函數(shù)為最短配送路徑，通過粒子群算法對車輛調(diào)度數(shù)學模型進行求解，完成配送中心車輛調(diào)度的協(xié)調(diào)性優(yōu)化，該方法可以合理的選擇運輸路徑，但不能合理的完成車輛運輸路徑的裝載[1]。張倩、魯渤、楊華龍?zhí)岢隽艘环N物流區(qū)域配送中心車輛路徑的魯棒優(yōu)化方法，該方法根據(jù)算例對車輛路徑的魯棒性度量指標效果進行分析，對適用于車輛運輸路徑方案的魯棒性指標進行選擇，通過兩階段優(yōu)化算法完成配送中心車輛運輸路徑調(diào)度的協(xié)調(diào)性優(yōu)化，該方法可以合理的對車輛運輸路徑進行裝載，但得到的運輸路徑不合理[2]。

三、模型的建立

本文要求在不考慮裝載容量及運輸成本的情況下，確定行車方案，使得所有運貨車輛在城內(nèi)的運送工作時間總和最短。在車輛勻速行駛的條件下，要使運送工作時間總和最短，即要求車輛行駛路徑最短。由于不需要考慮每輛車的裝載容量，所以首先派出一輛車入城收貨，遍歷所有的收貨點，求這輛車的最短路徑，這樣就成為一個典型的旅行商(TSP)問題。然后建立單目標多約束的線性優(yōu)化模型，調(diào)用蟻群算法求解模型。再運用逐步推進法確定第一輛車的行駛路徑，判斷是否需要加派車輛，完成本文中的最短行駛時間的目標。

(一)建立求解各個商區(qū)內(nèi)最短路徑的模型

1.選取決策變量

由于勻速行駛，計算一個商區(qū)內(nèi)的最短行駛時間，等價于計算最短行駛路徑，即轉(zhuǎn)化成典型的旅行商問題。選取貨車從收貨點i到收貨點j的整數(shù)型0-1變量xij、收貨點i和j之間的行駛距離dij為決策變量。

2.確定目標函數(shù)

以最短行駛時間為目標，建立一個商區(qū)內(nèi)的單目標多約束的線性優(yōu)化模型。以商區(qū)A01為例建立模型，選取貨車在該商區(qū)內(nèi)運行時間函數(shù)t：

式中，dij為兩個收貨點i和j之間的行駛距離，v為貨車行駛的速度，由題目知v=25km/h，定義0-1整數(shù)型變量xij=1表示貨車從收貨點i到收貨點j，否則xij=0，10為每個收貨點收貨的時間，n為每個商業(yè)區(qū)商場的數(shù)量。

3.對目標函數(shù)做以下約束：

(1)貨車到達收貨點i后，接下來的目的地j只能有一個：

(2)對于收貨點j，只能由一個收貨點i出發(fā)到達此處：

(3)確保貨車行駛路線中沒有子回路的產(chǎn)生：

問題一與TSP的不同在于終點的不同，TSP問題的終點即起點，根據(jù)題意問題一的終點是最后一個收貨點。

xi1i2+xi2i3+…+xik-1ik≤k-1(i1,i2,…,ik=1,2,…,n;k=2,3,…,n-1)

(4)判斷貨車經(jīng)過收貨點i后是否緊接著要經(jīng)過收貨點j：

綜上所述，貨車在A01商區(qū)內(nèi)的線路優(yōu)化模型為：

(二)建立求解城內(nèi)最短路徑的模型

基于已知相關數(shù)據(jù)，以貨車在城區(qū)內(nèi)進行貨物運送的路線為研究對象，求其最優(yōu)行車路線和貨車調(diào)度策略。先考慮只派出一輛貨車的情況，求得兩個商業(yè)區(qū)域間的運送時間最短的方案。然后判斷該車接下來是直接回中轉(zhuǎn)站還是去鄰近商區(qū)，若去鄰近商區(qū)的時間比從中轉(zhuǎn)站重新派車的時間長，則需要重新派車。在每一個商業(yè)區(qū)收貨結(jié)束后都需要重復判斷，直至最后一個中轉(zhuǎn)站。從而實現(xiàn)調(diào)度分配與行車路線規(guī)劃。本題以時間最短為目標，建立單目標多約束的貨車行車路線線性優(yōu)化模型。

1.選取決策變量

因為貨車勻速行駛，行駛時間最短等價于行駛路程最短，又已知各個商場的坐標中轉(zhuǎn)站的坐標，所以選取任意兩點之間的運行時間fk為決策變量。

2.確定目標函數(shù)

為了使所有運貨車輛在城內(nèi)的運送工作時間綜合最小，選取總時間函數(shù)T：

其中fk為貨車在第k個商業(yè)區(qū)域內(nèi)的運送工作時間。

3.確定約束條件

(1)判斷某商區(qū)是否由某物流中轉(zhuǎn)站派出貨車：

其中，l指的是第l個中轉(zhuǎn)站，k指的是第k個商區(qū)。

(2)計算每個商區(qū)內(nèi)的運送工作時間

dlk1表示從第l個中轉(zhuǎn)站派車去第k個商區(qū)的第1個商場在城內(nèi)所經(jīng)過的距離，dkn1表示從第k個商區(qū)的第n個商場收貨完成后回到第l個中轉(zhuǎn)站的城內(nèi)的距離。

(3)每個物流中轉(zhuǎn)站在派車時，需要考慮中轉(zhuǎn)站自身的貨車數(shù)量。需滿足派出的貨車數(shù)量小于等于該中轉(zhuǎn)站的貨車數(shù)量的條件：

式中，對商區(qū)的某個中轉(zhuǎn)站派遣貨車數(shù)量累計求和，小于等于該中轉(zhuǎn)站總貨車數(shù)量，其中，貨車數(shù)量上限分別為n1=3,n2=2,n3=3,n4=2,n5=3,n6=2,n7=3。

(4)物流中轉(zhuǎn)站派出的貨車數(shù)量應滿足是非負整數(shù)

ni∈N

式中，N表示物流中轉(zhuǎn)站可派的貨車數(shù)量，i表示物流中轉(zhuǎn)站的標號。

(5)為了能有效完成所有商業(yè)區(qū)的貨車運送任務，不考慮裝載容量和運輸成本的條件下，至少需要派出一輛貨車進行運送，因此有以下約束：

綜上所述，貨車行車路線優(yōu)化可以歸結(jié)為以下模型：

四、模型的求解

(一)蟻群算法求解TSP問題

由于在某一商區(qū)區(qū)域內(nèi)的貨車行駛時間最短問題可以轉(zhuǎn)換為TSP問題，且蟻群算法采用了分布式并行計算機制，易于與其他方法結(jié)合，具有很強的魯棒性，因此我們選用蟻群算法來解決TSP問題，該算法基本步驟如下：

step1:首先初始化，設迭代次數(shù)為NC，初始化NC=0；將m只螞蟻置于n個頂點上；初始化信息素及其他參數(shù)。

step2：進入循環(huán)，按照分段函數(shù)計算全局轉(zhuǎn)移選擇因子，計算轉(zhuǎn)移概率，m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游。設螞蟻k當前所在頂點為i，那么螞蟻k由點i向點j移動要遵循概率函數(shù)而遷移選擇下一點。

step3：判斷第k只螞蟻是否到達終點，若到達終點，則k=k+1，否則返step2；記錄本次迭代最佳路線，按照螞蟻行駛路徑更新局部信息素。

step4：判斷所有螞蟻是否完成搜索，若全部完成搜索，進行全局信息素更新，否則返回step3。

step5：達到循環(huán)結(jié)束的條件后，循環(huán)停止，輸出計算結(jié)果最優(yōu)路徑，否則NC=NC+1。

(二)確定商區(qū)內(nèi)最短行車路線

由于每個商業(yè)區(qū)域內(nèi)的收貨點比較密集，若不只派一輛車進入同一個商區(qū)收貨，將會使貨車在城區(qū)內(nèi)的運行時間及成本大大提高，不滿足題意及實際需求，因此可以將每一個商區(qū)都視為一個TSP問題，但不需要考慮再返回起點。使用蟻群算法對每個商區(qū)內(nèi)行車路線進行求解，得到的結(jié)果如表2：

表2 每個商區(qū)內(nèi)最佳行車路線

(三)計算所需車輛數(shù)

根據(jù)固定的收貨點和物流中轉(zhuǎn)站，可以求解出貨車在相鄰兩個商區(qū)收貨點之間行駛的時間。當貨車在上一個商區(qū)收完貨物之后，需判斷直接回中轉(zhuǎn)站還是繼續(xù)去下一個商區(qū)。

圖1 判斷是否新增貨車示意圖

如圖1所示，若線段a+b+c+d>a+c+e，則說明貨車不返回直接去下一商區(qū)的時間更短，無需新增貨車；否則新增一輛貨車，沿線段d入城收貨。

經(jīng)判斷發(fā)現(xiàn)，貨車從06商區(qū)A0606收貨點前往10商區(qū)A1003收貨點的時間大于從A0606到城區(qū)邊界與從A1003到城區(qū)邊界的最短時間之和，因此需派兩輛車進行貨物運送，其中第一輛車運送范圍為A01-A07商業(yè)區(qū)，第二輛車運送范圍為A08-A10商業(yè)區(qū)。

五、總結(jié)

本文在求解滿足目標條件下的最優(yōu)運輸路徑時，考慮到每個商區(qū)內(nèi)收貨點分布比較密集，最好用同一輛車進行運送，因此首先將每個商區(qū)視為一個整體，將其轉(zhuǎn)化為TSP問題，從而使用蟻群算法求解出每個商區(qū)內(nèi)的最優(yōu)路徑；后來經(jīng)過判斷共需兩輛車后，再分別將兩輛車的行駛范圍看作一個TSP問題，便于求解出滿足目標的最優(yōu)方案，這樣既將問題簡化，同時又符合實際。