Non-myopic relocation of idle mobility-on-demand vehicles as a dynamic location-allocation-queueing problem

Operation of on-demand services like taxis, dynamic ridesharing services, or vehicle sharing depends significantly on the positioning of idle vehicles to anticipate future demand and operational states. A new queueing-based formulation is proposed for the problem of relocating idle vehicles in an on-demand mobility service. The approach serves as a decision support tool for future studies in urban transport informatics and design of new types of urban mobility systems like carsharing, ridesharing, and smart taxis. A Lagrangian Decomposition heuristic is developed and compared with a relaxed lower bound solution. Using New York taxicab data, the proposed algorithm reduces the cost by up to 27% compared to the myopic case.