基于NSGA Ⅱ的生鮮品冷鏈配送聯合調度優化

梁桂云，陳淮莉

(上海海事大學物流科學與工程研究院，上海 201306)

0 引 言

近年來,隨著互聯網技術日益成熟、用戶消費習慣和理念的轉變,生鮮電商行業得到迅速發展。2020年受新冠疫情影響，消費者對于生鮮到家的需求急速增長,中國生鮮電商交易額達到1 821.2億元。由于生鮮品具有易腐性和保質期短的特點，生鮮電商企業須在完成對生鮮品的流通加工后立即組織安排配送。然而,目前生鮮電商企業大多憑經驗來判定各崗位的員工調度，由此帶來加工環節混亂、配送延遲和各種資源的緊缺與沖突等眾多問題。因此，如何協同優化流通加工與配送這兩個環節，在降低總成本的同時保證交付產品的新鮮度,一直是生鮮電商企業關注的問題。

關于生鮮品的生產加工和配送聯合調度(production and distribution integrated scheduling，PDIS)問題的研究如下：AMORIM等研究分批和批量兩種生產模式下的生鮮品PDIS問題，通過算例驗證了批量生產能夠降低總成本。BELO-FILHO等設計了一種自適應大鄰域搜索算法求解生鮮品PDIS問題。SEYEDHOSSEINI等提出了一種考慮批量生產和庫存路徑的生鮮品PDIS模型，并開發了啟發式算法進行求解。DEVAPRIYA等研究了保質期約束下的生鮮品PDIS問題，通過遺傳算法對所構建的生鮮品PDIS模型進行求解。吳瑤等基于路網交通狀況的時變性，構建了以配送成本與產品價值損耗總和最小為目標的優化模型，并設計了混合遺傳算法進行求解。馬雪麗等考慮生鮮品的需求和配送時間的隨機性，研究了生產商和零售商兩級供應鏈模式下的生鮮品PDIS問題，并利用基于隨機模擬的混合遺傳算法進行求解。LACOMME等研究了單一生鮮品生產和多車運輸一體化問題。王旭坪等根據在線訂餐問題特點，將生產環節和配送環節分別抽象為并行機調度問題和帶時間窗的車輛路徑問題(vehicle routing problem with time window, VRPTW)，以服務所有訂單需要的總時間之和最小為目標，構建并行機生產多車多任務配送聯合優化模型，并設計了三階段啟發式在線調度算法進行求解。李暢等在關于生鮮品PDIS問題中考慮了生鮮品保質期和客戶購買行為，并通過算例驗證了所建模型的有效性。DAYARIAN等根據生產人員配置建立了生鮮品PDIS優化模型，再根據模型特點設計了新的分支定價算法進行求解。LIU等以最小化配送時間為目標建立了生鮮品PDIS優化模型，并設計了一種改進的大鄰域搜索算法進行求解。LI等研究了考慮食品包裝因素影響的生鮮品PDIS問題,利用混合整數線性規劃方法來描述這個新問題，提出了兩種分支切割算法，計算結果表明包裝與生產路線的集成優化可以帶來經濟效益。SOLINA等考慮生產加工的轉換時間和產品易腐性約束，以最小化生產和配送成本為目標建立了一個生產和分銷的綜合調度優化模型。

以上關于生鮮品PDIS的文獻大多考慮單目標或者將多個目標轉化為單目標進行研究。經濟的發展和生活質量的改善使得人們對商品品質的要求逐漸提高，而新鮮度作為決定生鮮品品質的重要指標越來越受到重視。少數學者開始在關于多目標生鮮品配送路徑優化的研究中考慮產品交付時的新鮮度：李暢等在生鮮品配送路徑優化的研究中構建了以最大化新鮮度和最小化配送成本為目標的生鮮品配送路徑優化模型，并利用基本自適應差分進化算法進行求解；李善俊等將生鮮品新鮮度與多目標VRPTW進行結合，建立最大化生鮮品新鮮度和最小化配送成本的多目標車輛路徑優化模型，并設計了非支配排序遺傳算法(non-dominated sorting genetic algorithm，NSGA)進行求解。然而，少有文獻將生鮮品的新鮮度與多目標生鮮品冷鏈配送聯合調度問題相結合。因此，本文在以往文獻研究成果的基礎上，以產品交付時新鮮度最大和總成本最低為目標，建立多目標生鮮品冷鏈配送聯合調度優化模型，并利用第二代非支配排序遺傳算法(NSGA Ⅱ)，獲得滿足產品交付時新鮮度最大和總成本最低的相對較優解。

