Online optimization of the dial a ride problem with the integral primal simplex

Metropolitan areas seek to increase the use of ridesharing services to decrease congestion, parking issues, and pollution. Several initiatives propose such a service like UberPool. However, they rarely use advanced optimization methods due to complex implementation in practice. Developed algorithms for Dial a Ride Problem (DARP) in dynamic mode often try to batch requests to take advantage of the static optimization. They restart the optimization for each new batch without using previous solutions. We aim to develop an algorithm for dynamic DARP that reuses previously computed solutions using the strengths of the integral primal simplex to expand the current routes with the new arrival requests.