邵可南，呂成瑤，張帥帥，宮 婧

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210023)

0 引 言

隨著人們生活水平的提高，越來越多的人選擇在線上購買生鮮商品。近幾年，國內(nèi)冷鏈物流運(yùn)輸市場逐步擴(kuò)大，如何控制運(yùn)輸成本成為研究的熱點(diǎn)。冷鏈物流是一種新型的物流運(yùn)輸方式，與傳統(tǒng)物流運(yùn)輸有較大的不同。首先，冷鏈物流運(yùn)輸?shù)能囕v需要使用額外的電能對生鮮商品進(jìn)行低溫冷凍；其次，生鮮商品必須要長期保存在低溫環(huán)境下，在運(yùn)輸過程中和卸貨配送過程中的溫度變化都會導(dǎo)致生鮮商品的變質(zhì)腐敗；再次，冷鏈運(yùn)輸對于配送時(shí)間窗的要求很高，物流運(yùn)輸車如果在客戶期望的時(shí)間窗外到達(dá)客戶點(diǎn)，無論是早到和遲到都會付出一定的代價(jià)；最后，冷鏈物流過程中使用了降溫裝置，造成的碳排放也會隨之增大，要通過合理規(guī)劃路徑減少碳排放。

車輛路徑優(yōu)化問題(VRP)是一類經(jīng)典的組合優(yōu)化問題，這類問題的研究工作有著非常重要的理論意義和應(yīng)用價(jià)值。其中，帶有容量約束的車輛路徑優(yōu)化問題(CVRP)具有更高的現(xiàn)實(shí)意義，所以得到了學(xué)術(shù)界更加廣泛的關(guān)注。目前，國內(nèi)外學(xué)者基于CVRP模型，構(gòu)建了很多冷鏈物流路徑優(yōu)化模型。Mansoureh Naderipour等[1]提出了考慮二氧化碳和氮氧化物排放以及開放時(shí)間窗的車輛路徑優(yōu)化模型。趙志學(xué)等[2]提出了考慮交通擁堵的冷鏈物流城市配送的綠色車輛路徑優(yōu)化模型。Ferani E.Zulvia等[3]提出了考慮運(yùn)營成本、貨損成本、碳排放量、客戶滿意度和時(shí)間窗的路徑優(yōu)化模型。劉虹等[4]提出了考慮客戶厭惡度和總成本的冷鏈物流路徑優(yōu)化模型。徐松梅[5]提出了考慮了固定成本、運(yùn)輸成本、制冷成本的帶時(shí)間窗路徑優(yōu)化模型。孫明明等[6]提出了考慮冷鏈物流配送過程中的時(shí)間成本、溫度成本和貨損成本的路徑優(yōu)化模型。

針對CVRP問題的求解算法，可以大致分為兩類，即精確算法和智能優(yōu)化算法。CVRP是一類典型的NP問題，精確算法雖然可以得到全局最優(yōu)解，但是隨著問題規(guī)模的擴(kuò)大，算法帶來的運(yùn)算量會以指數(shù)級的速度增長，這是人們無法接受的。因此，絕大多數(shù)研究者都將關(guān)注點(diǎn)放在了智能優(yōu)化算法上。20世紀(jì)70年代以來，伴隨著仿生學(xué)和人工智能科學(xué)的發(fā)展，人們提出了一系列傳統(tǒng)的智能優(yōu)化算法，包括粒子群算法、禁忌搜索、模擬退火算法、蟻群算法、遺傳算法以及人工神經(jīng)網(wǎng)絡(luò)技術(shù)等。隨后，研究者們也提出了很多改進(jìn)的智能優(yōu)化算法。蔣麗等[7]提出了求解眾包配送路徑問題的改進(jìn)蟻群算法。顏騰威[8]提出了求解VRP問題的改進(jìn)和聲算法。Ziauddin Ursani 等[9]提出了求解帶時(shí)間窗VRP問題的局部遺傳算法。Jean-Fran?ois Cordeau等[10]提出了求解VRP問題的并行迭代禁忌搜索算法。Artur Pessoa等[11]提出了求解異構(gòu)車隊(duì)VRP問題的改進(jìn)分支定價(jià)算法。龐凌[12]提出了結(jié)合煙花算法和遺傳算法來求解異質(zhì)車隊(duì)VRP問題。李小川等[13]提出了求解多目標(biāo)帶時(shí)間窗VRP問題的文化狼群算法。殷亞等[14]提出了多種混合蝙蝠算法用以求解帶硬時(shí)間窗的多目標(biāo)車輛路徑問題。

