近日，南方科技大學機械與能源工程系教授楊再躍團隊在智慧交通領域取得多項研究成果，兩篇論文被該領域期刊之一IEEE Transactions on Intelligent Transportation Systems接收。
現時，交通物流行業已大量採用電動汽車作為運輸工具。然而，與傳統燃油車不同，電動汽車充電需要花費相當長的時間，勢必會影響車輛的調度安排。囙此，我們需要同時考慮電動汽車路徑規劃和充電的聯合調度問題（electric vehicle routing problem，EVRP），最大化運輸收益、最小化用車成本。該問題是一類NP-hard的混合整數規劃（mixed integer programming，MIP）問題，採用常規方法非常耗時。研究團隊提出了一種計算時間複雜度低的兩階段算灋（TLP），利用線性規劃鬆弛的精確性、並提出消除耦合項方法，將原始問題轉化為兩個線性規劃，故可以在多項式求解時間內獲得近似最優解。為了進一步提高解的質量，課題組又提出了一種基於兩階段算灋的反覆運算算灋（ILP）。圖1展示了兩種算灋既可保證近似最優解，又能將計算時間降低了4個數量級。
以此為基礎，研究團隊進一步針對線上的EVRP以及未來資訊的不確定性，提出了一種利用滾動優化框架和虛擬節點生成的快速算灋。如圖2所示，相較於商用的求解器，如CPLEX、GUROBI和分支定價算灋，研究團隊提出的MBD算灋將計算速度提高了3~4個數量級；此外，算灋對記憶體需求小，可求解350個節點和35輛車的算例，從而驗證了提出算灋的優越性。
圖1左：最優間隔的比較；右：算灋計算時間的比較
圖2左：不同算灋的計算時間比較；右：大規模算例的計算時間比較
以上論文由南方科技大學和哈爾濱工業大學共同完成。兩篇論文的第一作者為南方科技大學與哈爾濱工業大學聯合培養的2018級博士生姚燦棋，通訊作者為楊再躍、機械與能源工程系研究助理教授陳士博，南科大是論文第一單比特。以上論文由科技部重點研發計畫、國家自然科學基金、深圳市科創委等資助。
論文連結：
1、https://ieeexplore.ieee.org/document/9713755
2、https://ieeexplore.ieee.org/document/9430759