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

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

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.