公路零擔(dān)物流企業(yè)末端配送路徑優(yōu)化

鄧紅星，王瑋琦，王永康

(1.東北林業(yè)大學(xué) 交通學(xué)院，黑龍江 哈爾濱 150040； 2.中國(guó)鐵路上海局集團(tuán)有限公司 蚌埠貨運(yùn)中心，安徽 蚌埠 233000)

企業(yè)物流的高效運(yùn)作關(guān)系到企業(yè)的運(yùn)營(yíng)與發(fā)展。物流的末端配送車輛路徑優(yōu)化因其節(jié)省成本、提高效率、增加企業(yè)競(jìng)爭(zhēng)力等優(yōu)點(diǎn)而被廣泛關(guān)注，因此，研究配送體系中的車輛路徑優(yōu)化問(wèn)題十分必要，近些年國(guó)內(nèi)外學(xué)者都在努力探索。

國(guó)外對(duì)公路零擔(dān)貨運(yùn)的研究主要集中在運(yùn)輸網(wǎng)絡(luò)模型的設(shè)計(jì)。Yaman[1]提出了層級(jí)軸輻式網(wǎng)絡(luò)設(shè)計(jì)模型，進(jìn)而實(shí)現(xiàn)網(wǎng)絡(luò)資源的均衡利用。Alumur[2]等在考慮建站成本和需求不確定性的基礎(chǔ)上，構(gòu)建了單分配和多分配樞紐點(diǎn)選址的共用模型。 Ishfaq和Sox[3]通過(guò)評(píng)估樞紐點(diǎn)作業(yè)對(duì)于網(wǎng)絡(luò)設(shè)計(jì)的影響，建立了以物流網(wǎng)絡(luò)設(shè)計(jì)成本最小化為目標(biāo)的數(shù)學(xué)模型。Alan Erera[4]針對(duì)零擔(dān)貨運(yùn)(LTL)承運(yùn)商面臨的服務(wù)網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題提出了一個(gè)整數(shù)規(guī)劃模型。

近年來(lái)，公路零擔(dān)貨物運(yùn)輸迅猛發(fā)展，引起了國(guó)內(nèi)很多專家的關(guān)注，專業(yè)性的研究也越來(lái)越多。王瑞等人[5]對(duì)公路零擔(dān)貨運(yùn)企業(yè)擴(kuò)大營(yíng)業(yè)網(wǎng)點(diǎn)的方式進(jìn)行了SWOT分析，提出相應(yīng)的發(fā)展策略。孫真[6]利用共同配送理論將城市末端物流資源進(jìn)行整合，從而緩解末端物流配送成本高、效率低的問(wèn)題。 莫仁邊[7]通過(guò)分析電子商務(wù)平臺(tái)給零擔(dān)運(yùn)輸企業(yè)帶來(lái)的挑戰(zhàn)和機(jī)遇，就提高零擔(dān)運(yùn)輸企業(yè)競(jìng)爭(zhēng)力提出了相應(yīng)對(duì)策。許智子和宋微等人[8-9]通過(guò)引入相關(guān)的數(shù)學(xué)模型，用以解決零擔(dān)運(yùn)輸配送路徑優(yōu)化問(wèn)題。田昀和羅耀等人[10-11]分別利用模擬退火算法和改進(jìn)粒子群算法對(duì)配送路徑優(yōu)化問(wèn)題進(jìn)行分析研究。劉丹霞[12]構(gòu)建了基于“互聯(lián)網(wǎng)+”的同城配送路徑優(yōu)化模型，并使用改進(jìn)的禁忌搜索算法對(duì)帶時(shí)間窗的同時(shí)取送貨問(wèn)題進(jìn)行了優(yōu)化求解。吳正陽(yáng)[13]建立了靜態(tài)模型和動(dòng)態(tài)模型，用于解決多資源約束下配送路徑的優(yōu)化問(wèn)題。

本文從企業(yè)角度出發(fā)，根據(jù)公路零擔(dān)物流企業(yè)的實(shí)際物流問(wèn)題，建立數(shù)學(xué)模型，并結(jié)合算法對(duì)零擔(dān)物流企業(yè)末端配送路徑進(jìn)行優(yōu)化設(shè)計(jì)，更加具有針對(duì)性和實(shí)踐意義。

1 末端配送路徑優(yōu)化模型的建立

1.1 問(wèn)題描述

