突發性片堵塞下兩車信息共享的加拿大旅行者問題

蘇 兵，林 剛，程新峰，孫璐璐

(西安工業大學經濟管理學院，陜西 西安 710032)

1 引言

加拿大旅行者問題(Canadian Traveler Problem，CTP)是指旅行者從起點出發去終點的過程中遭遇無法預知突發性堵塞下如何制定實時路徑選擇策略使花費時間盡可能少的問題[1-2]。對這個受不確定因素影響較大的問題，國內外學者采用在線問題與競爭策略的理論開展了相關研究[3-6]，主要討論了堵塞信息完全未知和有限預知情形下的單一路段堵塞的單車路徑選擇策略。對于堵塞信息完全未知的情形，建立一般網絡中路段堵塞不可恢復下的單車在線路徑選擇模型，設計貪婪策略和復位策略并證明策略競爭比[7-10]；建立方格路網中路段堵塞不可恢復下的單車在線路徑選擇模型，設計方向貪婪策略和多選擇移動策略并證明策略競爭比[11]；建立連續網絡中路段堵塞可恢復下的單車在線路徑選擇模型，設計等待策略和移動策略并證明策略競爭比[12]。對于堵塞信息有限預知情形下即單車到達某一節點時可以預知相鄰節點一條關聯邊堵塞信息，建立一般離散網絡中路段堵塞可恢復的單車在線路徑選擇模型，設計等待策略和貪婪策略并證明策略競爭比，建立一條路上路段堵塞可恢復的單車在線路徑選擇模型，設計混合策略并證明策略競爭比[13-15]。現有加拿大旅行者問題研究主要是在單車遭遇突發性路段堵塞的假設下進行的。然而在實際中，網絡中經常會發生片堵塞，即多……