CRII: AF: The Geometry Behind Logistics - Approximation Algorithms for Real-Time Delivery

CRII：AF：物流背后的几何 - 实时交付的近似算法

• 批准号: 1464276
• 负责人: Sharath Raghvendra
• 金额: $ 17.5万
• 依托单位: Virginia Polytechnic Institute and State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-02-01 至 2018-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1464276&HistoricalAwards=false
• 关键词: CRII; AF; Geometry; Behind; Logistics

In the era of instant gratification, consumers expect to receive delivery of goods and services on demand. In an effort to address consumer needs, vendors have adopted routing algorithms with little or no provable guarantee. The algorithms available today are often unreliable and yield higher costs than desired. There are two major difficulties finding effective solutions. First, in many cases, routing decisions need to be made with partial or no information on future requests. The second challenge is related to processing speed. In current solutions, even if all required information is available in advance, it could take several hours to compute an efficient route making real-time routing almost impossible. This project investigates a new approach for real-time algorithms applicable in routing applications. The idea is to use "straight-line" distance between locations as a proxy for the actual road travel distance to design approximation algorithms. The project considers algorithms for certain geometric optimization problems that arise in logistics with a goal of exploring the possibility of a future unified framework in the logistics space. The PI will combine ideas from different research areas including computational geometry, operations research, and online algorithms. In terms of real-world impact, the public and private sectors can benefit from this research. While private sector companies in package delivery and ground transportation services have a vested interest in algorithms providing low-cost routing solutions, real-time routing solutions could also be useful in various humanitarian and military settings. The military, for example, can utilize such algorithms to route supplies quickly. In the case of natural disasters like floods, it is essential to provide timely access to food and aid for people who may be trapped at various locations. Typically in such settings, information about the places where relief is needed changes dynamically, requiring real-time solutions under uncertainty. Further broader impacts include bringing together young researchers with a computer science background and training them across several mathematical topics in an interdisciplinary research plan. This project will be the first to study the design of geometric online algorithms that assist in making provably better decisions under uncertainty. There is some empirical evidence to suggest that utilizing geometry helps in arriving at better solutions. The PI will, however, build theoretical foundations to justify the claim. Additionally, this project will initiate the design of exact and approximation algorithms for a large class of practical pick-up and delivery problems that commonly occur in logistics. While there are approximation algorithms for certain routing problems in geometric settings, these approaches do not typically extend to the pick-up and delivery problems. The mathematical techniques designed here will advance our understanding of how geometry can be utilized to optimize algorithms for a broader class of routing problems.

在即时满足的时代，消费者期望按需获得商品和服务。为了满足消费者的需求，供应商采用了很少或没有可证明保证的路由算法。当今可用的算法通常不可靠，并且产生的成本比预期更高。 寻找有效的解决方案存在两个主要困难。首先，在许多情况下，需要在未来请求的部分信息或没有信息的情况下做出路由决策。第二个挑战与处理速度有关。在当前的解决方案中，即使提前提供所有必需的信息，也可能需要几个小时才能计算出有效的路线，从而几乎不可能实现实时路由。该项目研究了一种适用于路由应用程序的实时算法的新方法。这个想法是使用位置之间的“直线”距离作为实际道路行驶距离的代理来设计近似算法。该项目考虑了物流中出现的某些几何优化问题的算法，目的是探索物流空间中未来统一框架的可能性。 PI 将结合不同研究领域的想法，包括计算几何、运筹学和在线算法。就现实世界的影响而言，公共和私营部门都可以从这项研究中受益。虽然包裹递送和地面运输服务领域的私营公司对提供低成本路线解决方案的算法有着既得利益，但实时路线解决方案也可用于各种人道主义和军事环境。例如，军方可以利用此类算法快速路由补给。在发生洪水等自然灾害时，必须为可能被困在不同地点的人们及时提供食物和援助。通常在这种情况下，有关需要救援的地方的信息会动态变化，需要在不确定的情况下提供实时解决方案。更广泛的影响包括将具有计算机科学背景的年轻研究人员聚集在一起，并在跨学科研究计划中对他们进行多个数学主题的培训。 该项目将是第一个研究几何在线算法设计的项目，该算法有助于在不确定性下做出可证明更好的决策。有一些经验证据表明，利用几何有助于获得更好的解决方案。然而，PI 将建立理论基础来证明这一主张的合理性。此外，该项目还将针对物流中常见的一大类实际取货和送货问题启动精确和近似算法的设计。虽然存在针对几何设置中的某些路由问题的近似算法，但这些方法通常不会扩展到拾取和交付问题。这里设计的数学技术将加深我们对如何利用几何来优化更广泛的路由问题的算法的理解。