考慮實(shí)時(shí)擁堵指數(shù)和時(shí)間窗的多目標(biāo)冷鏈物流配送路徑優(yōu)化

摘要：針對(duì)生鮮產(chǎn)品冷鏈物流配送時(shí)間和總成本最小化為目標(biāo)，對(duì)配送中車輛使用成本、油耗以及碳排放成本等進(jìn)行綜合考慮。在實(shí)時(shí)擁堵指數(shù)和配送時(shí)間窗的約束下，構(gòu)建成本最小化模型。并結(jié)合行駛過(guò)程中三個(gè)連續(xù)階段的擁堵指數(shù)導(dǎo)致的行駛時(shí)間變化，從而得到優(yōu)化策略;最后，基于Pareto支配接受準(zhǔn)則的多目標(biāo)模型進(jìn)行求解，通過(guò)實(shí)際案例驗(yàn)證了模型的實(shí)用性和算法的有效性。結(jié)果表明，通過(guò)減少成本以及縮短時(shí)間來(lái)滿足客戶需要，將滿足國(guó)家以及人民對(duì)冷鏈物流配送的要求。

Abstract： Aiming at minimizing the distribution time and total cost of cold chain logistics of fresh products， the vehicle use cost， fuel consumption and carbon emission cost are considered comprehensively. Under the constraints of real-time congestion index and distribution time window， a cost minimization model is constructed. The driving time caused by the congestion index in three consecutive stages during the driving process is combined to obtain an optimized strategy. Finally， the multi-objective model based on Pareto domination acceptance criterion is solved， and the practicability of the model and the effectiveness of the algorithm are verified by a real case. The results show that by reducing costs and time to meet customer needs， it will meet the national and people's requirements for cold chain logistics distribution.

關(guān)鍵詞：冷鏈物流;實(shí)時(shí)擁堵指數(shù);路徑優(yōu)化;模擬退火算法

Key words： cold chain logistics;real-time congestion index;path optimization;simulated annealing algorithm

中圖分類號(hào)：F259.2;X322? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2020）09-0131-03

0? 引言

隨著經(jīng)濟(jì)的發(fā)展和居民生活質(zhì)量的提高，人們對(duì)生鮮產(chǎn)品的需要也越來(lái)越高，同時(shí)對(duì)冷鏈物流的要求也越來(lái)越高。與傳統(tǒng)的物流相比，冷鏈物流對(duì)運(yùn)輸產(chǎn)品的時(shí)效性具有更高的要求，此外，在考慮成本的情況下，也應(yīng)降低行駛過(guò)程中對(duì)于車輛以及冷凍設(shè)備等產(chǎn)生的碳排放量。因此，本文在確保生鮮產(chǎn)品時(shí)效性的前提下，實(shí)現(xiàn)低碳運(yùn)輸，建立冷鏈物流配送模型。

1? 問(wèn)題的描述與模型建立

1.1 問(wèn)題描述

已知L連鎖超市生鮮配送中心的冷鏈配送車輛為同一車型，且車輛最大載重為Q，配送車輛以L連鎖超市生鮮配送中心為起點(diǎn)，執(zhí)行完配送任務(wù)后且再返回L連鎖超市生鮮配送中心。假設(shè)L連鎖超市的每個(gè)超市被且只被訪問(wèn)一次，配送車輛的最大裝載量不能超過(guò)配送車輛的最大載重量Q，每個(gè)需被配送的超市都有一個(gè)時(shí)間窗，且不允許超過(guò)時(shí)間窗范圍。本文考慮道路的交通擁堵和滿足時(shí)間窗約束情況下，對(duì)冷鏈物流配送路徑優(yōu)化問(wèn)題進(jìn)行研究，考慮碳排放最低和配送時(shí)間最短兩個(gè)目標(biāo)。

1.2 假設(shè)前提

①配送網(wǎng)絡(luò)中，顧客的需求量已知;

②車隊(duì)只有一種運(yùn)輸車輛，其參數(shù)已經(jīng)確定;

③車輛在途中不允許停留，不考慮貨物裝卸時(shí)間;

④顧客的需求必須被滿足，并且顧客的需求不超過(guò)一輛車輛的總?cè)萘俊?/p>

1.3 道路實(shí)時(shí)交通擁堵指數(shù)設(shè)置

