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

Virginia Polytechnic Institute And State University, Blacksburg VA

Investigators

Abstract

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.