車輛路徑問題

車輛路線問題是一個規劃過程，其中（運輸）訂單被分組到旅游中并按順序放置。 通常，游覽是由人或車輛進行的。 這個計劃過程在所有需要計劃大量訂單和旅游的領域都很重要。 示例是零售商分支機構的交付、郵件的收集、垃圾的收集、人員的運輸和服務人員的部署。 在快遞-快遞-包裹服務等常規路線的情況下，以這種方式形成運輸網絡結構。

訂單通常包括將一定數量的貨物從起點運送到目的地。 車輛路徑問題的解決方案通常有兩個方面：

• 聚類表明哪些訂單被分組到一個旅游中
• 路線定義了行程中各點的服務順序。

例如，車輛路徑問題的目標是最小化使用的車輛數量、行駛距離、運行時間、二氧化碳排放量或更復雜的成本函數。 在標準的車輛路線問題問題中，所有起點或終點都在一個停車場，那里有有限或無限數量的相同車輛，但容量有限。 其他變體考慮額外的限制，例如 B. 時間窗口、多個站點或任意起點和終點（所謂的取件和送貨問題）。

實際上，任務因許多限制而擴展。 例如，考慮多個倉庫、異構車隊或訂單之間的優先級關系。 另一個可能的附加任務是考慮時間窗，車輛必須在該時間窗內到達客戶，以符合由時間窗管理分配或預訂的時段。 當訂單情況在計劃期間動態變化時，有人談到動態車輛路徑問題。

除了物流部門，在為客戶提供服務的所有經濟部門都有應用。 在許多公司中，車輛路線問題的軟件用于編譯生成的旅行并根據時間規范或重量限制以及運輸成本等標準對其進行優化。

車輛路線問題的基本模型屬于NP-hard問題類。 因此，啟發式方法被用來解決問題。 簡單的解決方法是節省啟發式算法和掃描算法。 更好質量的解決方案基于進化算法、模擬冷卻和禁忌搜索。 他們使用本地搜索策略，其中交換訂單順序或訂單分配給車輛。 最近，螞蟻算法也越來越多地被認為是一種解決問題的方法。

作為車輛路徑問題的子問題，旅行商問題是通過考慮一輛無限容量的車輛并讓它以最小的成本或距離行駛而產生的。

Def.: 將一組訂單分配給一組運輸工具，同時考慮距離和限制，以使使用運輸工具和所覆蓋的距離引起的所有總運輸成本最小化。

車輛路徑問題軟件支持公司規劃和優化旅游。 數字道路網絡、客戶主文件、車輛和駕駛員列表以及當前訂單列表。 距離和旅行時間可以使用地理參考客戶地址的坐標粗略估計或從遠程工作中獲取，或者用于路線優化的算法在數字道路網絡上運行。 優化是通過將許多客戶的運輸要求組合成一個或多個旅行來進行的，這樣可以觀察到客戶的時間規格、車輛負載和容量、司機休息和工作時間以及車輛維護周期，同時所產生的運輸成本被最小化。 這些可能包括司機、調度員和車輛的固定成本，以及由消耗成本、通行費、維護和修理、工作時間和加班費組成的可變車隊成本。