基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化問題

王勇，王靜媛，茍夢圓，羅思妤

綠色包裝與循環經濟

基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化問題

王勇，王靜媛，茍夢圓，羅思妤

（重慶交通大學，重慶 400074）

針對當前生鮮商品配送效率低和成本高等問題，采用車倉溫度可控的多倉車輛作為配送裝備，并結合時間窗等約束，研究基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化問題。建立最小化物流運營成本和車輛使用數量的雙目標模型，然后設計基于Clarke-Wright節約算法的非支配排序遺傳算法（CW-NSGA-Ⅱ）求解該模型。利用CW節約算法生成初始配送路徑，以提高初始解的質量，并設計精英迭代策略，以提高算法的尋優性能?；诟倪M的Solomon算例，將文中所提算法與多目標粒子群算法、多目標蟻群算法、多目標遺傳算法進行了對比，驗證了CW-NSGA-Ⅱ算法的求解性能。結合實例，對多倉車輛使用數量、溫控成本和運營成本等指標進行對比分析，結果表明，經優化后多倉車輛使用數量減少了35.7%，溫控成本減少了39.2%，物流運營總成本減少了47.7%。文中所提模型和算法能夠有效優化配送路徑，降低運營成本，為構建高效率、低成本的生鮮配送網絡提供了理論支持和決策參考。

生鮮商品配送；多倉溫控；時間窗；CW-NSGA-Ⅱ

近年來，隨著電子商務的發展和人民生活水平的提高，生鮮商品配送服務逐步向高品質、精細化、個性化方向發展，客戶不再局限于單一的商品需求[1]。然而，傳統的生鮮配送方式通常采用單車倉冷藏車進行服務，無法一次性滿足客戶現階段多種商品的需求，導致配送效率較低。此外，生鮮商品具有時效性、易腐性，不合理的配送路徑規劃（如交叉配送、遠距離配送等）會延長配送時間，增大生鮮商品的腐壞概率，從而增加配送成本和溫控成本。運輸裝備的合理選用和配送路徑的有效規劃直接關系到生鮮商品配送服務效率的提升和運營成本的降低。應用多倉配送車代替單倉配送車作為運輸裝備，通過合理設置不同車倉的溫度、規劃配送路徑能夠滿足客戶的多樣化生鮮商品需求，并能夠有效縮短配送距離和配送時間，提高配送服務效率，減少生鮮商品的損壞，因此研究基于時間窗和多倉溫控的生鮮商品配送車輛路徑問題對于推動生鮮配送行業的高質量發展具有重要意義。國內外學者從多倉配送車輛路徑優化問題和生鮮商品配送路徑優化問題兩方面進行了一系列研究工作。

針對多倉配送車輛路徑優化問題，20世紀80年代，Christofides等[2]以車輛路徑問題變體的形式提出了多倉配送車輛路徑優化問題。Coelho、Laporte[3]將多倉車輛路徑問題分為4類，并針對每類問題建立了優化模型。孫麗君等[4]研究了不同橫向轉運方式下的成品油多倉配送路徑優化問題，建立了配送成本最小化的數學模型，應用節約算法求解該模型，有效降低了企業的配送成本。Chen等[5]研究了易腐商品的多倉配送車輛路徑問題，以包含固定成本和油耗成本的總成本最小化為目標，設計了自適應大鄰域搜索算法。Ostermeier等[6]研究了零售商品配送問題，研究發現，相較于單車倉車隊，使用包含單車倉和多車倉的混合車隊進行配送，可以節約高達30%的運營成本。王淑云等[7]研究了隨機需求下的蓄冷式多溫共配問題，建立了總成本最小化模型，并分別設計了蟻群算法和動態規劃算法。由上述文獻可知，相較于單倉配送車輛，使用多倉配送車輛能夠有效降低運營成本。在生鮮商品配送方面，如何合理規劃多倉配送車輛路徑有待進一步研究。