1 問題描述和模型建立

1.1 問題描述和模型假設

結合生鮮品加工和配送的特點，將多目標生鮮品冷鏈配送聯合調度問題描述為：如圖1所示，一個生鮮電商配送中心向多個客戶提供生鮮品送貨上門服務。生鮮電商企業在平臺接收客戶訂單后，根據訂單需求安排多名加工人員進行加工，每個訂單產品種類不同且不可拆分。訂單加工完成后立即分批組織車輛進行配送，忽略裝車時間。針對生鮮品易腐和保質期短的特點，需要將流通加工環節與配送環節進行聯合調度。同時，為了提高客戶滿意度和生鮮電商企業的利潤，需要在追求產品交付時新鮮度最大和總成本最低兩個目標的基礎上決策：訂單分配給加工人員、各加工人員的訂單加工順序、已完成加工的訂單生成合理的配送車次，以及各車次的訂單交付順序。本文采用文獻[15]中定義的()表示產品新鮮度。根據生鮮品價值隨運輸時間加速遞減的特點，令()為生鮮品的價值損耗系數，為訂單產品的保質期，則()=eln(2)-1，從而()=1-()。

圖1 生鮮品加工配送流程示意圖

由于多目標生鮮品冷鏈配送聯合調度的復雜性，為便于模型的構建和求解，假設：(1)客戶地理位置、客戶要求服務的時間窗、產品的需求量和保質期等信息已知；(2)每個客戶只被服務一次，每個訂單只包含同一類產品且加工時間均不同；(3)加工中心采取并行機加工模式，由多個能力相同的加工人員進行加工，不考慮訂單加工的等待時間；(4)每個訂單僅由一名加工人員負責加工，訂單不可拆分且只被加工一次，忽略不同訂單之間的切換時間和成本；(5)有多輛車(其容量是相等的)負責配送，不存在等待配送情況；(6)每車次負責配送一條路徑，該車次從配送中心的發車時刻不早于對應路徑上最后一個訂單的加工完成時刻；(7)車輛完成一次配送后立即返回配送中心；(8)生鮮品離開配送中心時新鮮度最大。

1.2 參數定義

1.3 模型構建

本文將流通加工環節抽象為并行機調度問題，將配送環節抽象為VRPTW。由于每個訂單的加工成本是固定的，而配送成本不是固定的，因此將配送總成本作為目標之一。配送總成本主要包括運輸成本、固定成本、延遲成本、等待成本和產品價值損耗成本。基于上述分析和參數定義，模型建立如下：

(1)

(2)

s.t.

(3)

(4)

(5)

(6)

?,∈,≠,∈

(7)

(8)

(9)

(10)

(11)

(12)

(13)

?,∈,∈

(14)

(15)

(16)

()≥

(17)

={0,1}, ?,∈,∈

(18)

={0,1}, ?,∈,∈

(19)

={0,1}, ?∈,∈

(20)

式(1)表示配送總成本最低；式(2)表示產品交付時平均新鮮度最大；式(3)表示最多只有一個訂單是由加工人員第一個加工的；式(4)和(5)表示所有訂單均被生產加工；式(6)表示加工人員的訂單加工順序；式(7)表示訂單的后續緊鄰訂單的生產加工完成時間；式(8)和(9)表示所有客戶均被服務且只訪問一次；式(10)表示路徑流量平衡；式(11)表示每輛車配送完成后必須返回配送中心；式(12)表示每條路徑滿足車輛容量約束；式(13)表示每條路徑的開始配送時間不早于該路徑上所有訂單的生產完成時間；式(14)～(16)表示每條配送路徑上的時間關系約束；式(17)表示交付的產品滿足最低新鮮度要求；式(18)～(20)為0-1變量約束。

2 NSGA Ⅱ設計

