鄧紅星，王瑋琦，王永康

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

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

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

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

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

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

1.1 問題描述

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

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

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

1.1.2 約束條件

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

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

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

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

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

1.2 模型構(gòu)建

1.2.1 假設(shè)條件

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

1)僅考慮一個配送中心對客戶的配送情況；

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

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

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

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

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

文中在數(shù)學(xué)模型中出現(xiàn)的參數(shù)變量符號如下：V為客戶集，V={2，3，…，n}；V0為節(jié)點(diǎn)集(客戶集合和配送中心)，中心倉庫由數(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允許最早開始服務(wù)的時間；bi為客戶i允許最晚開始服務(wù)的時間；ti為客戶i所需的服務(wù)時間；M為一個任意大的數(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)離開配送中心的載重量，t；Lj為車輛服務(wù)客戶j(j)后的載貨量，t；Sik為車輛開始服務(wù)客戶i(i∈V)的時間，如果車輛k沒有服務(wù)客戶i，則Sik=0。

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

2.1 JOPT簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 車輛資源基本信息

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

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

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

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

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

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

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

圖1 配送線路

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

4 結(jié) 語

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