PhD Dissertation Proposal by Supriyo GHOSH

Proactive Sequential Resource (Re)distribution for Improving Efficiency in Urban Environments

Due to the increasing population and lack of coordination, there is a mismatch in supply and demand of common resources (e.g., shared bikes, ambulances, taxis) in urban environments, which has deteriorated a wide variety of quality of life metrics such as success rate in issuing shared bikes, response times for emergency needs, waiting times in queues etc. Thus, in my thesis, I propose efficient algorithms that optimise the quality of life metrics to better match the supply of resources to the demand (that is both stochastic and dynamic) for resources by proactively redistributing the resources using intelligent operational (day-to-day) and strategic (long-term) decisions. For operational decisions, I use Bike Sharing System (BSS) as the motivating domain, because the stations of BSS are often not balanced due to uncoordinated movements of resources (i.e., bikes) by customers. For strategic decisions, Emergency Medical Service (EMS) domain is employed as the spatial distribution of resources (e.g., base stations and ambulances) in EMS remains static for a long period.

The primary objective of BSS is to reduce carbon footprint. Unfortunately, the mismatch of supply and demand for bikes leads to significant loss in demand and therefore, increases the usage of private transportation which is the major source of carbon emission. In order to reduce the lost demand, I contribute three operational decision making approaches for sequential redistribution of bikes: (i) Optimising carbon footprint through dynamic repositioning; (ii) Optimising carbon footprint through robust repositioning; and (iii) Optimising carbon footprint through incentives. For the first two approaches carrier vehicles are used for the repositioning of idle bikes. The first approach is useful for consistent demand patterns, where I consider the expected demand for multiple time steps to find a repositioning solution and provide novel decomposition and abstraction mechanisms to speed up the solution process. The second approach deals with scenarios where the demand is highly uncertain and the pattern changes over time. For the third approach bike trailers are employed for repositioning tasks to further reduce the carbon footprint and a mechanism is designed to crowdsource these tasks within a given budget constraint. The experimental results on two real-world data sets of Capital Bikeshare (Washington, DC) and Hubway (Boston, MA) BSS demonstrate that our approaches reduce the average and worse case lost demand by 22% and 10% over the current practice.

Lastly, I propose strategic decision making approach for EMS so as to place base stations at “right” location and allocate “right” number of ambulances on those bases to better match the emergency requests to the supply of ambulances. An accelerated version of greedy algorithm on top of a data-driven optimisation formulation is proposed to jointly consider the placement of bases and allocation of ambulances. Experiment results on a real-world data set show that our approach serves 3% extra requests within a threshold time bound over the existing approaches.