公路零擔(dān)物流企業(yè)末端配送路徑優(yōu)化模型可以描述為：在已經(jīng)獲取配送中心以及客戶點(diǎn)的地理位置信息情況下，安排一定數(shù)量的配送車輛從配送中心裝載貨物后出發(fā)，為客戶點(diǎn)提供送貨和集貨服務(wù)，其中，車輛的最大行駛距離以及載重量己知，每個(gè)客戶的可接受服務(wù)時(shí)間和需求量己知，要求合理安排配送車輛，規(guī)劃合理的配送路徑，在滿足約束條件的前提下，實(shí)現(xiàn)目標(biāo)函數(shù)的最優(yōu)。

1.1.1 優(yōu)化目標(biāo)

為更加直觀地表示目標(biāo)優(yōu)化問(wèn)題，使運(yùn)算過(guò)程更符合現(xiàn)實(shí)情況，現(xiàn)將路徑優(yōu)化模型中的目標(biāo)轉(zhuǎn)化為配送費(fèi)用形式，包含車輛運(yùn)輸?shù)墓潭ㄙM(fèi)用和變動(dòng)費(fèi)用。固定費(fèi)用與配送車輛的數(shù)量成正比，變動(dòng)費(fèi)用可以用配送距離的正比例函數(shù)來(lái)表示。

1.1.2 約束條件

在建立配送路徑優(yōu)化模型時(shí)，為保障配送服務(wù)的可實(shí)現(xiàn)性，需要設(shè)立相應(yīng)的約束條件，具體可分為以下幾方面：

1)貨物數(shù)量約束：在優(yōu)化配送路徑的過(guò)程中必須使車輛遍歷所有客戶點(diǎn)。

2)送達(dá)時(shí)間約束：配送車輛只允許在約定時(shí)間段內(nèi)進(jìn)行裝卸作業(yè)。

3)資源使用約束：在配送過(guò)程中資源使用量不能超出配送中心的現(xiàn)有數(shù)量。

4)配送車輛約束：由于城市內(nèi)大多對(duì)貨車有交通管制，只有特定的時(shí)間可以通行，并且也有載重量限制。當(dāng)貨物超出額定載重量時(shí)，需要增加配送車輛的數(shù)量，將配送路徑進(jìn)一步劃分。

1.2 模型構(gòu)建

1.2.1 假設(shè)條件

路徑優(yōu)化模型根據(jù)條件的不同可以有很多類型，根據(jù)公路零擔(dān)物流企業(yè)末端配送的實(shí)際情況，對(duì)模型作出以下假設(shè)。

1)僅考慮一個(gè)配送中心對(duì)客戶的配送情況；

2)配送路徑與配送車輛一一對(duì)應(yīng)；

3)每輛車可為多個(gè)客戶服務(wù)，每個(gè)客戶只能被一輛車服務(wù)；

4)客戶需求的準(zhǔn)確性和時(shí)效性必須保障；

5)地理位置及需求量均已知；

6)配送車輛車型統(tǒng)一且無(wú)超載現(xiàn)象；

7)所有貨物均可同車配送有特殊要求的客戶。

1.2.2 目標(biāo)函數(shù)

目標(biāo)函數(shù)

(1)

約束條件

?j∈V,

(2)

(3)

(4)

(5)

Lj≥L1k-Dj+Pj-M(1-x1jk)

?j∈k;?k∈K,

(6)

?i∈V;?j∈V;i≠j,

(7)

?j∈V;?k∈K,

(8)

?i∈V0;?j∈V0;?k∈K,

(9)

xijk∈{0，1} ?i∈V0;?j∈V0;?k∈K,

(10)

?i∈V0;?j∈V0;?k∈K.

(11)

式(1)以車輛運(yùn)輸?shù)墓潭ㄙM(fèi)用和變動(dòng)費(fèi)用最小為目標(biāo)函數(shù)。式(2)確保每個(gè)顧客只能被一輛車服務(wù)。式(3)保證車輛完成對(duì)客戶的服務(wù)后必須離開(kāi)，以實(shí)現(xiàn)路徑的連續(xù)性。式(4)保證每輛車從配送中心出發(fā)，到達(dá)客戶后必須離開(kāi)，最終返回配送中心。式(5)～式(7)為車輛載貨量，分別為初始載貨量、服務(wù)第一個(gè)客戶后的載貨量和車輛在路徑中的載貨量。M為一個(gè)任意大的數(shù)。式(8)為載貨量條件，車輛在配送過(guò)程中不能超重行駛。式(9)為時(shí)間窗條件，確保在規(guī)定時(shí)間內(nèi)完成配送。式(10)為變量的取值范圍。式(11)為車輛行駛的距離不能超過(guò)額定最大距離。

