使用模擬退火演算法規劃多人共乘車之路徑

Path Planning by Simulated Annealing for Multi- Passengers Ride-Sharing Vehicle

曾繁勛(Fan-Hsun Tseng) ； 簡暐哲(Wei-Che Chien) ； 賴槿峰(Chin-Feng Lai) ； 江華珮(Hua-Pei Chiang) ； 趙涵捷(Han-Chieh Chao)

《前瞻科技與管理》 8卷1期 (2018/08) Pp. 55-73

https://doi.org/10.6193/JATM.201808_8(1).0003

摘要

近年來，伴隨著物聯網的蓬勃發展，智慧城市是一個嶄新的研究領域，其中，便利的交通運輸成為熱門的研究議題，旨在解決交通擁塞問題並提升交通的靈活性，成就更有效率的智慧運輸系統。然而，現有的共乘車研究大多侷限於固定路線，乘客得根據需求點上下車，而非依據乘客的需求來規劃對應之乘車路線，因此，本研究提出一個嶄新的共乘車概念，定義多人共乘車之路徑規劃問題，分別提出模擬退火等待時間演算法與模擬退火最短路徑演算法，模擬結果顯示，本研究提出的方法能因應不同的使用者需求而規劃最適合的共乘車行車路線。

關鍵字

共乘車 ； 啟發式演算法 ； 智慧運輸系統 ； 智慧城市 ； 路徑規劃

並列摘要

In recent years, smart city accompanies with Internet of Things development is a novel research field. The convenient transportation is a vital research issue. It aims at solving traffic congestion problem and improving traffic flexibility. In addition, it achieves intelligent transportation systems more efficient and convenient. However, existing literature on ride-sharing vehicle is mostly restricted to fixed routes. Passengers must get on and off ride-sharing vehicle according to boarding points and alighting points rather than their requirements of travel routes. As a result, the paper presents a novel ride-sharing method. We define the path planning problem of multi-passengers for ride-sharing vehicles then propose two algorithms, i.e., simulated annealing-based waiting time algorithm and simulated annealing-based shortest path algorithm. The simulation results show that the proposed method in the paper is able to plan the most suitable routes for multi-passengers ridesharing vehicles.

並列關鍵字

ride-sharing vehicle ； metaheuristic algorithm ； intelligent transportation system ； smart city ； path planning

參考文獻

Agatz, N.,Erera, A.,Savelsbergh, M.,Wang, X.(2012).Optimization for Dynamic Ride-Sharing: A Review.European Journal of Operational Research.223(2),295-303.

Alonso-Mora, J.,Samaranayake, S.,Wallar, A.,Frazzoli, E.,Rus, D.(2017).On-Demand High-Capacity Ride-Sharing via Dynamic Trip-Vehicle Assignment.Proceedings of the National Academy of Sciences.114(3),462-467.

Alsabaan, M.,Alasmary, W.,Albasir, A.,Naik, K.(2013).Vehicular Networks for a Greener Environment: A Survey.IEEE Communications Surveys and Tutorials.15(3),1372-1388.

Antosiewicz, M.,Koloch, G.,Kamiński, B.(2013).Choice of Best Possible Metaheuristic Algorithm for The Travelling Salesman Problem with Limited Computational Time: Quality, Uncertainty and Speed.Journal of Theoretical and Applied Computer Science.7(1),46-55.

Arora, A.,Yun, M.,Kim, T.,Zhou, Y.,Choi, H.-A.(2009).Automated Ride Share Selection Using Vehicular Area Networks.IEEE International Conference on Communications Workshops.(IEEE International Conference on Communications Workshops).: