Online optimization of the dial-and-ride problem with the integral primal simplex

Transportation Network Companies such as Uber and Lyft have provided on-demand mobility services to cope with rising transportation demands. More recently, ridesharing has been introduced as a new option for customers using these services (e.g., UberPool, Lyft Shared) to decrease congestion, parking issues and pollution. However, these systems rarely use advanced optimization methods due to complex implementation and this limits their potential benefits. Developed algorithms for dial-and-ride problem (DARP) in dynamic mode often divide the time horizon into short periods and try to batch requests to take advantage of the static optimization. They restart the optimization for each new batch without using previous solutions. Our goal is to develop an algorithm for dynamic DARP that reuses previously computed solutions using the strengths of the integral primal simplex. In contrast to prior studies which consider fixed epochs to batch requests, we propose a re-optimization strategy which update the dispatching plan dynamically to expand the current routes with the new arrival requests. The performance of the algorithm is evaluated on large-size instances from the New York city Taxi and limousine dataset, and we compare the quality of results with prior studies in terms of the average waiting time of the passengers.