AAAI Publications, Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
Dynamic Redeployment to Counter Congestion or Starvation in Vehicle Sharing Systems
Supriyo Ghosh, Pradeep Varakantham, Yossiri Adulyasak, Patrick Jaillet

Last modified: 2015-04-01


Vehicle-sharing (ex: bike sharing, car sharing) is widelyadopted in many cities of the world due to concernsassociated with extensive private vehicle usage, whichhas led to increased carbon emissions, traffic conges-tion and usage of non-renewable resources. In vehicle-sharing systems, base stations are strategically placedthroughout a city and each of the base stations containa pre-determined number of vehicles at the beginningof each day. Due to the stochastic and individualisticmovement of customers, typically, there is either con-gestion (more than required) or starvation (fewer thanrequired) of vehicles at certain base stations. As demon-strated in our experimental results, this happens oftenand can cause a significant loss in demand. We proposeto dynamically redeploy idle vehicles using carriers soas to minimize lost demand or alternatively maximizerevenue of the vehicle sharing company. To that end,we contribute an optimization formulation to jointly ad-dress the redeployment (of vehicles) and routing (of car-riers) problems and provide two approaches that rely ondecomposability and abstraction of problem domains toreduce the computation time significantly. Finally, wedemonstrate the utility of our approaches on two realworld data sets of bike-sharing companies.


Vehicle Sharing System; Dynamic Redeployment; Lagrangian Dual Decomposition; Abstraction

Full Text: PDF