Award Abstract # 1537394
Stochastic Optimization Models and Methods for the Sharing Economy

NSF Org: CMMI
Division of Civil, Mechanical, and Manufacturing Innovation
Recipient: CORNELL UNIVERSITY
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: FY 2015 = $200,000.00
History of Investigator:
  • David Shmoys (Principal Investigator)
    shmoys@cs.cornell.edu
  • Shane Henderson (Co-Principal Investigator)
Recipient Sponsored Research Office: Cornell University
341 PINE TREE RD
ITHACA
NY  US  14850-2820
(607)255-5014
Sponsor Congressional District: 19
Primary Place of Performance: Cornell University
136 Hoy Rd
NY  US  14853-3801
Primary Place of Performance
Congressional District:
19
Unique Entity Identifier (UEI): G56PUALJ3KT5
Parent UEI:
NSF Program(s): OE Operations Engineering
Primary Program Source: 01001516DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 076E, 078E, 8023
Program Element Code(s): 006Y00
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.

(Showing: 1 - 10 of 12)
Chong, K.C., S. G. Henderson, and M. E. Lewis. "Two-class routing with admission control and strict priorities" Probability in the Engineering and Informational Sciences , v.32 , 2018 , p.163
Daniel Freund, Shane G Henderson and David B Shmoys "Minimizing multimodular functions and allocating capacity in bike-sharing systems" Integer Programming and Combinatorial Optimization 2017. Proceedings. , 2017 , p.186
Daniel Freund, Shane G. Henderson, David B. Shmoys "Minimizing multimodular functions and allocating capacity in bike-sharing systems" IPCO 2017 , 2017 , p.186
D. J. Eckman and S. G. Henderson. "Reusing search data in ranking and selection: What could possibly go wrong?" ACM Transactions on Modeling and Computer Simulation , v.28 , 2018 , p.Article 1
H. Chung, D. Freund, D.B. Shmoys. "Bike Angels: An Analysis of Citi Bike's Incentive Program" COMPASS '18 Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies , 2018 , p.5:1-5:9 10.1145/3209811.3209866
Naijia (Anna) Dong, David J. Eckman, Matthias Poloczek, Xueqi Zhao and Shane G. Henderson "Comparing the finite-time performance of simulation-optimization algorithms." Proceedings of the 2017 Winter Simulation Conference. , 2017 , p.2206
Nanjing Jian and Shane G. Henderson "An introduction to simulation optimization" Proceedings of the 2015 Winter Simulation Conference , 2015 , p.1780
Nanjing Jian, Daniel Freund, Holly Wiberg and Shane G. Henderson "Simulation optimization for a large-scale bike-sharing system" Proceedings of the 2016 Winter Simulation Conference , 2016 , p.602
Ni, E. C., D. F. Ciocan, S. G. Henderson and S. R. Hunter. "Efficient ranking and selection in parallel computing environments" Operations Research , v.65 , 2017 , p.821
Patrick R. Steele, Shane G. Henderson, David B. Shmoys "Online deliveries to clients on a line" Naval Research Logistics , v.65 , 2018 , p.187
Sijia Ma and Shane G. Henderson "An efficient fully sequential selection procedure guaranteeing probably approximately correct selection" Proceedings of the 2017 Winter Simulation Conference , 2017 , p.2225
(Showing: 1 - 10 of 12)

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.

Print this page

Back to Top of page