針對生鮮商品配送路徑優化問題，李軍濤等[8]構建了以配送總成本最小化和客戶滿意度最大化為目標的多車型路徑優化模型，并采用自適應遺傳模擬退火算法求解。Zulvia等[9]以運營成本、貨損成本、碳排放量最小化和顧客滿意度最大化為目標，設計了多目標梯度進化算法。梁桂云等[10]針對當前生鮮商品配送過程中成本高、配送效率低下和商品損耗大等問題，以新鮮度最大化和總成本最小化為目標，建立了生鮮商品配送聯合調度優化模型，并使用非支配排序算法進行求解。Liu等[11]以配送成本和碳排放成本最小化為目標，建立了生鮮企業橫向合作模式下的綠色車輛路徑優化模型，通過模擬退火算法進行路徑優化，顯著降低了目標函數值。上述多目標函數構建和混合智能算法設計為研究基于時間窗和多倉溫控的生鮮商品配送問題提供了切入方法。

基于以上情況，文中構建了最小化運營成本和配送車輛使用數量的雙目標優化模型，設計了基于節約算法的非支配排序遺傳算法求解模型。結合實例，對比分析了不同車倉數量下的運營成本、溫控成本和車輛使用數量等指標，為帶時間窗和多倉溫控的生鮮商品配送車輛路徑優化問題提供了新思路。

1 問題描述

針對客戶多種溫控區間的生鮮商品需求，多倉配送車從配送中心出發，為沿途的客戶提供服務，服務完成后返回配送中心。多倉配送車可以為具有多種生鮮商品需求的客戶提供服務，減少了配送次數和車輛使用數量。在車輛路徑規劃時，根據生鮮商品的類型，將其安排在合適溫度區間的車倉和該車輛的配送路線中，從而減少溫控成本，提高車輛的裝載利用率。結合客戶的地理位置、服務時間窗和生鮮商品需求類型等信息，合理規劃多倉配送車輛路徑，可減少配送車輛的使用數量，降低時間窗懲罰成本?；跁r間窗和多倉溫控的生鮮商品配送車輛路徑優化前后對比如圖1所示。

優化前的配送路徑和車倉裝載情況如圖1a所示，在配送網絡中路徑交叉冗余、客戶時間窗被違反的現象較多，部分多倉配送車的車倉裝載商品較少、剩余空間較大，增加了車輛使用數量，提高了配送成本、時間窗懲罰成本。優化后的配送路徑和車倉裝載情況如圖1b所示，根據網絡中各個客戶的生鮮商品需求，將同類溫度控制區間的生鮮需求安排給同一多倉車輛進行服務，并合理規劃該多倉車輛的路徑，使其盡可能實現多倉滿載，且減少客戶的時間窗違反現象，進而降低配送成本和時間窗懲罰成本。

圖1 基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化前后對比

2 模型建立

2.1 模型假設

生鮮商品配送網絡中包含1個配送中心、多輛多倉配送車和一系列客戶點。配送中心根據客戶的地理位置分布和生鮮商品需求數量、類型對多倉配送車進行配送調度[12]。模型假設如下。

1）多倉配送車輛均為同一車型，1輛車配備了多個車倉，每個車倉的空間劃分相同，但每個車倉可設置不同的溫度區間。

2）在配送過程中，不考慮車輛的導航路徑及道路運輸實際場景對車輛行駛速度的影響，并假定多倉配送車行駛速度相同且恒定[13]。

3）不考慮多倉配送車在客戶點的服務時間。

4）客戶時間窗懲罰成本由車輛到達客戶點的時間和客戶點需求量決定[14]。

2.2 符號定義

這里涉及的變量及其定義如表1所示。

2.3 模型構建

以物流運營成本1最小化和多倉配送車使用數量2最小化為目標，建立了基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化模型，見式（1）～（2）。

表1 變量定義

Tab.1 Variable definition

約束條件見式（8）～（20）。其中，式（8）表示每個客戶只能被1輛多倉配送車訪問1次。式（9）表示配送節點流量守恒。式（10）表示消除子回路。式（11）表示多倉配送車的使用數計算方式。式（12）表示車倉裝載量不超過該車倉的最大載質量。式（13）表示任意一輛多倉配送車的行駛距離不超過該車輛的最大行駛距離。式（14）表示客戶的每種生鮮商品需求只能由1輛多倉配送車中的1個車倉提供。式（15）表示多倉配送車到達節點的時間均在其服務時間窗內。式（16）～（17）表示多倉配送車到達節點的時間約束。式（18）～（20）表示決策變量約束。

3 CW-NSGA-Ⅱ算法設計