該文提出的冷鏈低碳物流路徑優(yōu)化模型是一個(gè)考慮綜合運(yùn)輸代價(jià)、帶有硬時(shí)間窗和容量約束的車輛路徑優(yōu)化問題模型(CVRP-TW)，并使用模擬退火—遺傳混合算法進(jìn)行仿真實(shí)驗(yàn)。

1 冷鏈低碳物流路徑優(yōu)化模型的構(gòu)建

1.1 模型簡述

根據(jù)冷鏈物流運(yùn)輸?shù)奶攸c(diǎn)及需求，該文構(gòu)建了多車輛、帶有硬時(shí)間窗約束和容量約束并且考慮綜合運(yùn)輸代價(jià)的冷鏈物流運(yùn)輸模型(CVRP-TW)。模型的結(jié)構(gòu)如圖1所示。

圖1 模型結(jié)構(gòu)

為了界定研究的問題，提出以下假設(shè)：

只有一個(gè)物流中心，但有若干臺冷鏈運(yùn)輸車，所有冷鏈運(yùn)輸車均為同一型號，運(yùn)輸商品全部是同一種生鮮商品。物流企業(yè)事先已經(jīng)了解所有配送客戶的準(zhǔn)確位置、貨物需求量、期望和接受的時(shí)間窗和卸貨配送所需要的時(shí)間。冷鏈運(yùn)輸車的最大載貨量不小于任一客戶的貨物需求量。物流企業(yè)有足夠的冷鏈運(yùn)輸車以確保能夠一次性完成整個(gè)運(yùn)輸配送過程。每個(gè)客戶的貨物只能由一臺冷鏈物流車為其配送一次，并且所有客戶的貨物需求量都得到滿足。所有冷鏈運(yùn)輸車在完成最后一個(gè)配送客戶的服務(wù)之后需要返回物流中心。冷鏈運(yùn)輸車到達(dá)客戶點(diǎn)的時(shí)間必須在客戶可接受的時(shí)間窗之內(nèi)。

基于上述假設(shè)，該文研究的問題描述為：在一次完整的物流運(yùn)輸過程，有一個(gè)物流中心，若干臺冷鏈運(yùn)輸車和若干個(gè)客戶參與其中，運(yùn)輸貨物完全為生鮮商品。在保證配送客戶貨物需求量和可接受時(shí)間窗的前提下，合理規(guī)劃路徑，找到一個(gè)綜合運(yùn)輸代價(jià)最小的配送方案。考慮的綜合運(yùn)輸代價(jià)包括運(yùn)輸固定代價(jià)、車輛運(yùn)輸代價(jià)、制冷代價(jià)、貨損代價(jià)、時(shí)間懲罰代價(jià)和碳排放代價(jià)。

1.2 模型建立

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

根據(jù)問題描述，建立考慮綜合代價(jià)的CVRP-TW模型，其中優(yōu)化目標(biāo)為：

minC=C1+C2+C3+C4+C5+C6

(1)

其中，C1至C6分別表示運(yùn)輸固定代價(jià)、車輛運(yùn)輸代價(jià)、制冷代價(jià)、貨損代價(jià)、時(shí)間窗代價(jià)和碳排放代價(jià)。

(1)固定代價(jià)C1：

C1=mc1

(2)

其中，c1是每輛車的固定代價(jià)。

(2)車輛運(yùn)輸代價(jià)C2：

(3)

其中，c2是車輛行駛單位路程所造成的車輛運(yùn)輸代價(jià)，對所有車輛在運(yùn)送回路上的距離求和并乘上單位運(yùn)輸代價(jià)即為車輛運(yùn)輸代價(jià)。

(3)制冷代價(jià)C3：

(4)

其中，p31為車輛行駛過程中單位時(shí)間產(chǎn)生的制冷代價(jià)，p32為卸貨配送過程中單位時(shí)間產(chǎn)生的制冷代價(jià)，對車輛行駛時(shí)間和卸貨配送時(shí)間分別求和乘上對應(yīng)的單位制冷代價(jià)作為總的制冷代價(jià)。

(4)貨損代價(jià)C4：

