文章概述

文章研究了城市物流背景下帶有第三方轉運設施的車輛路徑問題。與經典的車輛路徑問題不同，這些問題提供了將客戶需求交付給第三方轉運設施（如城市集散中心）的選擇，并收取一定的費用。為了解決這些挑戰，該研究提出了一種自適應大鄰域搜索（ALNS），其中嵌入了一個隨機變量鄰域下降作為局部搜索組件，并使用集合劃分問題來解決路由重組。

這篇論文介紹并研究了車輛路徑問題與轉運設施（VRPTF）的兩個新問題變體：帶有時間窗口和轉運設施的車輛路徑問題（VRPTWTF）以及帶有時間窗口和轉運設施的車隊規模和混合車輛路徑問題（FSMTWTF）。這些變體考慮了與位置有關的時間窗口和異構車隊。所提出的方法在現有文獻中的基準實例和新創建的實例上進行了測試，顯示出有希望的結果，并改進了現有算法。還提出了一個真實世界的研究，以了解轉運費用、訂單大小和異構車隊對轉運決策的影響。

研究背景

本文的研究背景集中在城市物流領域的車輛路徑問題，特別是涉及第三方轉運設施的問題。城市物流和最后一公里配送面臨諸多挑戰，如公眾對可持續性的日益關注、城市通行限制和不斷增長的配送量。為應對這些挑戰，物流服務提供商通常采用在轉運設施（如城市集結中心，UCCs）集中貨物的方式來提高城市貨運效率。城市集結中心定義為靠近城市區域的物流轉運設施，可跨公司整合城市貨運。盡管有關UCCs的研究眾多，且多個城市已實施了UCCs，但很少有研究將個別貨件是否外包給第三方轉運設施（如UCCs）的決策納入車輛路徑問題中。

問題介紹

文中提到的“帶時間窗口和轉運設施的車輛路徑問題”（VRPTWTF）是一種車輛路徑問題（VRP）的變體。在傳統的車輛路徑問題中，車輛從一個集散中心出發，直接將貨物配送到各個客戶處。然而，VRPTWTF引入了兩個重要的額外特征：時間窗口和轉運設施。

1. 時間窗口（Time Windows）：這指的是每個客戶地點可接收貨物的特定時間范圍。車輛必須在這個時間窗口內到達客戶地點，以完成貨物交付。時間窗口對路線規劃構成了額外的約束，因為它限制了車輛到達各地點的可能時間。

2. 轉運設施（Transshipment Facilities）：在VRPTWTF中，除了直接向客戶配送之外，還可以選擇將貨物先運送到第三方的轉運設施，例如城市集結中心（UCCs）。在這些轉運設施中，貨物可以進行重新整合或中轉，之后再由不同的車輛或方式最終配送到客戶手中。這種方法特別適用于城市物流，可以幫助緩解城市交通壓力、減少碳排放，并提高配送效率。

VRPTWTF的核心挑戰在于如何優化車輛路線和貨物分配，以在滿足時間窗口約束的同時，充分利用轉運設施的優勢。這包括決定哪些貨物應該直接送達客戶，哪些應該通過轉運設施，以及如何安排車輛路線，使得總成本最低，效率最高。

方法介紹

這篇論文詳細介紹了自適應大鄰域搜索(ALNS)的方法論，這是一種用于解決車輛路徑問題的元啟發式方法，其特點是通過移除和插入程序執行大規模移動。該算法涉及初始化參數，創建初始解決方案，然后通過移除和插入程序迭代地破壞和修復解決方案。還嵌入了局部搜索過程以進一步改進解決方案。

搜索空間和目標函數的設計考慮了在搜索過程中關于時間窗約束的不可行解。這是通過使用“時間松弛方案”來實現的，該方案允許車輛“時間倒流”以滿足時間窗約束，而這種時間扭曲會用于對目標函數進行懲罰。自適應懲罰參數會根據現有解的可行性進行調整。

算法中的移除程序包括各種啟發式方法，比如隨機移除、路徑移除、最差移除、歷史知識節點移除、肖移除、集群移除、與距離相關的移除、與時間相關的移除以及相鄰字符串移除。每個程序都有特定的策略來選擇從當前解決方案中移除哪些客戶請求。

The removal procedures in the adaptive large neighborhood search (ALNS) algorithm, as detailed in the paper, are designed to selectively remove customer requests from the current solution. These procedures play a crucial role in the algorithm’s iterative process of destroying and repairing solutions to find an optimal route. Each removal procedure has its unique strategy and criteria for selecting which customer requests to remove. Here’s a summary of each:

1. Random Removal: This heuristic randomly removes customer requests from a given solution using a uniform probability distribution.

2. Route Removal: In this heuristic, a random route is selected, and up to a certain number of customer requests from the route are randomly removed until the desired number of customers is reached.

3. Worst Removal: Introduced by Ropke and Pisinger (2006a), this heuristic removes customer requests that contribute significantly to the objective function’s cost. It calculates the savings of removing each customer request, sorting them in descending order, and then removing them in a controlled manner.

4. Historical Knowledge Node Removal: This heuristic utilizes historical data, removing customer requests with the highest difference between their current costs and their historically lowest costs.

5. Shaw Removal: Also known as related removal, this method defines the similarity between two customer requests based on several characteristics, including demand difference, distance, time window difference, and shared transshipment facilities. Customer requests are then removed based on these similarities.

6. Cluster Removal: Developed by Ropke and Pisinger (2006b), this method aims to remove an entire cluster of customer requests. It involves partitioning the customer requests in a route into clusters and then removing one of these clusters.

7. Distance-Related Removal: Also known as radial removal, this heuristic removes customer requests that are geographically close to each other.

8. Time-Related Removal: This method removes customer requests that are related in terms of the time they are served.

9. Adjacent String Removal: Introduced by Christiaens and Vanden Berghe (2020), this approach removes adjacent strings of customer requests, aiming to be more efficient by potentially eliminating detours in the destroyed route.

Each of these removal procedures is designed to diversify the search process and avoid local optima by creating variations in the solutions for further exploration.

自適應大鄰域搜索（ALNS）算法中的移除過程，如論文中所述，旨在有選擇地從當前解中移除客戶請求。這些過程在算法的迭代過程中破壞和修復解以找到最優路線起著關鍵作用。每個移除過程都有其獨特的策略和標準來選擇要移除的客戶請求。以下是每個策略的概述：

1. 隨機移除：此啟發式使用均勻概率分布從給定解中隨機移除客戶請求。

2. 路線移除：在此啟發式中，隨機選擇一個路線，并從該路線中隨機移除一定數量的客戶請求，直到達到所需的客戶數量。

3. 最差移除：由Ropke和Pisinger（2006a）引入，此啟發式移除對目標函數成本產生顯著影響的客戶服務請求。它計算移除每個客戶服務請求的節省，按降序排序，然后以受控的方式移除它們。

4. 歷史知識節點移除：此啟發式利用歷史數據，移除具有當前成本與歷史最低成本之間最高差異的客戶請求。

5. Shaw移除：也稱為相關移除，此方法根據幾個特征定義兩個客戶服務請求之間的相似性，包括需求差異、距離、時間窗口差異和共享運輸設施。然后根據這些相似性移除客戶服務請求。

6. 集群移除：由Ropke和Pisinger（2006b）開發，此方法旨在移除整個客戶服務請求集群。它涉及將路線上的客戶服務請求劃分為集群，然后移除其中一個集群。

7. 距離相關移除：也稱為徑向移除，此啟發式移除地理位置相近的客戶請求。

8. 時間相關移除：該方法移除與提供服務的時間相關的客戶服務請求。

9. 相鄰字符串移除：由Christiaens和Vanden Berghe（2020）引入，此方法移除相鄰的客戶請求字符串，旨在通過可能消除被破壞路線上的繞路來提高效率。

每個移除過程都設計為多樣化搜索過程，并通過在解決方案中創建變化以避免局部最優解，從而進一步探索。

插入程序用于將已刪除的客戶請求重新整
合到解決方案中。這些程序包括隨機順序最佳插入、需求順序最佳插入、最遠優先最佳插入和最近優先最佳插入。這些程序考慮需求、到倉庫的距離和其他標準來確定最佳插入位置。

本地搜索過程通過將ALNS方法與隨機變鄰域下降（RVND）相結合來加強搜索。這涉及選擇鄰域并在解決方案中尋找改進。該算法還使用各種路由間和路由內鄰域來實現更好的局部最優解。

研究結論與討論

最后，本文討論了一個由混合整數規劃（MIP）求解的集合分割問題（SP）模型。該模型有助于在確保每個客戶請求在解決方案中僅包含一次的同時，最小化路線成本之和。該模型針對車隊規模和混合問題變體進行了調整。