本文提出的多目標生鮮品冷鏈配送聯合調度問題是傳統PDIS問題的延伸，PDIS問題已被證明是NP難問題，因此多目標生鮮品冷鏈配送聯合調度問題也是NP難問題。CPLEX只適合求解現實生活中較為簡單的小規模算例，因此無法通過CPLEX在合理的時間內獲得本文問題的解。而智能優化算法已被廣泛地應用于大規模、復雜度高的算例中。與單目標優化問題的不同在于，在考慮多個目標時，這些目標通常都是相悖的，很難在不降低一個目標性能的前提下提高另一個目標性能。在實際的經營活動中，決策者會根據不同的場景和自身的經驗以及偏好在所得的帕累托最優解集中選擇一個或者多個相對合適的帕累托最優解作為實際問題的解決方案。因此，為得到多目標生鮮品冷鏈配送聯合調度問題的帕累托最優解集，本文根據所提問題和模型的特點，利用NSGA Ⅱ對構建的模型進行求解，算法流程見圖2。

圖2 NSGA Ⅱ流程

2.1 染色體編碼和種群初始化

根據所建模型的特點，設計以下編碼方案：染色體采用自然數編碼；染色體包含3個子串(訂單加工順序子串，負責加工各訂單的加工人員子串和配送路徑子串)。這種編碼方式的優勢在于可以十分便捷地將信息直接輸入染色體中，不需要復雜的計算和解碼過程。例如，加工配送中心有6個客戶訂單待服務，有2名加工人員，若生成的染色體如圖3所示，則該染色體表示加工人員1需要依次加工訂單3和6，加工人員2需要依次加工訂單1、2、4、5，配送中心共需要發出3個車次。在配送路徑子串3中0用于分隔不同車次，表示車輛從配送中心出發最終又回到配送中心。

圖3 染色體示意圖

2.2 快速非支配排序和個體擁擠度比較

2.2.1 快速非支配排序

快速非支配排序是NSGA Ⅱ的關鍵步驟之一，其基本原理是根據種群中染色體之間的支配關系對種群進行等級劃分，從而使算法可以快速向帕累托前沿方向進行搜索。將本文問題轉換為最小化問題后，假設支配染色體的染色體的數量為，被染色體支配的染色體的集合為。快速非支配排序的主要步驟如下：

分別計算種群中每一個染色體的和，如果染色體支配染色體，即<，則=∪{}；如果染色體支配染色體，則=+1；直至種群所有染色體均進行了比較。

遍歷種群中所有的染色體，當染色體不受任何其他染色體支配，即=0時，將染色體納入第一非支配層，并令中所有的染色體的非支配序=1，令=0。

=+1，當第非支配層不為空集時，對于中的每一個染色體以及被染色體支配的任一染色體，令=-1。當=0時，則令染色體的非支配序=+1。

判斷第+1非支配層+1是否為空：若為空，快速非支配排序終止，否則轉步驟3。

由上述步驟可以得到??…，其中中的解比中的解具有更高的優先度。與非支配排序相比，快速非支配排序的優點在于不僅能夠快速對種群進行等級劃分，而且能夠將算法的復雜度由()(為目標函數數量)降到()，極大地提高了算法的運算效率。

個體擁擠度比較是NSGA Ⅱ的另一關鍵步驟，其基本原理是首先計算同一非支配層中所有個體的擁擠距離，然后根據擁擠距離的大小對同一非支配層中的個體進行優先級排序。個體的擁擠距離是指在目標空間中緊鄰的兩個個體與之間的距離。本文中，目標函數的數量=2。個體擁擠度比較主要步驟如下：

初始化同一非支配層中所有個體的擁擠距離:令為同一非支配層中任意個體的擁擠距離，令=0。

計算同一非支配層的所有個體的第′個目標函數值，并按照目標函數值升序排列。

令排序在邊緣的個體的擁擠距離值等于最大的距離值，使得排序在邊緣的個體具有選擇優勢。

對任意排序在中間的個體，計算其擁擠距離：

2.2.4 自卑心理:當腸造口開放,患者容易感覺到該病不僅對自身的形象構成嚴重影響,甚至還給家人帶來了較大的麻煩,嚴重時甚至還會導致家庭、社會關系破裂,如朋友遠去、夫妻離婚等,從而導致其產生自卑、自閉心理。

循環執行步驟2～4，直至計算出該非支配層中所有個體在第′個目標函數下的擁擠距離。