這里設計了基于Clarke-Wright節約算法的非支配排序遺傳算法，以求解基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化問題。首先，利用Clarke-Wright（CW）節約算法生成初始路徑。然后，應用非支配排序遺傳算法（NSGA-Ⅱ）進行車輛路徑的迭代優化，并引入精英迭代策略，從而提高算法全局尋優能力。最后，輸出帕累托最優解集。CW-NSGA-Ⅱ算法流程如圖2所示。其中，表示算法迭代次數，max表示算法最大迭代次數，表示精英迭代次數，max表示最大精英迭代次數。

圖2 CW-NSGA-Ⅱ算法流程

3.1 初始種群構造

采用整數編碼方式[17]構造染色體。假設該生鮮商品配送網絡中共有6個客戶，經過整數編碼，染色體表示為（1，2，3，4，5，6）。根據約束對該染色體解碼，可行解表達為（0，1，2，0，3，4，0，5，6，0），其中0表示配送中心。該可行解共有3條生鮮商品配送路徑：配送路徑1為0→1→2→0；配送路徑2為0→3→4→0；配送路徑3為0→5→6→0。初始種群的構造應用CW節約算法[18]，具體步驟如下。

1）將個客戶分別與配送中心相連，構成個閉合回路0→→0（=1，2，3，…，）。

2）對于任意2個客戶點組成的連接點對(,)，根據式（21）計算其節約里程值(,)。其中，c為節點與節點之間的距離。

3）將所有(,)按降序排列。

4）設置1條空路徑，根據(,)的排列順序，逐個考察各客戶連接點對(,)。若滿足客戶點和不在一條配送路徑上且均與配送中心相鄰，則將連接點對(,)插入路徑中。當該路徑違反載重約束或配送中心的時間窗約束時，則關閉該條配送路徑，重新開啟一條空路徑。重復步驟4），直至所有客戶被插入配送路徑中。

5）輸出初始種群。

3.2 部分映射交叉

部分映射交叉常被用于車輛路徑問題求解，可有效避免算法陷入局部最優解[19-20]。首先，通過錦標賽選擇2條父代染色體1和2，然后隨機選擇染色體上的基因位置作為交叉區域進行局部交叉，最后進行沖突測試。如果染色體中出現基因重復，則根據交換的基因片段建立映射關系，從而保證子代基因無沖突。部分映射交叉操作如圖3所示。

由圖3a可知，染色體1和2執行部分映射交叉后，生成染色體1、2。對1、2解碼后生成配送方案。其中，1中有2條配送路徑，分別為：0→3→5→0，0→1→6→4→2→0；2中有2條配送路徑，分別為：0→2→4→1→0，0→3→5→6→0。

3.3 多點變異

通過錦標賽選擇、部分映射交叉操作后，利用多點變異擴大解空間[21]。首先根據變異概率選擇父代染色體，然后在選出的父代染色體中隨機選擇2個基因進行交換，剩下的基因再隨機生成，最后檢查染色體中是否存在重復基因，若“是”，則移除重復基因后再生缺失基因。多點變異操作如圖4所示。

圖3 部分映射交叉操作示意圖

圖4 多點變異操作示意圖

3.4 帕累托優化解選擇

帕累托優化解的選擇主要依據解的非支配層級及擁擠度[22]，非支配層級={1,2,3, …,}，具體步驟如下。

1）對種群中每個個體設置2個參數、，其中表示種群中支配個體的解數量，表示被個體所支配的解集合。

2）設置=1，將=0的個體歸入。

3）對于中的每個個體，遍歷其所支配的解集，將中每個個體的減去1。

4）令=+1，將=0的解歸入。

5）重復步驟3）、4），直至所有個體均被劃分等級。

為了衡量同一層級中個體的優劣，將每層級邊界上個體的擁擠度設置為無窮大，利用式（22）、（23）計算各層級中剩余個體的擁擠度。

帕累托優化解的選擇過程如圖5所示。種群中個體的非支配層級優于個體的非支配層級，所以個體優于個體；個體與個體處于同一非支配層級中，但個體的擁擠度大于個體的擁擠度，則個體優于個體。

3.5 算法比較

為了驗證CW-NSGA-Ⅱ算法的有效性，將CW- NSGA-Ⅱ算法與多目標粒子群算法（MOPSO）[23]、多目標蟻群算法（MOACO）[24]、多目標遺傳算法（MOGA）[25]進行對比分析，算法的相關參數設置如表2所示。

