On-demand transportation optimization with pgRouting + DARP

Public transportation in rural and sparsely populated areas is facing considerable challenges in these years. The regular public transportation is often not economically or environmentally sustainable anymore and therefore it is necessary to develop new ways of public transportation in such areas.

 

We have implemented a Dial-a-Ride Problem (DARP) solver for pgRouting aiming to help build a better and more flexible transportation system. The concept for a public transit management system is based on existing infrastructure such as taxis, buses and micro-buses. Customers send transportation requests containing specified pickup and target locations together with a desired departure and arrival time window. Then DARP solver tries to minimize transportation cost while satisfying customer service level constraints (time windows violation, waiting and travelling times) and fleet constraints (number of cars and capacity, as well as depot location).

 

This presentation is going to give an insight into the latest development of pgRouting, an extension of PostGIS with shortest path search functionality and tools for spatial network analysis. By implementing DARP and other generic algorithms to solve spatial optimization problems, pgRouting can provide the groundwork for fleet management, transportation and logistics applications.