文中在數(shù)學(xué)模型中出現(xiàn)的參數(shù)變量符號(hào)如下：V為客戶集，V={2，3，…，n}；V0為節(jié)點(diǎn)集(客戶集合和配送中心)，中心倉(cāng)庫(kù)由數(shù)字1表示，客戶集由2，3，…，n表示，V0=V∪{1}；K為車輛集，K={1，2，…，m};Qk為車輛k的裝載能力，t；Sk為車輛k的最大行駛距離，km；cd為車輛k的分派成本，元；ct為單位距離的行駛成本，元；dij為客戶i和j之間的距離，km；i∈V，j∈V;i≠j;Pi為客戶i的取貨量，t；Di為客戶i的送貨量，t；ai為客戶i允許最早開(kāi)始服務(wù)的時(shí)間；bi為客戶i允許最晚開(kāi)始服務(wù)的時(shí)間；ti為客戶i所需的服務(wù)時(shí)間；M為一個(gè)任意大的數(shù)；xijk為車輛k的行駛變量，xijk∈{0，1}。如果車輛k從點(diǎn)i(i∈V0) 行駛到點(diǎn)j(j∈V0)，則xijk=1，否則，xijk=0；L0K為車輛k(k∈K)離開(kāi)配送中心的載重量，t；Lj為車輛服務(wù)客戶j(j)后的載貨量，t；Sik為車輛開(kāi)始服務(wù)客戶i(i∈V)的時(shí)間，如果車輛k沒(méi)有服務(wù)客戶i，則Sik=0。

2 基于JOPT的末端配送路徑優(yōu)化仿真

2.1 JOPT簡(jiǎn)介

JOPT(配送路徑優(yōu)化和移動(dòng)資源調(diào)度算法包)是由德國(guó)DNA Evolutions軟件公司開(kāi)發(fā)的用于配送路徑優(yōu)化和車輛調(diào)度的算法包。JOPT基于遺傳算法和啟發(fā)規(guī)則，在解決包含大規(guī)模配送點(diǎn)和車輛路徑問(wèn)題時(shí)表現(xiàn)出計(jì)算速度快、優(yōu)化質(zhì)量高、集成方便的特點(diǎn)。

2.2 創(chuàng)建優(yōu)化模型信息

1)創(chuàng)建模型對(duì)象信息：首先在main主程序中創(chuàng)建模型對(duì)象，創(chuàng)建云計(jì)算訪問(wèn)JOPT的對(duì)象Client。主要包括時(shí)間、營(yíng)業(yè)時(shí)間、工作時(shí)間、資源信息、配送點(diǎn)信息、優(yōu)化結(jié)果對(duì)象以及模型優(yōu)化參數(shù)。

2)創(chuàng)建優(yōu)化模型對(duì)象：用戶需要把所有的信息都封裝匯總到opt中，然后由opt上傳到優(yōu)化器中。

3)創(chuàng)建資源(人和車輛)信息：主要包括資源編號(hào)或名稱、緯度經(jīng)度信息、工作時(shí)間上限、行駛路程上限、工作時(shí)間區(qū)間。創(chuàng)建好第i個(gè)資源后，還需添加其它屬性并創(chuàng)建多維運(yùn)能變量。

4)創(chuàng)建配送點(diǎn)(客戶)信息：配送點(diǎn)信息函數(shù)主要有配送點(diǎn)編號(hào)或名稱、緯度經(jīng)度信息、營(yíng)業(yè)時(shí)間區(qū)間、資源在該配送點(diǎn)需要訪問(wèn)持續(xù)的時(shí)間(s)、該配送點(diǎn)被訪問(wèn)的優(yōu)先等級(jí)(從低到高1 100)。

5)創(chuàng)建類對(duì)象信息：首先創(chuàng)建運(yùn)能對(duì)象，并為運(yùn)能對(duì)象添加體積約束和重量約束，然后創(chuàng)建裝載或卸載對(duì)象，添加配送點(diǎn)需要裝載和卸載貨物的體積和重量。

