Traffic congestion is considered to be a major source of greenhouse gas emissions and has become one of the causes for significant economic costs, wasted time and public health risks (Levy et al. 2010; Pi et al. 2021; Schrank et al. 2019). In order to reduce the negative impact of traffic congestion, people have striven to find different methods to tackle this problem. Ride-sharing, defined as a joint-trip of more than two participants that share a vehicle and requires coordination with respect to itineraries, has the potential to help mitigate congestion (Furuhata et al.2013). Although this idea dates back to the 1940s, it is only until recent development of internet, global-positioning-systems (GPS) and wireless communications that ride-sharing can fully realize its potential.

 
A good ride-sharing system should provide quick response to passenger requests while optimizing the routes which is not an easy task especially in the situation when passengers request dynamically. One way to mitigate the effect of uncertainty is to allow passengers to walk while waiting for the drivers. At the same time, we would like to fully utilize the incentives of ride-sharing provided by the government agencies: the increasing use of High Occupancy Vehicle (HOV) lanes. Therefore, in this report, we study and formulate the dynamic pickup and delivery problem with HOV lanes and meeting points with application to ride-sharing.

In our ride-sharing context, the drivers are travelling toward their own destinations and can make detours to pick up or drop off additional passengers where the passengers have flexible pickup and drop-off locations. We propose a two-stage heuristic algorithm which consists of an insertion heuristic to solve the pickup and delivery problem (PDP) and a second stage algorithm that can solve the meeting points problem optimally in polynomial time.

Our experimental results show that both the HOV lanes and meeting points can increase the efficiency of a dynamic ride-sharing system. A good combination of HOV lanes and meeting points can provide passengers with lower commuting cost and faster commuting experience.