其中，p0為生鮮商品的單價(jià)，α為車輛行駛中的商品變質(zhì)率，β為卸貨配送過程中的商品變質(zhì)率。一個(gè)客戶點(diǎn)的商品，從物流中心出發(fā)到客戶點(diǎn)會經(jīng)歷車輛運(yùn)輸?shù)臅r(shí)間和之前客戶點(diǎn)的卸貨配送時(shí)間，在這段時(shí)間商品會產(chǎn)生變質(zhì)，貨損和時(shí)間的關(guān)系可以用線性關(guān)系刻畫[15]。故對運(yùn)輸時(shí)間和卸貨時(shí)間分別求和乘上貨物量和相應(yīng)的變質(zhì)率作為各客戶點(diǎn)的貨損，再對所有客戶點(diǎn)的貨損求和并乘上商品單價(jià)作為總的貨損代價(jià)。

(5)時(shí)間懲罰代價(jià)C5：

(6)

(7)

(6)碳排放代價(jià)C6：

其中，p51為冷鏈運(yùn)輸車早到單位時(shí)間的等待代價(jià)，p52為冷鏈運(yùn)輸車遲到單位時(shí)間的遲到代價(jià)。ε0為冷鏈運(yùn)輸車空載時(shí)行駛單位距離的油耗，εM為冷鏈運(yùn)輸車滿載時(shí)行駛單位距離的油耗，q(k,i,j)為第k輛車行駛在地點(diǎn)i到地點(diǎn)j之間時(shí)的車輛載重量。E2為制冷設(shè)備工作單位時(shí)間產(chǎn)生的能耗，e為二氧化碳排放系數(shù)即單位能耗所排放的二氧化碳質(zhì)量，p6為排放單位質(zhì)量二氧化碳所產(chǎn)生的代價(jià)。式(8)計(jì)算了車輛行駛時(shí)發(fā)動機(jī)工作產(chǎn)生的能耗和制冷設(shè)備工作時(shí)產(chǎn)生的能耗(其中發(fā)動機(jī)工作產(chǎn)生的代價(jià)和車輛當(dāng)前載重有關(guān))，再乘上單位能耗產(chǎn)生的二氧化碳和單位碳排放代價(jià)作為總的碳排放代價(jià)[16]。

1.2.2 約束條件

根據(jù)上述問題假設(shè)，得到模型的約束條件。每個(gè)客戶的貨物需求量不能超過一臺冷鏈運(yùn)輸車的最大載重量，即：

Qj≤QM,j=1,2,…,n

(9)

每個(gè)客戶都被服務(wù)并且只能由一臺配送車輛為其服務(wù)一次，即：

(10)

所有冷鏈運(yùn)輸車在完成最后一個(gè)配送客戶的服務(wù)之后需要返回物流中心，即：

(11)

冷鏈運(yùn)輸車到達(dá)客戶點(diǎn)的時(shí)間必須在客戶可接受的時(shí)間窗之內(nèi)，即：

(12)

2 求解CVRP-TW問題的模擬退火-遺傳混合算法

CVRP-TW是一類典型的NP問題，需要使用智能優(yōu)化算法對問題的解空間進(jìn)行有效的搜索來尋找最優(yōu)解。該文將使用一種模擬退火-遺傳混合算法來求解CVRP-TW問題。

2.1 算法流程

Step1：初始化算法環(huán)境，輸入原始參數(shù)，設(shè)置算法參數(shù)：種群規(guī)模np，初始選擇規(guī)模ns，初始交叉概率pc，初始模擬退火算法執(zhí)行概率ps，線性參數(shù)k1,k2,k3，進(jìn)化代數(shù)M。置迭代數(shù)gen=1；

Step3：計(jì)算當(dāng)前種群中個(gè)體的適應(yīng)度，選擇ns+?gen/k1」個(gè)體，并復(fù)制一部分個(gè)體填充新種群；

Step4：對當(dāng)前種群中所有個(gè)體兩兩配對，依概率pc-k2gen進(jìn)行交叉操作；

Step5：對當(dāng)前種群中所有個(gè)體依概率ps+k3gen執(zhí)行模擬退火算法；

Step6：gen=gen+1，若gen

2.2 算法實(shí)現(xiàn)

由于CVRP-TW問題的特殊性，為考慮算法的計(jì)算可行性，該文采用針對該問題的編碼方式和解的更新操作。

(1)編碼方式是自然數(shù)編碼，具體方式為在每輛車的配送路徑(即配送客戶點(diǎn)編號序列)后加上0(最后一輛車不用加)。例如：1,2,3,0,4,5,6表示第一輛車配送客戶點(diǎn)編號先后為1,2,3，第二輛車配送客戶點(diǎn)編號先后為4,5,6。算法首先會生成一個(gè)配送方案集合。