為使帕累托最優解集分布更加均勻以及提高解的多樣性，擁擠距離較大的個體被選中的概率更大。同時采用錦標賽方法從父代種群中選擇染色體進行交叉和變異操作，生成新的子代。在每次錦標賽選擇過程中，當被選中的染色體屬于同一非劣等級，即值相同時，優先選擇擁擠距離較大的染色體；當被選中的染色體屬于不同非劣等級，即值不同時，優先選擇非劣等級較低，即值較小的染色體。

2.3 交叉和變異操作

算法在進化過程中主要通過交叉和變異操作生成新的個體，因此交叉和變異操作對于算法的全局搜索能力具有重要影響。本文交叉操作采用基于位置的交叉(position-based crossover，PBX)方式和單點交叉方式。按照設置的交叉概率，對染色體的子串1和子串3進行PBX操作，對子串2進行單點交叉操作。

如圖4所示,PBX的操作步驟如下：①隨機選擇一對染色體(父代)中的幾個基因，位置可不連續，但兩條染色體被選位置相同。②生成初子代 1和初子代 2，使得父代中被選中的基因保持位置不變被遺傳到初子代 1和初子代 2中，其他基因位暫時空置。③先找出父代1(2)中選中的基因在父代2(1)中的位置，將其該位置上的基因刪除，再將剩余的基因按順序放入初子代1(2)中，即得到子代1(2)。

圖4 PBX操作示意圖

本文在進化過程中的變異操作主要包括次序逆轉變異和隨機變異。按照設置的變異概率，對染色體的子串1和子串3采用次序逆轉變異的方式。若經交叉后得到的子代染色體的子串1和子串3滿足次序逆轉變異的條件，則分別在子串1和子串3上隨機選擇兩個變異點，對變異點之間的基因段進行倒序排列；對子串2采用隨機變異的方式，即在子串2中選擇任意基因位進行變異，基因取值不超過加工人員的總數量。

當算法的最大迭代次數達到1 000時，算法終止并輸出結果。

3 算例分析

3.1 算例設置

目前還沒有PDIS的標準測試算例，本文構建的模型的加工環節為并行機調度問題，配送環節為VRPTW，因此借鑒關于VRPTW研究的Solomon算例中R101類數據。因為Solomon公開的研究數據均無量綱，所以本部分所有數據均無量綱。假設訂單加工時間服從均勻分布，～[2,5]，訂單的保質期在客戶時間窗結束時刻的基礎上隨機加減60。

NSGA Ⅱ的參數設置：種群規模為100，最大迭代次數為1 000，交叉概率為0.8，變異概率為0.2。為提高算法的收斂速度和效率，一開始不考慮產品交付時最低新鮮度約束，在算法迭代結束后再考慮該約束，具體表現為在所得的帕累托解集中剔除低于最低新鮮度的解。算法采用MATLAB 2016b編程實現，程序在核心參數為4核CPU，2.10 GHz主頻，16 GB內存和Windows 10操作系統的計算機上運行，其他實驗參數見表1。

表1 實驗參數

3.2 實驗結果與分析

3.2.1 考慮新鮮度和總成本的多目標生鮮品冷鏈配送聯合調度方案分析

以訂單規模為30、加工人員數量為3為例進行計算，算法運行10次。算例進化過程如圖5所示，其中總成本的進化曲線隨著迭代次數的增加呈現穩定下降的趨勢，新鮮度的進化曲線在迭代到150次左右已收斂到最優解附近，后又經過將近100次迭代跳出局部最優，說明NSGA Ⅱ在多目標求解過程中具有良好的搜索能力和收斂性。

a)總成本

對于實際的生鮮電商企業來說，總成本與新鮮度之間存在著相互制約的關系，增加配送車次可以在一定程度上減緩產品新鮮度的降低，但也意味著總成本的增加，反之亦然，難以找到使兩者均達到最優的解。因此，本文求解的是帕累托最優解集，見圖6。在帕累托最優解集中的解都是相對較優解，不能簡單地比較解的優劣。表2給出了從帕累托最優解集中隨機選擇的一個解(即其中一個多目標生鮮品冷鏈配送聯合調度方案)，其中在第2列“加工配送時間”中分別列出了各加工人員的加工結束時間和各車次訪問對應客戶點的時間。這個聯合調度方案的總成本為2 655.22，產品交付時的平均新鮮度為0.843，共需要發出6個車次。根據聯合調度方案繪制出配送路徑圖，見圖7。

