如今，城市化的滾滾車輪與電子商務的蓬勃發展，為我們帶來了前所未有的便利，但也帶來了日益嚴峻的挑戰：街道上川流不息的車輛不僅加劇了交通擁堵，其排放的溫室氣體也成為環保的隱憂。與此同時，線上購物催生了海量的輕型包裹，傳統的貨車配送模式在面對這些“小件”時顯得有些“大材小用”，效率低下且成本高昂。人們曾寄希望于“共享”模式——例如網約車——能夠減少路面車輛總數，但現實卻令人深思。研究表明，在歐洲和美國，大量網約車行程實際上是空載的“空駛”（deadheading）或在等待訂單，這反而增加了行駛里程和碳排放。另一邊，城市快遞的“最后一公里”配送也面臨著效率與成本的瓶頸。有沒有一種辦法，能像魔術一樣，將這兩個看似不相干的難題結合起來，化“問題”為“解決方案”呢？

共享搭乘（Share-a-Ride Problem, SARP）的概念應運而生。其核心思想是，讓出租車在運送乘客的同時，利用車內的閑置空間順路捎帶包裹，從而實現“客貨混載”，提高車輛利用效率，減少空駛，最終達到節能減排、降低城市物流成本的雙重目的。然而，理想很豐滿，現實卻很“骨感”。早期的SARP模型允許為了服務包裹而對乘客行程進行“繞行”，但這嚴重影響了乘客的出行體驗。研究表明，行程中的繞行和額外停靠會顯著降低乘客對拼車服務的接受度。因此，如何在不打擾乘客、禁止其行程繞路的前提下，高效地整合包裹運輸，成為了一個亟待解決的關鍵問題。此外，SARP是經典“按需響應交通問題”（Dial-a-Ride Problem, DARP）的擴展，已知是NP-hard的難題，現有的精確算法只能求解非常小規模的算例，開發能夠有效求解更大規模問題的先進算法至關重要。

為此，由Ana Beatriz Herthel、Teobaldo Bulh?es、Anand Subramanian和Richard F. Hartl組成的研究團隊，在《Computers & Operations Research》上發表了他們的最新成果。他們研究了一個網約車系統中的SARP變體，該變體嚴格禁止乘客繞行，并將乘客服務置于最優先地位。本研究的首要貢獻是設計了一個針對該SARP變體的分支-切割-定價（Branch-Cut-and-Price, BCP）算法。這是首批用于求解SARP的BCP算法之一，集成了多種現代技術，包括用于求解定價子問題的高效標簽算法、兩階段強分支、內存有限的一階秩割（rank-1 cuts with limited memory）以及ng-路徑（ng-paths）技術。其次，研究團隊改造并應用了一個當前最先進的多車場異質DARP數學啟發式（matheuristic）方法，為研究的問題生成高質量的初始解（primal bounds），這些解被用來提升BCP算法的性能。第三個亮點是，他們首次對SARP（也是對所有取送問題的首批之一）進行了實例空間分析（Instance Space Analysis, ISA），以評估不同實例特征如何影響問題的求解難度。最后，研究通過評估請求的起訖點距離和服務時間窗長度對空駛和包裹服務比例的影響，為客貨聯合運輸的服務質量提供了新的見解。

為了開展這項研究，作者們主要運用了以下幾類關鍵技術方法：首先是數學建模與優化算法，構建了禁止繞行SARP的緊湊數學模型，并以此為基礎設計了核心的分支-切割-定價精確求解框架，其中定價子問題通過動態規劃中的標簽算法高效處理。其次是啟發式算法設計，通過改造一個已有的、針對多車場異質DARP的數學啟發式方法，快速獲得高質量可行解，為精確算法提供上界。再者是計算實驗與性能分析，在自行生成及文獻已有的數據集上進行了大量計算，評估算法效率。最后是數據驅動的特征分析，引入了實例空間分析方法，對算例的多項特征進行主成分分析等，定量研究影響求解難度的關鍵因素。所有算例包含來自文獻和自行生成的實例，最多包含90個請求（乘客和包裹）。

計算實驗表明，經過改造的數學啟發式方法能夠在不到一分鐘的時間內，為包含多達90個請求的算例獲得高質量的初始解，其解的質量優于文獻中一個專用于SARP的兩階段方法。利用這些初始解，研究所提出的BCP算法表現優異，成功求解了本文中82%的算例。對于獲得了對偶界（dual bound）的較大規模算例，BCP算法在12%的情況下改進了啟發式方法得到的解值。算法在包裹時間窗較短、每輛車請求比率較小的算例上表現更好。報告了包含最多60名乘客和30個包裹的算例的最優解。

ISA指出，請求數量、全天內時間窗口的分散程度（即時間窗口在時間軸上分布更廣），以及平均路徑長度，是增加算例求解難度的最主要特征。這意味著，當需要處理的訂單更多、訂單的服務時間點分布在全天各個時段、以及車輛平均行駛路線更長時，問題會變得更加復雜和難以求解。

分析還得到了關于系統服務質量的洞見。研究發現，盡管上述特征（請求多、時間窗分散、路徑長）使算例更難以求解，但它們卻為包裹投遞提供了更多機會，并在最終路徑中減少了空駛。具體而言，更短的包裹時間窗口和更長的請求起訖點距離，反而會使算例更容易被求解。這是一個有趣的權衡：約束更緊（時間窗短）或任務本身更長（距離遠），可能限制了可行的調度方案空間，使得搜索最優解的難度降低；但同時，距離遠的請求可能本身就產生了更高的收益，從而更容易被納入有利可圖的路徑中。

本研究針對現實需求，提出并求解了一個禁止乘客繞行的共享搭乘問題（SARP）變體。通過開發一個融合了多種先進技術的分支-切割-定價（BCP）精確算法，并結合高效的數學啟發式方法，研究團隊實現了對較大規模算例（最多90個請求）的高效求解，其中BCP算法解決了超過80%的測試實例。這為SARP這一具有挑戰性的NP-hard問題提供了強有力的精確求解工具，填補了該領域高級精確算法稀缺的空白。

更為重要的是，研究首次將實例空間分析（ISA）方法引入到SARP乃至取送問題中，揭示了影響問題求解難度的關鍵實例特征，如請求數量、時間窗口分布和路徑長度。這一分析不僅有助于理解問題的內在復雜性，還能指導未來測試算例的設計和算法性能的評估。此外，對系統服務質量的量化分析（如時間窗長度、距離對空駛和服務比例的影響）為實際運營提供了寶貴的決策依據。它表明，在設計共享搭乘系統時，需要在運營復雜度（求解難度）與服務效率（減少空駛、提高包裹服務率）之間進行權衡。

綜上所述，這項工作不僅在算法層面推動了共享交通優化領域的發展，也通過深入的實例分析和系統評估，為理解和設計更高效、更環保的城市客貨融合運輸系統提供了重要的理論洞察與實踐指導。其成果對于促進智慧城市物流、降低交通碳排放、提升網約車平臺運營效率具有顯著的意義。