圖5 帕累托優化解選擇

在Solomon數據集[26]中選取15組數據進行改進，增加了客戶需求的生鮮商品種類及質量，算例數據特征如表3所示。每組算例分別計算10次，選取最優物流運營成本、多倉配送車使用數量和求解時間進行對比，具體結果如表4所示。

如表4所示，首先在運營成本方面，CW-NSGA-Ⅱ算法計算結果均值為14 424.5元，相較于MOPSO、MOACO、MOGA，分別降低了11.7%、10.3%、11.2%；其次，在多倉配送車輛使用數量方面，相較于其他算法，CW-NSGA-Ⅱ的計算結果均值減少了1輛；最后，在算法求解時間上，CW-NSGA-Ⅱ的平均求解時間為164.9 s，而MOPSO、MOACO、MOGA的平均求解時間分別為175.2、174.0、175.4 s。通過檢驗與比較，結果顯示，CW-NSGA-Ⅱ算法與其他3種算法存在顯著性差異。由此可見，在求解文中所研究的問題方面，CW-NSGA-Ⅱ算法具有更好的尋優能力。

表2 算法參數設置

Tab.2 Parameter settings

表3 算例數據特征

Tab.3 Characteristics of the datasets

表4 不同算法優化結果對比

Tab.4 Comparison of optimization results of different algorithms

4 實例分析

4.1 相關數據

以重慶市某生鮮商品配送中心（D）所服務的100個客戶點（1～100）為研究對象，配送中心與客戶點的地理位置分布如圖6所示。選取生鮮商品配送中心的部分商品類型，結合生鮮食品要求的溫度分區，并考慮運輸過程中的溫控成本，將多倉配送車劃分為3個車倉，并設置相應的溫控區間，如配送櫻桃、葡萄、玉米等蔬菜、水果的溫控區間為1～5 ℃，魚、蝦等海鮮商品的溫控區間為?5～0 ℃，冷凍水餃、冰激凌等冷凍商品的溫控區間為?10～?6 ℃。具體信息如表5所示，相關參數設置[27-28]如表6所示。

圖6 配送中心與客戶的地理分布

表5 生鮮商品溫控區間及商品種類

Tab.5 Temperature control ranges and product categories

4.2 優化結果及分析

針對基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化問題，以最小化物流運營成本和多倉配送車輛使用數為目標，應用CW-NSGA-Ⅱ算法對模型進行求解。優化前后運營成本、多倉配送車使用數量及溫控成本等指標變化情況如表7所示。

表6 參數設置

Tab.6 Parameter settings

由表7可知，優化后，配送車輛的使用數減少了5輛，運營成本減少了14 093.4元，溫控成本減少了1 847.5元，懲罰成本減少了89.3%，配送距離縮減了49.0%?；跁r間窗和多倉溫控的生鮮商品配送車輛路徑優化方案如表8和圖7所示。

如圖7a所示，在優化后配送車輛數減少了5輛，僅需要9輛多倉配送車為所有客戶點提供服務。如圖7b所示，9輛多倉配送車中有5輛處于滿載狀態，其余4輛多倉配送車的車倉剩余裝載空間均小于18%，實現了車倉容量的合理利用。

4.3 分析與討論

進一步探討了不同車倉數目對各項運營指標的影響，分別研究了3種情形。結果如表9和圖8所示。

1）多倉配送車有3個車倉，將車倉溫度區間分別設置為1～5 ℃、?5～0 ℃、?10～?6 ℃。

2）相較于情形1，將多倉配送車增加1個1～5 ℃的車倉，共有4個車倉。

3）相較于情形2，將多倉配送車增加1個?5～0 ℃的車倉，共有5個車倉。

表7 基于時間窗和多倉溫控的生鮮商品配送車輛路徑優化結果前后對比

Tab.7 Comparison between fresh commodity distribution routes based on time windows and multi-compartment temperature control before and after the optimization

表8 優化后車輛配送方案

圖7 配送路徑

表9 不同車倉下的優化結果對比

Tab.9 Comparison of optimization results under different compartment numbers

圖8 不同車倉下的各項指標結果對比

