
NSF Org: |
CMMI Division of Civil, Mechanical, and Manufacturing Innovation |
Recipient: |
|
Initial Amendment Date: | September 1, 2015 |
Latest Amendment Date: | September 1, 2015 |
Award Number: | 1537394 |
Award Instrument: | Standard Grant |
Program Manager: |
Georgia-Ann Klutke
gaklutke@nsf.gov (703)292-2443 CMMI Division of Civil, Mechanical, and Manufacturing Innovation ENG Directorate for Engineering |
Start Date: | September 1, 2015 |
End Date: | August 31, 2018 (Estimated) |
Total Intended Award Amount: | $200,000.00 |
Total Awarded Amount to Date: | $200,000.00 |
Funds Obligated to Date: |
|
History of Investigator: |
|
Recipient Sponsored Research Office: |
341 PINE TREE RD ITHACA NY US 14850-2820 (607)255-5014 |
Sponsor Congressional District: |
|
Primary Place of Performance: |
136 Hoy Rd NY US 14853-3801 |
Primary Place of
Performance Congressional District: |
|
Unique Entity Identifier (UEI): |
|
Parent UEI: |
|
NSF Program(s): | OE Operations Engineering |
Primary Program Source: |
|
Program Reference Code(s): |
|
Program Element Code(s): |
|
Award Agency Code: | 4900 |
Fund Agency Code: | 4900 |
Assistance Listing Number(s): | 47.041 |
ABSTRACT
The US economy is undergoing a dramatic change with the introduction of a wave of industries based on the sharing of resources. Prominent examples include vehicle-sharing services like ZipCar and Motivate, "taxi-like" services like Uber and Lyft, and Airbnb. Such services rely not just on real-time information flow between dispersed users, but also on ensuring high reliability levels to ensure that users remain loyal to the service. For example, in vehicle sharing it is important that subscribers are able to obtain vehicles when and where they want them with high reliability. This proposal explores stochastic optimization models and methodology for logistical questions associated with the sharing economy, with particular emphasis on vehicle sharing. Central questions relate to fleet sizing and fleet deployment across a city. These questions are complicated by the heavily time-dependent and stochastic nature of vehicle usage.
A suite of models and methods for tackling these problems is proposed that includes both long-term planning methodology for capacity sizing and short-term planning methodology for near real-time alignment of supply and demand of vehicles. The long-term planning methods are based on constructing stochastic models that simultaneously accurately model vehicle-sharing operations and provably possess mathematical structure that can be exploited through efficient optimization techniques, particularly integer linear programming. These properties will be established through combinatorial arguments to establish a set of sufficient conditions that allow one to apply linear programming on problems that are defined on integer lattices (since the number of vehicles at a location, and the capacity of locations are integral). These sufficient conditions will then be established for the stochastic models in question through the use of stochastic coupling techniques. This combination of combinatorial and coupling arguments may be broadly applicable beyond problems arising in the sharing economy, as evidenced by a plethora of similarly structured problems in a repository of simulation-optimization test problems. In addition to these long-term planning tools, short-term tools will be developed that enable a near real-time response to conditions on the ground. In vehicle-sharing systems, such tools would guide the repositioning of vehicles to better align with current and anticipated demand, using the results from long-term planning tools as a guide. A unifying principle in the proposed work is to develop methods that optimize expected performance under usual operating conditions to ensure efficient operation, while hedging against worst-case events to provide an important level of robustness to unexpected developments. The goal of this is work is provide practical solutions supported by new theoretical results that establish both strong average-case and worst-case guarantees.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The purpose of this work was to develop computational methods to aid in the design of systems that arise in the sharing economy, with special emphasis on bike-sharing systems to focus the research and serve as a practical testbed. The work proceeded in close partnership with Motivate, a company that owns and operates the largest bike-sharing systems in the USA today, including in New York City, Boston, Chicago, Washington DC and San Francisco.
Intellectual Merit: The work led to the development of new optimization methods for determining how to deploy both bikes and bike docks around a city, through the use of so-called discrete-convexity methods. The methods developed are dramatically faster than existing methods and have improved the understanding of discrete-optimization problems with certain types of constraints. Also, new methods have been developed for analyzing systems where customer behavior exhibits extremely strong dependence on time, as is exhibited in bike-sharing systems through the "tidal flows" of commuters using the system to get to/from work. Moreover, the work strongly motivates a new line of research in so-called "simulation optimization," where one uses a simulation model of a complex system, like bike sharing, along with a "search procedure" to tailor design decisions so as to maximize the social benefit of the design. The work has also inspired new efforts to understand and design bike-sharing systems that are not station-based, as with companies like Lime Bike, and systems that employ electric bikes, as with Ford Go-Bike in San Francisco.
Broader Impact: This project has obvious benefits to society through the improvements in operations and design of bike-sharing systems. Many of the ideas developed in this work have been implemented in the bike-sharing systems operated by Motivate, with heaviest impact in the operations of Citi Bike in New York City. The impacts are measurable and have been quantified. In addition, three PhD students and many undergraduate students have received training in applied research, and case studies from the work have been incorporated into existing and new classes at Cornell, especially in courses related to data-based decision making within the larger sphere of data science.
Last Modified: 11/24/2018
Modified by: David B Shmoys
Please report errors in award information by writing to: awardsearch@nsf.gov.