eduzhai > Applied Sciences > Engineering >

Speed-up Heuristic for an On-Demand Ride-Pooling Algorithm

  • king
  • (0) Download
  • 20210505
  • Save

... pages left unread,continue reading

Document pages: 11 pages

Abstract: With ongoing developments in digitalization and advances in the field ofautonomous driving, on-demand ride pooling is a mobility service with thepotential to disrupt the urban mobility market. Nevertheless, to apply thiskind of service successfully efficient algorithms have to be implemented foreffective fleet management to exploit the benefits associated with thismobility service. Especially real time computation of finding beneficialassignments is a problem not solved for large problem sizes until today. Inthis study, we show the importance of using advanced algorithms by comparing afast, but simple insertion heuristic algorithm with a state-of-the-artmulti-step matching algorithm. We test the algorithms in various scenariosbased on private vehicle trip OD-data for Munich, Germany. Results indicatethat in the tested scenarios by using the multi-step algorithm up to 8$ $additional requests could be served while also 10$ $ additional drivendistance could be saved. However, computational time for finding optimalassignments in the advanced algorithm exceeds real time rather fast as problemsize increases. Therefore, several aspects to reduce the computational time bydecreasing redundant checks of the advanced multi step algorithm areintroduced. Finally, a refined vehicle selection heuristic based on three rulesis presented to furthermore reduce the computational effort. In the testedscenarios this heuristic can speed up the most cost intensive algorithm step bya factor of over 8, while keeping the number of served requests almost constantand maintaining around 70$ $ of the driven distance saved in the system.Considering all algorithm steps, an overall speed up of 2.5 could be achieved.

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...