如表9和圖8所示，以車倉外溫度為20 ℃和3個車倉為研究基準，比較了不同車倉數量對各項運營指標的影響。當車倉數量增至4個時，多倉配送車的使用數量不變，而溫控成本增加了984.9元，行駛成本增加了1 313.7元，運營成本增加了2 848.6元。當車倉數量增至5個時，多倉配送車的使用數量保持不變，而溫控成本增加了1 394.1元，懲罰成本增加了1 200元，運營成本增加了3 800.3元。結果顯示，在車倉外溫度為20 ℃的情況下，當配送車輛具有3個車倉時，路徑優化結果優于其他2種場景。

5 結語

研究了基于時間窗和多倉溫控的生鮮商品配送車輛路徑問題。首先，建立了最小化運營成本和多倉配送車使用數量的雙目標優化模型。其次，設計了CW-NAGA-Ⅱ算法，以求解該模型，通過CW節約算法生成初始種群，并設計了精英迭代策略，以提高算法的尋優性能。最后，將CW-NAGA-Ⅱ算法與MOPSO、MOACO、MOGA進行比較分析，驗證了CW-NAGA-Ⅱ算法的有效性。

以重慶某生鮮商品配送網絡為例，對配送路徑進行優化，提出了相應的優化方案。結果表明，優化后多倉配送車使用數量減少了35.7%，運營成本縮減了47.7%，溫控成本從4 710.1元降至2 862.6元。此外，對比分析了不同車倉數量場景下的優化結果。結果顯示，在生鮮商品需求量一定的情況下，選擇合適車倉數目的多倉配送車可以有效降低運營成本和車輛使用數。文中研究為基于時間窗和多倉溫控的生鮮商品配送車輛路徑問題研究提供了新的切入點。

[1] 張文禮. 國務院辦公廳印發《“十四五”冷鏈物流發展規劃》[N]. 中國質量報, 2021-12-14(001).

ZHANG W L. Issued by The General Office of the State Council "14th Five-Year Plan" Cold Chain Logistics Development Plan[N]. China Quality Daily, 2021-12-14(001).

[2] CHRISTOFIDES N, MINGOZZI A, TOTH P. The Vehicle Routing Problem[J]. Revue Frangaise d'Informatique et de Recherche Opérationnelle, 1976, 10(2): 55-70.

[3] COELHO L C, LAPORTE G. Classification, Models and Exact Algorithms for Multi-Compartment Delivery Problems[J]. European Journal of Operational Research, 2015, 242(3): 854-864.

[4] 孫麗君, 周雅嫻, 石海洋, 等. 多種橫向轉運配送方式下的成品油配送方案優化方法[J]. 系統管理學報, 2020, 29(6): 1177-1187.

SUN L J, ZHOU Y X, SHI H Y, et al. An Approach to Optimizing Distribution Plans of Oil Products for Multiple Distribution Schemes with Lateral Transshipment[J]. Journal of Systems & Management, 2020, 29(6): 1177-1187.

[5] CHEN L, LIU Y, LANGEVIN A. A Multi-Compartment Vehicle Routing Problem in Cold-Chain Distribution[J]. Computers & Operations Research, 2019, 111: 58-66.

[6] OSTERMEIER M, HüBNER A. Vehicle Selection for a Multi-Compartment Vehicle Routing Problem[J]. European Journal of Operational Research, 2018, 269(2): 682-694.

[7] 王淑云, 孫虹, 牟進進. 隨機需求下蓄冷式多溫共配優化模型[J]. 系統管理學報, 2018, 27(4): 712-721.

WANG S Y, SUN H, MOU J J. Optimization of Cold-Storage Multi-Temperature Joint Distribution Based on Stochastic Demands[J]. Journal of Systems & Management, 2018, 27(4): 712-721.

[8] 李軍濤, 劉明月, 劉朋飛. 生鮮農產品多車型冷鏈物流車輛路徑優化[J]. 中國農業大學學報, 2021, 26(7): 115-123.

LI J T, LIU M Y, LIU P F. Route Optimization of Multi-Vehicle Cold Chain Logistics for Fresh Agricultural Products[J]. Journal of China Agricultural University, 2021, 26(7): 115-123.

[9] ZULVIA F E, KUO R J, NUGROHO D Y. A Many-Objective Gradient Evolution Algorithm for Solving a Green Vehicle Routing Problem with Time Windows and Time Dependency for Perishable Products[J]. Journal of Cleaner Production, 2020, 242: 118428.