圖6 帕累托最優解集

表2 多目標生鮮品冷鏈配送聯合調度方案

圖7 配送路徑圖

3.2.2 實驗結果對比分析

為測試算法的性能，分別利用NSGA Ⅱ與NSGA對所建模型進行計算和對比。實驗共設置3種情景：情景1的種群規模為100，最大迭代次數為800；情景2的種群規模為150，最大迭代次數為800；情景3的種群規模為150，最大迭代次數為1 000。在R101類數據中分別選取客戶規模為30和60的數據進行測試。NSGA Ⅱ與NSGA的計算結果見表3。

由表3可得，NSGA Ⅱ與NSGA得到的帕累托解的個數均隨著迭代過程中產生的鄰域解的個數的增加而增加，且計算時間均越來越長，但是NSGA Ⅱ的耗時比NSGA的短，說明NSGA II的計算效率高。在客戶規模為30的情景1下，與NSGA相比，用NSGAⅡ計算得到的總成本增加了5.73%，但新鮮度提高了9.06%；在客戶規模為30的情景3下，與NSGA相比，用NSGA Ⅱ計算得到的總成本減少了5.15%，但新鮮度降低了4.06%；在其他客戶規模和情景下，用NSGAⅡ計算得到總成本和新鮮度均優于用NSGA計算得到的結果，驗證了NSGAⅡ和本文所建模型的有效性。

表3 NSGA Ⅱ和NSGA計算結果和算法性能指標對比

為進一步探究本文模型和算法的適用場景，從調度范圍隨機均勻分布的R1實例和調度范圍較小的RC1實例中分別選取客戶規模為30、50、80和100的算例進行對比。將本文多目標優化模型與傳統的不考慮新鮮度的單目標生鮮品冷鏈配送聯合調度優化模型(簡稱“單目標優化模型”)進行對比，利用遺傳算法對單目標優化模型進行求解，得到的結果見表4。

表4 多目標優化模型與單目標優化模型結果對比

由表4可得，基于傳統單目標優化模型所得的總成本要略低于基于多目標優化模型所得的總成本，這是因為單目標優化模型不考慮新鮮度約束，所獲得的解可能是局部最優解。然而，從表4可以明顯看出，多目標優化模型對新鮮度的優化效果較好：基于單目標優化模型所得的總成本比基于多目標優化模型所得的總成本降低了2.18%～4.81%，但基于多目標優化模型的新鮮度結果比基于單目標優化模型的提高了5.03%～12.92%。這表明，生鮮電商企業在采用單目標優化模型時只需要略微提高經營成本就能夠得到較高的客戶滿意度，在越來越注重服務水平的生鮮電商行業中獲得更顯著的競爭優勢。由圖8可知：無論是R1的客戶類型還是RC1的客戶類型，隨著客戶規模的增加，多目標優化模型對新鮮度的優化效果更佳，說明本文提出的多目標優化模型更適合于客戶規模較大的場景；對調度范圍隨機均勻分布的R1實例的新鮮度優化率整體高于調度范圍較小的RC1實例的新鮮度優化率，這說明本文提出的多目標優化模型更適合調度范圍較大的場景。

圖8 本文多目標優化模型的新鮮度優化率

4 結 論

本文提出基于新鮮度最大和總成本最低的多目標生鮮品冷鏈配送聯合調度問題，考慮了產品的易腐性、配送延遲、交付時間窗、配送路線、訂單加工排序以及加工人員調度。對于這個復雜的問題，本文利用第二代非支配排序遺傳算法(NSGAⅡ)得到了滿足新鮮度最大和總成本最低的相對較優解，驗證了本文模型的有效性。同時實驗結果表明，本文所建的多目標優化模型在客戶規模和配送調度范圍較大的情景下優化效果更佳，這對生鮮電商企業在不同情景下的決策具有一定的參考價值。該模型是在假設可獲得的數據是確定的前提下提出的，沒有考慮實際活動中的不確定因素，因此在未來研究中可以在此基礎上考慮不確定性等情況。