根據(jù)車載GPS收集到的數(shù)據(jù)以及道路功能和流量等綜合因素，換算成實(shí)時(shí)擁堵指數(shù)指標(biāo)，從而用數(shù)值方式量化描述道路交通運(yùn)行狀態(tài)，提高道路交通運(yùn)行狀態(tài)表達(dá)精度，同時(shí)也達(dá)到一個(gè)指數(shù)值。無(wú)論對(duì)快速路、地面主干路或其他道路具有相同的擁堵含義描述。為了能更有效及準(zhǔn)確的收集各路段的實(shí)時(shí)擁堵指數(shù)，本文路段的實(shí)時(shí)擁堵指數(shù)來(lái)自于百度智慧交通，百度智慧交通是基于百度地圖海量的交通出行數(shù)據(jù)、車輛軌跡數(shù)據(jù)、位置定位數(shù)據(jù)挖掘計(jì)算所得，根據(jù)對(duì)各路段長(zhǎng)久以來(lái)歷史數(shù)據(jù)的收集，可以準(zhǔn)確的預(yù)測(cè)出各個(gè)時(shí)刻路段的實(shí)時(shí)擁堵指數(shù)。

參考文獻(xiàn)及計(jì)算方法，為設(shè)置合理的擁堵參數(shù)，以上海市為例，通過(guò)百度地圖智慧交通數(shù)據(jù)，研究其交通擁堵情況，如圖1所示，因考慮生鮮配送時(shí)間，圖中僅研究從4：00-10：00的道路實(shí)時(shí)擁堵指數(shù)。

在模型計(jì)算中，根據(jù)周一至周五的擁堵指數(shù)按照以下標(biāo)準(zhǔn)規(guī)則，將實(shí)時(shí)擁堵指數(shù)與速度之間的關(guān)系對(duì)應(yīng)起來(lái)，如表1。

1.4 參數(shù)變量

為了便于問(wèn)題的求解，我們給出如表2所示符號(hào)說(shuō)明。

1.5 車輛時(shí)間求解

1.5.1 實(shí)時(shí)擁堵指數(shù)變化時(shí)的行駛時(shí)間計(jì)算方法

一般擁堵情況下的行駛時(shí)間模型，在行駛過(guò)程中大致分為三個(gè)連續(xù)階段：①擁有穩(wěn)定速度vncon（變量）的正常行駛期，②擁有穩(wěn)定速度vcon （常量）的擁堵期，③在兩者之間的過(guò)渡期。車輛在行駛弧的距離d和離開(kāi)時(shí)間l的計(jì)算如下式子所示：

上述式子中分別對(duì)應(yīng)的行駛狀況如下：式1）和式5）表示車輛處于正常自由行駛情況;式2）表示車輛處于由正常過(guò)渡到擁堵情況;式3）表示車輛處于完全擁堵的情況;式4）表示車輛處于由擁堵過(guò)渡到正常自由行駛的情況。

1.5.2 總行駛時(shí)間計(jì)算

在時(shí)變交通擁堵?tīng)顩r下，為了確定車輛在行駛?。╥，j）上的總行駛時(shí)間Tij，引入一個(gè)非負(fù)變量t■■表示

1.6 車輛成本求解

1.6.1 車輛的固定使用成本（人力成本+車輛使用成本）

使用車輛的固定成本通常是常數(shù)，與車輛行駛里程和服務(wù)的顧客數(shù)量沒(méi)有關(guān)系，包括車輛的固定損耗以及駕駛員工資等與車輛使用相關(guān)的成本，設(shè)定為常數(shù)C1。

其中，Sk為0，1變量，Sk=1表示配送中心第k輛車被使用，否則Sk=0。

1.6.2 油耗（運(yùn)輸成本）和碳排放成本

為定量研究車輛燃油消耗和碳排放的計(jì)算，客戶節(jié)點(diǎn)（i，j）的單位距離燃油消耗量ρ與車輛載重量Qx成線性關(guān)系可表示為：

已知配送車輛自重Q0，最大載重量Qk，設(shè)空載時(shí)單位距離燃油消耗量ρ0，滿載時(shí)燃油消耗量ρ*，所以有：

得出：

可以得出，單位距離車輛燃油消耗量為：

可以得出客戶節(jié)點(diǎn)（i，j）路段配送中所產(chǎn)生的燃油成本C2和配送中總碳排放量Qc表示為：

碳排放成本主要是描述車輛在配送過(guò)程中產(chǎn)生碳排放量的環(huán)境成本，本文通過(guò)燃油消耗來(lái)刻畫(huà)車輛碳排放量，通過(guò)碳稅機(jī)制定量計(jì)算碳排放成本，即碳排放成本=碳稅*碳排放量，則在客戶節(jié)點(diǎn)配送中的碳排放成本C3表示為：

