基于經(jīng)典TSP問(wèn)題的物流運(yùn)輸任務(wù)規(guī)劃

何 慧 程鐵信

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

一、問(wèn)題的背景

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

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

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

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

二、文獻(xiàn)綜述

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

三、模型的建立

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

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

1.選取決策變量

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

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

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

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

3.對(duì)目標(biāo)函數(shù)做以下約束：

(1)貨車到達(dá)收貨點(diǎn)i后，接下來(lái)的目的地j只能有一個(gè)：

(2)對(duì)于收貨點(diǎn)j，只能由一個(gè)收貨點(diǎn)i出發(fā)到達(dá)此處：

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

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

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

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

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

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

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

1.選取決策變量

因?yàn)樨涇噭蛩傩旭偅旭倳r(shí)間最短等價(jià)于行駛路程最短，又已知各個(gè)商場(chǎng)的坐標(biāo)中轉(zhuǎn)站的坐標(biāo)，所以選取任意兩點(diǎn)之間的運(yùn)行時(shí)間fk為決策變量。

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

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

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

3.確定約束條件

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

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

(2)計(jì)算每個(gè)商區(qū)內(nèi)的運(yùn)送工作時(shí)間

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

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

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

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

ni∈N

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

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

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

四、模型的求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五、總結(jié)

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