(2)配送方案選擇操作是選擇ns+?gen/k1」個(gè)當(dāng)前配送方案集合中的方案保留到下一代配送方案。其中最好的前5%配送方案直接保留，剩下的選擇名額會根據(jù)適應(yīng)度用輪盤賭選出，適應(yīng)度為配送方案代價(jià)的倒數(shù)。最后對新集合最終適應(yīng)度排名靠前的np-ns-?gen/k1」個(gè)配送方案進(jìn)行復(fù)制填充入新集合。

(3)交叉操作是隨機(jī)選擇兩個(gè)配送方案，再隨機(jī)選擇兩個(gè)交叉點(diǎn)，互換選中的兩個(gè)配送方案里兩個(gè)交叉點(diǎn)之間的編碼(0的位置不動)，再根據(jù)交換表更新非交換部分的編碼。

隨著高等教育體制改革的逐步深入，高校辦學(xué)規(guī)模不斷擴(kuò)大，師生數(shù)量、資產(chǎn)購置、基建投資規(guī)模和經(jīng)費(fèi)總量都大幅度增長，高校在經(jīng)費(fèi)使用、基建工程、物資設(shè)備采購等方面擁有越來越多的自主權(quán)。因此，廉潔風(fēng)險(xiǎn)防控機(jī)制是高校規(guī)范權(quán)力運(yùn)行、科學(xué)有序發(fā)展的必然要求，是完善大學(xué)治理體系、建設(shè)現(xiàn)代大學(xué)制度的現(xiàn)實(shí)需要，是加強(qiáng)高校干部隊(duì)伍作風(fēng)建設(shè)、推動學(xué)校預(yù)防腐敗工作的有力抓手[1]。高校要圍繞“人、財(cái)、物”等管理監(jiān)督重點(diǎn)，加強(qiáng)廉潔風(fēng)險(xiǎn)防控機(jī)制建設(shè)。

(4)模擬退火算法中的配送方案的更新為隨機(jī)選擇的兩點(diǎn)交換或三點(diǎn)輪換(0的位置可以改變，但0不能連續(xù)或在頭尾)。

為保證配送方案的有效性，只要對配送方案本身進(jìn)行改變，就要對新配送方案進(jìn)行約束條件檢測，確保配送方案集合里所有的配送方案都是可行的。SA-GA算法的實(shí)現(xiàn)流程如圖2所示。

圖2 SA-GA算法執(zhí)行流程

2.3 算法小結(jié)

模擬退火-遺傳混合算法(SA-GA)是通過對經(jīng)典的遺傳算法和模擬退火算法進(jìn)行結(jié)合和優(yōu)化形成的一種混合算法。經(jīng)典遺傳算法中的變異操作是保證遺傳算法局部搜索精度的操作，該文將這個(gè)操作用模擬退火算法進(jìn)行替換。此外，種群選擇的規(guī)模、個(gè)體交叉的概率和對種群每個(gè)個(gè)體執(zhí)行模擬退火的概率采用動態(tài)設(shè)置，以保證在算法執(zhí)行初期能有較大的全局搜索范圍，在算法執(zhí)行中后期能夠?qū)ο鄬潭ǖ姆N群進(jìn)行較大次數(shù)的迭代尋優(yōu)，從而在搜索范圍和求解精度兩個(gè)方面盡可能保證算法的性能。

3 仿真實(shí)驗(yàn)設(shè)計(jì)與分析

通過仿真實(shí)驗(yàn)測試遺傳算法的求解效果。問題參數(shù)設(shè)置如下：一個(gè)物流中心要向20個(gè)客戶點(diǎn)提供冷鏈物流配送服務(wù)，共有四輛冷鏈運(yùn)輸車，冷鏈運(yùn)輸車行駛速度為50 km/h、最大載重量12 t，模型的參數(shù)如表1所示。

表1 仿真實(shí)驗(yàn)參數(shù)設(shè)置

續(xù)表1

3.1 仿真實(shí)驗(yàn)求解結(jié)果

使用上述設(shè)定數(shù)據(jù)進(jìn)行模擬退火-遺傳混合算法的實(shí)驗(yàn)仿真。設(shè)置算法參數(shù)如下：最大進(jìn)化代數(shù)M=100，種群規(guī)模np=100，初始交叉率pc=0.8，初始模擬退火算法執(zhí)行率ps=0.8，線性參數(shù)k1=3,k2=0.008,k3=0.002，模擬退火算法初始溫度T0=126，終止溫度Tf=91.7，降溫系數(shù)αc=0.968 8，Markov鏈長度Lk=1。隨機(jī)生成初代配送方案集合，執(zhí)行20次模擬退火-遺傳混合算法，得到最優(yōu)代價(jià)為5 901.5，最佳配送方案中四輛冷鏈運(yùn)輸車的配送代價(jià)分別為1 453.6、1 509.7、1 417.0和1 521.2。在求解算法中每一次更新解都會進(jìn)行約束條件檢驗(yàn)，所以最優(yōu)解是有效的。

