基於多人駕駛之人員交通路線規劃系統

A route planning system for people transportation with multiple drivers

王淳平(Chuen-Ping Wang)

指導教授 ： 王佳盈

中原大學/電機資訊學院/電機工程研究所/碩士(2018年)

https://doi.org/10.6840/cycu201800045

摘要

在籌辦戶外活動的時候，有些時候會需要安排汽車共乘，而這種多司機多乘客的人車分配問題，要怎樣安排才能使所有人員能在最短的時間到達目的地，往往是一個瑣碎耗時又不容易做好的工作。本論文主要即針對這種多司機多乘客的人車分配問題進行探討。我們假設已知所有司機和乘客的地址，以及將要前往的目的地，我們利用Google Maps API計算任意兩點的距離和行車時間，並提出適當的演算法來找出最佳的共乘安排，以及產出每位司機載客的路線圖。當人數眾多的時候，最佳的安排可能會導致極大的計算量，對此我們也提出了簡化的版本，在所舉的實例當中，可以在少量的運算量之下，達到幾近最好的效能。

關鍵字

路徑規劃 ； 多人共乘 ； 多司機路徑規劃 ； 車輛路線規劃

並列摘要

In organizing outdoor activities, sometimes there will be arrangements for car sharing. How to arrange this multi-driver and passengers path planning problem such that all people can reach their destination in the shortest time is a troublesome and time-consuming job. In this thesis, we focus on this multi-driver and passengers path planning problem. Giving all people's addresses and the destination, we propose an appropriate algorithm to find the best arrangement which uses Google Maps API to calculate the distances and driving times. We also generate the road map for each driver and the corresponding passengers. When the number of people increase, the calculations of best arrangement can lead to a tremendous amount of computation. In such a case, we also propose a simplified algorithm that achieves nearly the best performance with only a small amount of computation

並列關鍵字

path planning ； ride sharing ； car sharing ； vehicle routing

參考文獻

吾技術學院資訊科技應用研究所，2010。

[3] 連中銓、黃書猛，動態即時路徑規劃應用於物流管理之研究，醒

[4] 王張煒、蘇昭銘，中小型鄉鎮接駁公車之路線設計方法，私立中

[6] Distance Matrix API手冊, Available:

[7] Python, Available: https://www.python.org/