AF: Small: Approximation Algorithms for Problems in Logistics

AF：小：物流问题的近似算法

• 批准号: 1526067
• 负责人: David Shmoys
• 金额: $ 40万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526067&HistoricalAwards=false
• 关键词: AF; Small; Approximation; Algorithms; Problems

Logistics problems lie at the heart of the functioning of today's economy: how best to have packages routed to their intended destination, how best to design the supply networks for retailers, how best to manage the inventory levels for items in a retailer's supply chain. This is just a small sample of the types of optimization problems that must be routinely solved for the efficient management of resources in today's business world. Each of these problems can be formulated as a precise mathematical optimization problem - by specifying exactly what constitutes a feasible solution, something that can be implemented in practice, and using an objective function that captures how good that solution is, the PI gives a precise meaning to the issue of finding the best solution to a particular logistics problem. Unfortunately, most of these problems, from the perspective of computational complexity, belong to a class of problems that are believed to be intractable, and hence an easier goal is posited: to design efficient algorithms that find solutions that are provably near-optimal, in that the solutions found are guaranteed to be within a specified percent of the best possible.Tools in optimization and analytics will play a foundational role in the training of the next generation of students who will go on to invent and manage the disruptive industries of the future. Incorporating cutting-edge ideas from algorithm design for the problems in logistics is an effective way to get students to understand the potential that these tools have. This project, by both training PhD students who will be future leaders in both academia and industry, as well as by providing a link between this line of research and the undergraduate classroom, will help effectively educate this next generation.This project focuses on a number of discrete optimization problems that arise in logistics, including the notorious traveling salesman problem (as well as a closely related vehicle-routing problem, where the aim is not merely to find the shortest route covering a set of points, but the aim is to reach each point in the set so that each point is reached along the way not much later than a special-purpose shortest path just serving that one destination), a central network-design problem of installing a hub-and-spoke service network, so as to minimize the cost of the hubs installed plus the service costs implicit in that spoke selection (while respecting capacity constraints on the number of spokes that can be served by one hub), a number of multi-item inventory management problems that model the tradeoffs between the fixed costs in placing bulk orders versus the cost of maintaining the additional inventory until it is needed, and the bin-packing problem, in which one aims to partition items of given sizes into as few parts as possible, while respecting the constraint that each part is within a given capacity bound. This project focuses on the development of new algorithmic techniques to produce good solutions for these critical problems. One element that is frequently present in the design of an effective algorithm for these problems, either from a theoretical or a practical vantage point, is the development of a mathematical programming relaxation of the problem that enables the efficient computation of bounds that can prove that a solution at hand is nearly optimal. This project will pursue a number of new directions for developing extended formulations that are stronger than traditional approaches. This project will address a number of specific discrete deterministic & stochastic optimization problems, focusing on a few problems that appear to be at the right level of abstraction -- simple enough to permit the design & analysis of algorithms with performance guarantees -- and complex enough so that algorithmic insights gained from these stylized models will translate in a meaningful way to the motivating real-world application.

物流问题是当今经济运作的核心：如何最好地将包裹运送到预定目的地，如何最好地为零售商设计供应网络，如何最好地管理零售商供应链中物品的库存水平。这只是当今商业世界中为了有效管理资源而必须例行解决的优化问题类型的一小部分。这些问题中的每一个都可以被公式化为精确的数学优化问题-通过精确地指定什么构成可行的解决方案，可以在实践中实现的东西，并使用捕获该解决方案有多好的目标函数，PI为找到特定物流问题的最佳解决方案的问题提供了精确的含义。不幸的是，从计算复杂性的角度来看，这些问题中的大多数属于一类被认为是棘手的问题，因此提出了一个更容易的目标：设计有效的算法来找到可证明接近最优的解决方案，因为找到的解决方案保证在最佳可能性的指定百分比内。优化和分析工具将在培养下一代学生，他们将继续发明和管理未来的颠覆性行业。从算法设计中阐述物流问题的前沿思想是让学生了解这些工具潜力的有效方法。 该项目通过培养未来学术界和工业界的领导者博士生，以及提供这一研究领域与本科生课堂之间的联系，将有助于有效地教育下一代。该项目侧重于物流中出现的一些离散优化问题，包括臭名昭著的旅行商问题（以及一个密切相关的车辆路线问题，其目的不仅仅是找到覆盖一组点的最短路线，但目标是到达集合中的每个点，使得沿着该路径到达每个点不会比仅服务于该目的地的专用最短路径晚太多）这是一个中心网络设计问题，即安装一个轴辐式服务网络，以使安装的中心成本加上该辐条选择中隐含的服务成本最小化（同时考虑到一个中心可以服务的辐条数量的容量限制），多个多-项目库存管理问题，模型之间的权衡固定成本，在放置批量订单与成本，维持额外的库存，直到它是必要的，和装箱问题，其中一个目的是分区项目的给定大小到尽可能少的部分，同时尊重的约束，每个部分是在一个给定的能力范围内。该项目的重点是开发新的算法技术，为这些关键问题提供良好的解决方案。一个元素是经常出现在设计一个有效的算法，这些问题，无论是从理论或实际的Vantage地位，是一个数学规划放松的问题，使有效的计算界限，可以证明，解决方案是近最佳的发展。该项目将寻求一些新的方向，以开发比传统方法更强大的扩展配方。该项目将解决一些特定的离散确定性随机优化问题，重点关注一些似乎处于正确抽象级别的问题-足够简单，可以对具有性能保证的算法进行设计分析-并且足够复杂，以便从这些程式化模型中获得的算法见解将以有意义的方式转化为激励现实世界的应用程序。