[10] 梁桂云, 陳淮莉. 基于NSGA Ⅱ的生鮮品冷鏈配送聯合調度優化[J]. 上海海事大學學報, 2022, 43(3): 28-35.

LIANG G Y, CHEN H L. Integrated Scheduling Optimization of Fresh Food Cold Chain Distribution Based on NSGA Ⅱ[J]. Journal of Shanghai Maritime University, 2022, 43(3): 28-35.

[11] LIU G K, HU J Y, YANG Y, et al. Vehicle Routing Problem in Cold Chain Logistics: A Joint Distribution Model with Carbon Trading Mechanisms[J]. Resources, Conservation and Recycling, 2020, 156: 104715.

[12] 楊森炎, 寧連舉, 商攀. 基于時空狀態網絡的電動物流車輛路徑優化方法[J]. 交通運輸系統工程與信息, 2021, 21(2): 196-204.

YANG S Y, NING L J, SHANG P. Electric Logistics Vehicle Routing Optimization Based on Space-Time-State Network[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(2): 196-204.

[13] 李想, 閔德權, 張祺. 隨機需求下半開放式冷鏈物流車輛路徑優化[J]. 包裝工程, 2022, 43(7): 160-169.

LI X, MIN D Q, ZHANG Q. Routing Optimization of Semi-Open Cold-Chain Logistics Vehicle under Random Demand[J]. Packaging Engineering, 2022, 43(7): 160-169.

[14] WANG Y, ZHANG J, ASSOGBA K, et al. Collaboration and Transportation Resource Sharing in Multiple Centers Vehicle Routing Optimization with Delivery and Pickup[J]. Knowledge-Based Systems, 2018, 160: 296-310.

[15] XIAO Y Y, ZHAO Q H, KAKU I, et al. Development of a Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem[J]. Computers & Operations Research, 2012, 39(7): 1419-1431.

[16] 王思洪, 梁承姬, 張悅. 帶溫度決策與質量管理的冷鏈物流配送優化[J]. 制造業自動化, 2023, 45(4): 125-130.

WANG S H, LIANG C J, ZHANG Y. Optimization of Cold Chain Logistics Distribution with Temperature Decision and Quality Management[J]. Manufacturing Automation, 2023, 45(4): 125-130.

[17] 張異. 包裝廢棄物回收車輛路徑問題的改進遺傳算法[J]. 包裝工程, 2018, 39(17): 147-152.

ZHANG Y. Improved Genetic Algorithm for Vehicle Routing Problem in Packaging Waste Recycling[J]. Packaging Engineering, 2018, 39(17): 147-152.

[18] 王勇, 羅思妤, 鎮璐, 等. 考慮違約追償和損失補償的多中心集配網絡聯盟優化問題[J]. 中國管理科學, 2023, 31(3): 10-25.

WANG Y, LUO S Y, ZHEN L, et al. Multi-Center Pickup and Delivery Network Alliance Optimization Considering Default Penalties and Loss Compensations for Breach of Contract[J]. Chinese Journal of Management Science, 2023, 31(3): 10-25.

[19] 劉凡, 張惠珍, 周迅. 帶模糊需求的開放式選址路徑問題的混合離散蘑菇繁殖算法[J]. 計算機應用研究, 2021, 38(3): 738-744.

LIU F, ZHANG H Z, ZHOU X. Hybrid Discrete Mushroom Reproduction Algorithm for Solving Open Location-Routing Problem with Fuzzy Demands[J]. Application Research of Computers, 2021, 38(3): 738-744.

[20] ?LHAN ?. An Improved Simulated Annealing Algorithm with Crossover Operator for Capacitated Vehicle Routing Problem[J]. Swarm and Evolutionary Computation, 2021, 64: 100911.

[21] SA? T. PVS: A New Population-Based Vortex Search Algorithm with Boosted Exploration Capability Using Polynomial Mutation[J]. Neural Computing and Applications, 2022, 34(20): 18211-18287.

[22] ASGHARI M, MIRZAPOUR AL-E-HASHEM S M J. A Green Delivery-Pickup Problem for Home Hemodialysis Machines; Sharing Economy in Distributing Scarce Resources[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 134: 101815.

[23] HAN H G, ZHANG L L, HOU Y, et al. Adaptive Candidate Estimation-Assisted Multi-Objective Particle Swarm Optimization[J]. Science China Technological Sciences, 2022, 65(8): 1685-1699.

[24] 趙志學, 李夏苗, 周鮮成, 等. 考慮交通擁堵的冷鏈物流城市配送的GVRP研究[J]. 計算機工程與應用, 2020, 56(1): 224-231.

ZHAO Z X, LI X M, ZHOU X C, et al. Research on Green Vehicle Routing Problem of Cold Chain Distribution: Considering Traffic Congestion[J]. Computer Engineering and Applications, 2020, 56(1): 224-231.

[25] PIERRE D M, ZAKARIA N. Stochastic Partially Optimized Cyclic Shift Crossover for Multi-Objective Genetic Algorithms for the Vehicle Routing Problem with Time-Windows[J]. Applied Soft Computing, 2017, 52: 863-876.

[26] 文展, 唐康健, 李文藻. 一種改進粒子群優化算法在車輛路徑問題的應用研究[J]. 重慶郵電大學學報(自然科學版), 2020, 32(5): 891-897.

WEN Z, TANG K J, LI W Z. Research on Application of Vehicle Routing Problem Using an Enhanced Particle Swarm Optimization[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2020, 32(5): 891-897.

[27] 范厚明, 吳嘉鑫, 耿靜, 等. 模糊需求與時間窗的車輛路徑問題及混合遺傳算法求解[J]. 系統管理學報, 2020, 29(1): 107-118.

FAN H M, WU J X, GENG J, et al. Hybrid Genetic Algorithm for Solving Fuzzy Demand and Time Windows Vehicle Routing Problem[J]. Journal of Systems & Management, 2020, 29(1): 107-118.

[28] 方文婷, 艾時鐘, 王晴, 等. 基于混合蟻群算法的冷鏈物流配送路徑優化研究[J]. 中國管理科學, 2019, 27(11): 107-115.

FANG W T, AI S Z, WANG Q, et al. Research on Cold Chain Logistics Distribution Path Optimization Based on Hybrid Ant Colony Algorithm[J]. Chinese Journal of Management Science, 2019, 27(11): 107-115.

Fresh Commodity Distribution Vehicle Routing Optimization Based on Time Windows and Multi-compartment Temperature Control

WANG Yong, WANG Jingyuan,GOU Mengyuan,LUO Siyu

(Chongqing Jiaotong University, Chongqing 400074, China)

Aiming at the inefficient and high-cost fresh commodity distribution, the work aims to study the fresh commodity distribution route optimization based on time windows and multi-compartment temperature control by adopting multi-compartment vehicles with temperature controlled compartments as distribution equipment and applying time windows and other constraints. Firstly, the bi-objective model was established to minimize logistics operating cost and the number of vehicles. Then, the non-dominated sorting genetic algorithm based on the Clarke-Wright saving algorithm (CW-NSGA-Ⅱ) was designed to solve the model. Among them, the initial population was generated by the Clarke-Wright saving algorithm, which improved the quality of the initial solution, and an elite iterative strategy was designed to improve the optimization performance.Based on the improved Solomon example, the proposed algorithm was compared with the multi-objective particle swarm algorithm, multi-target ant colony algorithm and multi-target genetic algorithm, verifying the solution performance of the CW-NSGA-Ⅱ. Combined with a case study, the indicators such as the number of multi-compartment vehicles, temperature control costs and operating costs were compared and analyzed. The results showed that the number of optimized multi-compartment vehicles was reduced by 35.7%, the temperature control cost was reduced by 39.2%, and the total operating cost was reduced by 47.7%. The proposed model and algorithm can effectively optimize the distribution route, reduce the total operating cost, and provide theoretical support and decision-making reference for the construction of the efficient and low-cost fresh distribution network.

fresh commodity distribution; multi-compartment temperature control; time window; CW-NSGA-Ⅱ

F570；TB485.3

A

1001-3563(2024)05-0263-13

10.19554/j.cnki.1001-3563.2024.05.032

2023-09-28

國家自然科學基金（72371044，71871035）；重慶市教委科學技術研究重大項目(KJZD-M202300704)；重慶市自然科學基金面上項目（CSTB2022NSCQ-MSX0535）；巴渝學者青年項目（YS2021058）