3.2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法的有效性，該文使用經(jīng)典的遺傳算法和模擬退火算法各進(jìn)行20次實(shí)驗(yàn)仿真，三種算法的求解效果如表2所示，求解最優(yōu)解時(shí)的收斂軌跡如圖3所示。

表2 仿真實(shí)驗(yàn)結(jié)果比較

圖3 收斂軌跡

根據(jù)表2所示，模擬退火-遺傳混合算法相比前兩種經(jīng)典算法有著更好的求解性能，這主要體現(xiàn)在：

(1)求解效率提高。

模擬退火-遺傳混合算法在相同次數(shù)的實(shí)驗(yàn)下比兩種經(jīng)典算法有著更小的平均收斂代數(shù)，意味著混合算法的搜索效率更好。從最優(yōu)解的離散情況來看，混合算法的最小代價(jià)標(biāo)準(zhǔn)差介于兩種算法之間。

(2)搜索范圍較大。

模擬退火-遺傳混合算法求出的最優(yōu)配送方案的綜合代價(jià)優(yōu)于兩種經(jīng)典算法，這表明了混合算法的搜索范圍是較大的，并且最優(yōu)解沒有陷入局部最優(yōu)，收斂到全局最優(yōu)。

(3)求解精度更高。

模擬退火-遺傳混合算法的平均代價(jià)比兩種經(jīng)典算法要好，表明了混合算法在每個(gè)生成解的領(lǐng)域內(nèi)有著較高的搜索精度。

模擬退火-遺傳混合算法可以看作是模擬退火算法和遺傳算法的一種折中方案。如果智能優(yōu)化方法既要擴(kuò)大搜索范圍，又要提高求解精度，勢必要增加運(yùn)算量。所以模擬退火-遺傳混合算法是旨在保持相同數(shù)量級運(yùn)算量的前提下，對搜索范圍和搜索精度的一種權(quán)衡?；旌纤惴ㄔ趫?zhí)行的前期盡可能地?cái)U(kuò)大搜索范圍，避免算法陷入局部最優(yōu)解，在執(zhí)行的中后期根據(jù)動態(tài)概率的設(shè)定盡可能使種群穩(wěn)定下來，讓模擬退火算法對于每個(gè)個(gè)體有盡可能大的執(zhí)行次數(shù)，提高個(gè)體領(lǐng)域內(nèi)的搜索精度，并且由于每個(gè)個(gè)體領(lǐng)域的搜索是獨(dú)立的，也可以保證算法在中后期的搜索范圍。上述實(shí)驗(yàn)結(jié)果也表明了模擬退火-遺傳混合算法相對于前兩種經(jīng)典算法而言，是一種更加高效的智能搜索方法。同時(shí)，模擬退火-遺傳混合算法實(shí)現(xiàn)簡單，繼承了遺傳算法的魯棒性和潛在的并行性，有著較高的實(shí)用價(jià)值。

4 結(jié)束語

根據(jù)當(dāng)前冷鏈物流運(yùn)輸行業(yè)的需求，建立了帶硬時(shí)間窗的冷鏈低碳物流路徑優(yōu)化模型，確定了以綜合代價(jià)最優(yōu)為目標(biāo)的CVRP-TW問題。其后通過遺傳算法和模擬退火算法這兩個(gè)經(jīng)典的智能優(yōu)化算法對建立的模型進(jìn)行仿真實(shí)驗(yàn)求解。之后根據(jù)遺傳算法和模擬退火算法的優(yōu)缺點(diǎn)，將兩種經(jīng)典算法進(jìn)行改進(jìn)和結(jié)合，提出了模擬退火-遺傳混合算法。通過仿真實(shí)驗(yàn)?zāi)M求解，驗(yàn)證了模擬退火-遺傳混合算法在解決冷鏈低碳物流路徑優(yōu)化問題上有著更好的效率并且能給出更好質(zhì)量的解。下一步考慮將這一算法應(yīng)用到多物流中心和多配送車型等更多約束的路徑優(yōu)化問題的求解上。