An exact algorithm for vehicle routing problems with temporal dependency constraints
首創片段式演算法整合 5 種時間依賴約束，成功破解車輛路線排程的計算瓶頸。
- 時間取捨會導致傳統演算法的主導規則失效，難以解出複雜的跨路線約束。
- 全新片段式模型將時間依賴任務與常規任務脫鉤，從根本消除排程衝突。
- 定價切割枚舉框架配合 4 大強化不等式，運算效能大幅超越現有求解基準。
自 1959 年提出車輛路線問題以來，任務間的「時間依賴性」一直是演算法難以跨越的計算瓶頸。現有的精確求解器多侷限於處理單一時間限制，且完全無法計算「不重疊」約束。阿姆斯特丹自由大學團隊針對此痛點提出全新「片段式（fragment-based）」模型與定價-切割-枚舉演算法，不僅首度將 5 種時間依賴類型整合至單一數學框架，更成功解出過去被視為無法求解的複雜調度實例。
跨越時間依賴障礙：5 種任務排程挑戰
車輛路線問題（VRP）的傳統假設是各任務的執行時間彼此獨立，但在真實世界的調度場景中，這項假設往往與實務脫節。物流與排程系統經常面臨任務間的操作同步（operation synchronization）需求，這類時間依賴性可具體分為 5 大類型：同步（任務須同時開始）、優先順序（具備預定的先後次序）、最小/最大時間差、重疊（執行區間必須交集），以及不重疊（禁止同時執行）。
這類限制廣泛存在於各類產業應用中。在居家醫療照護中，病患可能需要多位護理人員同時到場；在航空機隊規劃中，不同日期的相同航班必須確保起飛時間一致；而在電動車路線規劃上，則需要避免充電站的排隊擁擠。當這類依賴關係出現於同一條或不同車輛的路線中時，會產生複雜的跨路線約束（inter-route constraints），導致傳統演算法的計算難度大幅飆升。
檢視現有的文獻與技術，多數的精確求解方法往往只能處理單一類型的時間依賴性，例如專門解決任務同步或最大時間差的演算法。部分演算法雖然能處理同步與重疊，但至今沒有任何一種精確演算法能夠妥善處理「不重疊」的限制，這成為當前物流排程技術的一大盲區。為了解決這個超過半世紀的數學難題，研究團隊針對所有可能的時間依賴配對建立 $\delta^{\mathrm{min}}$ 與 $\delta^{\mathrm{max}}$ 等 4 項核心參數，藉此將所有限制統一收斂進單一數學框架中。
打破路線優化矛盾：BP 演算法的計算極限
傳統上解決 VRP 問題的最先進技術通常依賴基於路線的數學公式，並運用主導規則（dominance rules）來消除次優路線。然而，時間依賴性會使這些主導規則徹底失效。在一般的排程中，提早開始任務通常是有利的；但在具備時間限制的場景中，延遲某個任務的執行反而可能滿足跨路線或路線內的同步條件。這種因為時間取捨而產生的矛盾，使得傳統的行生成（column generation）演算法難以直接套用。
為了克服這個難題，學界過去主要依賴兩種截然不同的解決策略。第一種是在BP 演算法（branch-and-price，分支定價法）的主問題與子問題中放寬時間限制，轉而透過時間窗分支來強制執行。這種作法的好處是能夠使用成熟的定價子問題求解器，但代價是會產生較弱的線性鬆弛邊界，因為演算法可能會生成忽略時間資訊的無效路線。
第二種策略則是將時間依賴性直接納入主問題，並為定價子問題開發專屬的演算法。雖然這能產生更嚴謹的數學公式，卻會帶來具備線性節點成本的複雜子問題，特別是當時間依賴性發生在單一路線內的任務時，求解難度將呈指數級上升。這兩種傳統策略在本質上都是在「公式強度」與「子問題複雜度」之間被迫做出極端的妥協。
重新定義路線結構：全新 Fragment 數學模型
為了在運算效率與模型強度之間找到最佳平衡，研究團隊拋棄了傳統的完整路線表示法，轉而提出一種全新的「片段式（fragment-based）」模型。在該定義下，一個Fragment（片段）是指由單一車輛執行的任務序列，其最大的特徵在於：只有在序列的起點與終點才允許包含具備時間依賴性的任務，而片段中間的所有任務皆為不受時間依賴限制的常規任務。
採用這種結構的關鍵優勢，在於它能成功將「決定時間依賴任務的精確起始時間」與「尋找無時間限制任務的可行序列」這兩件事脫鉤。在同一個片段內部，由於不存在其他具備時間依賴的任務，因此系統完全沒有動機去刻意引入等待時間或延遲中間任務。換言之，片段內部的任務只需要盡早執行即可，徹底消除了傳統路線規劃中因時間取捨而產生的排程衝突。
透過建立精簡排程（compact schedules），演算法能以線性時間 $\mathcal{O}(|F|)$ 快速透過動態規劃算出每個片段的最晚起始時間、最早完成時間與最短持續時間。這種設計不僅保留了極高的排程彈性，更大幅簡化了比較部分路線時的運算負擔，成為後續精確求解演算法得以高效運作的核心基石。
結合定價與切割機制：4 大強化不等式與最佳解
基於上述的片段式模型，團隊進一步開發出一套精確的定價-切割-枚舉（price-cut-and-enumerate）演算法。該演算法首先利用交替的行與列生成（alternating column-and-row generation）技術來計算出穩健的下界，同時輔以基於 MILP（混合整數線性規劃）的啟發式演算法來取得初始的上界。
在取得初步的上下界之後，系統會透過片段枚舉與片段縮減技術，配合分支切割（branch-and-cut）流程進行迭代優化。為了進一步限縮解空間並強化數學模型的嚴密性，研究中還特別提出了 4 大類全新的強化不等式（strengthening inequalities），用以排除不相容的片段組合，確保最終生成的路線既符合車輛容量，又完美遵守所有的時間同步要求。
運算實驗數據證實，這套創新框架不僅能夠處理涵蓋「不重疊」在內的廣泛時間依賴約束，其求解效能更顯著超越了現有兩大主流基準方法。這項演算法的突破，為高密度物流、航空機隊調度以及多重代理人協作等高度複雜的排程領域，提供了一個兼具運算效率與全域最優保證的技術途徑。
透過切割路線重組「片段式」模型，演算法成功化解排程優化的時間衝突，為多變數系統確立了運算新標竿。