Collaborative Research: Performance Guarantees for Approximate Dynamic Programming Approaches to Pricing and Capacity Management

协作研究：定价和容量管理的近似动态规划方法的性能保证

基本信息

批准号：
1824860
负责人：
Paat Rusmevichientong
金额：
$ 17.51万
依托单位：
University of Southern California
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-09-01 至 2022-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1824860&HistoricalAwards=false
关键词：
Collaborative Research Performance Guarantees Approximate

项目摘要

This project will benefit the U.S. economy and public quality of life by developing new solution methods for problems that involve dynamically managing the prices and limited resources to serve uncertain customer demands. Such pricing and capacity management problems occur in many settings, including selling processing capacity in cloud computing, pricing itineraries in airlines and hotels, and matching drivers with passengers in on-demand transportation. In these problems, finding the optimal course of action at any point in time requires keeping track of a large amount of information, including remaining processing times on thousands of servers, capacities left on hundreds of flights, and locations of thousands of drivers, along with forecasts of future needs. Existing solution methods often ignore the uncertainty in demand or the detailed customer arrival process. The fundamental research of this project will provide new knowledge and techniques for solving these challenging problems. The techniques will apply to a wide range of applications, will scale to large-scale problems brought by the information age, and will help make decisions at a rapid rate. This project will also broaden the participation of underrepresented groups and positively impact engineering education through the development of online certificate programs, shared data-sets, and industry collaborations. Dynamic programming is a general framework that can address dynamic decision-making problems under uncertainty, but dynamic programming formulations often end up with high-dimensional state variables, which make them difficult to solve. This research will develop approximate dynamic programming methods for a variety of pricing and capacity management problems that frequently occur in practice, including (a) pricing problems with reusable products, applicable to cloud computing systems where processing capacity is reusable, (b) pricing problems over a network of resources, applicable to airlines and hotels where there is an underlying network of resources and the sale of a product consumes a combination of resources, and (c) product pairing problems for upselling, applicable to online retail where additional product recommendations are made during checkout. The approximate dynamic programming methods will have performance guarantees. Some of these performance guarantees, especially those for pricing over a network of resources, will be the first of its kind. The methods will be flexible for a wide range of applications and will be scalable to industrial problem instances.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目将通过开发新的解决方法来解决涉及动态管理价格和有限资源以满足不确定的客户需求的问题，从而使美国经济和公共生活质量受益。此类定价和容量管理问题在许多情况下都会发生，包括销售云计算中的处理能力、航空公司和酒店的行程定价以及按需运输中的司机与乘客匹配。在这些问题中，在任何时间点找到最佳行动方案需要跟踪大量信息，包括数千台服务器上的剩余处理时间、数百个航班的剩余容量以及数千名驾驶员的位置，以及对未来需求的预测。现有的解决方法常常忽略需求的不确定性或详细的客户到达过程。该项目的基础研究将为解决这些具有挑战性的问题提供新的知识和技术。这些技术将适用于广泛的应用，将扩展到解决信息时代带来的大规模问题，并有助于快速做出决策。该项目还将扩大代表性不足群体的参与，并通过开发在线证书项目、共享数据集和行业合作对工程教育产生积极影响。动态规划是一种可以解决不确定性下动态决策问题的通用框架，但动态规划公式通常最终会得到高维状态变量，这使得它们难以求解。本研究将为实践中经常出现的各种定价和容量管理问题开发近似动态规划方法，包括（a）可重用产品的定价问题，适用于处理能力可重用的云计算系统，（b）资源网络，适用于航空公司和酒店，其中存在基础资源网络，并且产品的销售消耗资源组合，以及（c）追加销售的产品配对问题，适用于提出额外产品推荐的在线零售结账时。近似的动态规划方法会有性能保证。其中一些性能保证，尤其是通过资源网络定价的性能保证，将是同类中的首创。这些方法将灵活地适用于广泛的应用，并且可以扩展到工业问题实例。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。