Proactive sequential resource (re)distribution for improving efficiency in urban environments

• Main Author: GHOSH, Supriyo
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: dynamic redistribution; mathematical optimisation; data-driven modeling; decision analytics; bike sharing system; emergency response; Databases and Information Systems; Data Storage Systems
• Online Access: https://ink.library.smu.edu.sg/etd_coll/140; https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1139&context=etd_coll
• Institution: Singapore Management University

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 by proactively redistributing the resources using intelligent operational (day-to-day) and strategic (long-term) decisions in the context of urban transportation and health & safety. For urban transportation, Bike Sharing System (BSS) is adopted as the motivating domain. Operational decisions are crucial for BSS, because the stations of BSS are often not balanced due to uncoordinated movements of resources (i.e., bikes) by customers. The imbalanced stations lead to significant loss in demand and increase the usage of private transportation and therefore, defeat the primary objective of BSS which is to reduce carbon footprint. In order to reduce the carbon footprint, I contribute three operational decision making approaches for sequential redistribution of bikes: (i) Optimising lost demand through dynamic redistribution; (ii) Optimising lost demand through robust redistribution; and (iii) Optimising lost demand through incentives. In the first approach, I consider the expected demand for multiple time steps to find a redistribution solution and provide novel decomposition and abstraction mechanisms to speed up the solution process. This approach is useful for BSS with consistent demand patterns. Therefore, the second approach proposes a robust redistribution solution using the notion of two-player adversarial game to address the scenarios where the demand has high variance. For the third approach, within the central budget constraints of the operators, a mechanism is designed to incentivise the customers for executing the bike redistribution tasks by themselves. The experimental results on two real-world data sets of Capital Bikeshare (Washington, DC) and Hubway (Boston, MA) BSS demonstrate that our approaches significantly reduce the average and worse case lost demand over the current practices. For health & safety, Emergency Medical System (EMS) is adopted as the motivating domain. EMS is an extremely sensitive and critical domain for public healthcare services, because reducing the response times for emergency incidents by a few seconds can save a human life. In order to reduce the response times, 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. An accelerated version of greedy algorithm on top of an existing data-driven optimisation formulation is proposed to jointly consider the placement of bases and allocation of ambulances. Subsequently, I provide insights to improve the operational decisions of EMS for dynamic redistribution of ambulances by incorporating the exact real-world dynamics of EMS into the existing data-driven optimisation formulation. Experimental results on real-world data sets demonstrate that both our strategic and operational decisions improve the efficacy of EMS over the existing approaches.