在籌辦戶外活動的時候,有些時候會需要安排汽車共乘,而這種多司機多乘客的人車分配問題,要怎樣安排才能使所有人員能在最短的時間到達目的地,往往是一個瑣碎耗時又不容易做好的工作。本論文主要即針對這種多司機多乘客的人車分配問題進行探討。我們假設已知所有司機和乘客的地址,以及將要前往的目的地,我們利用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