1.7 目標(biāo)函數(shù)模型

式（1）為目標(biāo)函數(shù)1，代表車輛配送時(shí)間最短。式（2）為目標(biāo)函數(shù)2，代表總的配送成本最小。式（3）為車輛運(yùn)載能力約束。式（4）為配送車輛數(shù)量約束。式（5）為每輛車的配送線路起點(diǎn)和終點(diǎn)都是配送中心。式（6）和式（7）表示每個(gè)客戶都需要被訪問(wèn)一次且只被訪問(wèn)一次。式（9）和式（10）是時(shí)間窗約束。

2? 模擬退火算法

多目標(biāo)優(yōu)化方法：

通過(guò)對(duì)模型的分析，發(fā)現(xiàn)該模型有兩個(gè)目標(biāo)函數(shù)，時(shí)間最短和總成本最小。為求得多目標(biāo)優(yōu)化問(wèn)題的非劣解常常需要將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題去處理，實(shí)現(xiàn)這種轉(zhuǎn)化，的經(jīng)典方法主要有加權(quán)法，∈-約束法，進(jìn)化算法等。多目標(biāo)形式如下：

其中k？叟2表示目標(biāo)函數(shù)同時(shí)最小化。本文是一個(gè)k=2的雙目標(biāo)優(yōu)化問(wèn)題采用以下形式：

為了產(chǎn)生盡可能多的生成 Pareto 最優(yōu)解，每當(dāng)右側(cè)∈j有少量增加，問(wèn)題也再次求解。因此，首先選擇最小化總行駛時(shí)間為目標(biāo)函數(shù)進(jìn)行優(yōu)化求解，然后把得到的總時(shí)間作為約束條件，對(duì)第二個(gè)目標(biāo)函數(shù)進(jìn)行優(yōu)化求解。

3? 算例求解

某連鎖超市早上4點(diǎn)到9點(diǎn)前進(jìn)行生鮮配送，該公司具有4輛冷藏配送車，1個(gè)配送中心，配送網(wǎng)點(diǎn)9個(gè)，目前4輛車全部投入配送業(yè)務(wù)中，模型中各參數(shù)的取值情況如表3所示，各配送點(diǎn)的距離如表4所示。

本算例使用MatlabR2018a商業(yè)軟件進(jìn)行仿真，應(yīng)用本文提出的方法對(duì)模型進(jìn)行求解。模擬退火算法的參數(shù)為：初始溫度=10，結(jié)束溫度=100000，降溫速率=0.99。

通過(guò)運(yùn)算得到配送方案如表6所示，總配送成本為3850。

4? 結(jié)論

本文針對(duì)配送的批量小、地點(diǎn)分散、生鮮產(chǎn)品時(shí)間要求高的生鮮農(nóng)產(chǎn)品特點(diǎn)以及對(duì)品質(zhì)保障和低碳綠色物流的要求，考慮道路的實(shí)時(shí)擁堵指數(shù)和配送時(shí)間窗的約束下，同時(shí)優(yōu)化配送時(shí)間和碳排放成本，建立了以配送時(shí)間最短和配送成本最低為目標(biāo)函數(shù)的模型，從而進(jìn)行車輛路徑的選擇，進(jìn)一步提高配送的效率，降低碳排放成本和最大化配送效益。最后，在Pareto支配接受準(zhǔn)則下，運(yùn)用多目標(biāo)模擬退火算法進(jìn)行求解，并通過(guò)實(shí)際案例驗(yàn)證了模型的實(shí)用性和算法的有效性。

參考文獻(xiàn)：

[1]李妍峰，高自友，李軍.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐，2013，33（7）：1813-9.

[2]李妍峰，高自友，李軍.動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑派送問(wèn)題研究[J].管理科學(xué)學(xué)報(bào)，2014，17（8）：1-9.

[3]Alinaghian M， Naderipour M. A novel comprehensive macroscopic model for time-dependent vehicle routing problem with multi-alternative graph to reduce fuel consumption： A case study[J].Computers & Industrial Engineering.2016，99：210-22.

[4]Huang Y， Zhao L， Van Woensel T， Gross J-P. Time-dependent vehicle routing problem with path flexibility[J].Transportation Research Part B： Methodological.2017，95：169-95.

[5]Haghani A， Amoli GM， Pternea M. Dynamic （Time Dependent） Green Vehicle Routing Problem.2019.

作者簡(jiǎn)介：吳欣（1995-），女，安徽宿州人，碩士在讀，研究方向?yàn)楣愤\(yùn)輸。