6)創(chuàng)建數(shù)組類型信息：包括車輛工作時(shí)間、配送點(diǎn)開(kāi)放時(shí)間、車輛資源信息、配送點(diǎn)信息、優(yōu)化屬性。

7)創(chuàng)建優(yōu)化參數(shù)對(duì)象信息：影響整體優(yōu)化執(zhí)行的屬性如表1所示，影響針對(duì)多目標(biāo)的優(yōu)化結(jié)果，可通過(guò)設(shè)置程序懲罰系數(shù)，包括總距離、最大在途距離、時(shí)間窗和載重能力來(lái)實(shí)現(xiàn)。

表1 優(yōu)化終止條件

8)創(chuàng)建模型優(yōu)化結(jié)果對(duì)象：可以調(diào)用的方法有總成本、總時(shí)間、總行駛時(shí)間、總行程、第i個(gè)路徑的編號(hào)或名稱、第i個(gè)路徑上的第j個(gè)配送。

3 實(shí)例驗(yàn)證

淮南地區(qū)某公司有一批貨物，需分別配送給26位用戶(用編號(hào)A，B，C，D，…，Z表示)，車輛資源信息如表2所示，各客戶需要配送的貨物量、需要回收的貨物量、客戶點(diǎn)之間的位置如表3所示。按該公司現(xiàn)有配送方案，已知其配送成本為2 330元，配送距離為166 km，配送時(shí)間為22.2 h，使用車輛數(shù)為3輛?，F(xiàn)利用JOPT對(duì)末端配送路徑進(jìn)行優(yōu)化。

將JOPT算法包作為優(yōu)化器，需要使用C#語(yǔ)言在Microsoft Visual C#2010中編寫目標(biāo)函數(shù)和約束條件。有以下幾點(diǎn)需要說(shuō)明：

1)車輛和人員的上班時(shí)間設(shè)置為8時(shí)至18時(shí)，行駛里程上限為800 km，工作時(shí)間上限為10 h。

2)客戶點(diǎn)的開(kāi)放時(shí)間也統(tǒng)一設(shè)置為8時(shí)至18時(shí)。每個(gè)客戶點(diǎn)的作業(yè)時(shí)間設(shè)置為20 min，將客

表2 車輛資源基本信息

表3 客戶點(diǎn)服務(wù)需求數(shù)據(jù)表

戶點(diǎn)的優(yōu)先級(jí)進(jìn)行統(tǒng)一設(shè)置。

3)為區(qū)分配送貨物和取回貨物，給車輛設(shè)置運(yùn)能向量，分別表示兩種貨物的運(yùn)量和總運(yùn)量，并給出各個(gè)客戶點(diǎn)的貨物類型。

4)設(shè)置迭代次數(shù)為100；設(shè)置終止條件，當(dāng)目標(biāo)函數(shù)值趨于穩(wěn)定時(shí)，將超重懲罰系數(shù)設(shè)置為1 000。

將數(shù)據(jù)輸入到visual中，運(yùn)行軟件，調(diào)用JOPT算法包，得到優(yōu)化后績(jī)效指標(biāo)總成本為1 591元，總行駛距離為118 km，使用的配送車輛數(shù)為2輛，具體配送線路如圖1所示。

根據(jù)得到的實(shí)際數(shù)據(jù)，優(yōu)化前后的具體結(jié)果對(duì)比如表4所示。

表4 優(yōu)化前后對(duì)比

圖1 配送線路

通過(guò)以上信息可以看出，優(yōu)化后的配送路徑縮短了配送距離、減少了配送時(shí)間、降低了配送成本、提高了配送效率，在一定程度上增強(qiáng)了企業(yè)的競(jìng)爭(zhēng)力。

4 結(jié) 語(yǔ)

本文運(yùn)用JOPT算法包求解配送路徑優(yōu)化模型，對(duì)公路零擔(dān)物流企業(yè)末端配送路徑進(jìn)行了優(yōu)化。最后以末端配送的實(shí)際數(shù)據(jù)為例，證明該方法的可行性。通過(guò)對(duì)比分析，優(yōu)化路徑在一定程度上縮短了配送里程，降低了配送成本。因此，利用JOPT算法來(lái)優(yōu)化末端配送路徑的方法是可行的。本文的局限性在于僅討論了單個(gè)配送中心同種類車輛的配送問(wèn)題，但對(duì)多個(gè)配送中心的不同種類車輛配送問(wèn)題還需進(jìn)一步研究。