The ride sharing routing problem : an optimization algorithm
We investigate the ride sharing routing problem from an algorithmic point of view. The research is conducted to the paper `Algorithms for Trip-Vehicle Assignment in Ride-Sharing' by Bei & Zhang, 2018 to find a better algorithm that provides more optimized output in a more efficient time. Th...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/148474 |
| _version_ | 1824454990648836096 |
|---|---|
| author | Lawrence, Lucas |
| author2 | Gary Royden Watson Greaves |
| author_facet | Gary Royden Watson Greaves Lawrence, Lucas |
| author_sort | Lawrence, Lucas |
| collection | NTU |
| description | We investigate the ride sharing routing problem from an algorithmic point of view. The research is conducted to the paper `Algorithms for Trip-Vehicle Assignment in Ride-Sharing' by Bei & Zhang, 2018 to find a better algorithm that provides more optimized output in a more efficient time. The objective of the problem is to assign each drivers to fetch two passengers given the locations of drivers, passengers' pick-up points and their destinations. We then designed an algorithm and observed that it produces smaller costs solution in most of the randomly generated data with time complexity $O(n^2\log n)$ for real valued weighted graph and $O(n^2)$ for integer valued weighted graph improved from the previous $O(n^3)$. |
| first_indexed | 2025-02-19T03:31:06Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/148474 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:31:06Z |
| publishDate | 2021 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1484742023-02-28T23:18:59Z The ride sharing routing problem : an optimization algorithm Lawrence, Lucas Gary Royden Watson Greaves School of Physical and Mathematical Sciences gary@ntu.edu.sg Science::Mathematics::Discrete mathematics::Graph theory Science::Mathematics::Applied mathematics::Optimization Science::Mathematics::Discrete mathematics::Algorithms We investigate the ride sharing routing problem from an algorithmic point of view. The research is conducted to the paper `Algorithms for Trip-Vehicle Assignment in Ride-Sharing' by Bei & Zhang, 2018 to find a better algorithm that provides more optimized output in a more efficient time. The objective of the problem is to assign each drivers to fetch two passengers given the locations of drivers, passengers' pick-up points and their destinations. We then designed an algorithm and observed that it produces smaller costs solution in most of the randomly generated data with time complexity $O(n^2\log n)$ for real valued weighted graph and $O(n^2)$ for integer valued weighted graph improved from the previous $O(n^3)$. Bachelor of Science in Mathematical Sciences 2021-04-27T08:18:10Z 2021-04-27T08:18:10Z 2021 Final Year Project (FYP) Lawrence, L. (2021). The ride sharing routing problem : an optimization algorithm. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/148474 https://hdl.handle.net/10356/148474 en application/pdf Nanyang Technological University |
| spellingShingle | Science::Mathematics::Discrete mathematics::Graph theory Science::Mathematics::Applied mathematics::Optimization Science::Mathematics::Discrete mathematics::Algorithms Lawrence, Lucas The ride sharing routing problem : an optimization algorithm |
| title | The ride sharing routing problem : an optimization algorithm |
| title_full | The ride sharing routing problem : an optimization algorithm |
| title_fullStr | The ride sharing routing problem : an optimization algorithm |
| title_full_unstemmed | The ride sharing routing problem : an optimization algorithm |
| title_short | The ride sharing routing problem : an optimization algorithm |
| title_sort | ride sharing routing problem an optimization algorithm |
| topic | Science::Mathematics::Discrete mathematics::Graph theory Science::Mathematics::Applied mathematics::Optimization Science::Mathematics::Discrete mathematics::Algorithms |
| url | https://hdl.handle.net/10356/148474 |
| work_keys_str_mv | AT lawrencelucas theridesharingroutingproblemanoptimizationalgorithm AT lawrencelucas ridesharingroutingproblemanoptimizationalgorithm |