Communications of the ACM
Home/Magazine Archive/November 2021 (Vol. 64, No. 11)/Technical Perspective: Finding the Sweet Spot Amid.../Full Text
Research highlights
Technical Perspective: Finding the Sweet Spot Amid Accuracy and Performance
Credit: Getty Images
The field of transportation and logistics has witnessed fundamental transformations in the last decade, due to the convergence of seemingly unrelated technologies. The fast pace of innovations has been particularly striking for an industry that had been relatively stagnant for a long time.
Taxi services were born in England where a public coach service for hire was first documented in 1605. The Hackney Carriage Act, which legalized horse-drawn carriages for hire, was passed in Parliament in 1635, and a similar service was started in Paris in 1637. Public transit was invented by Blaise Pascal in 1662 through a service known as the "carriage," which was quite popular and operated for 15 years. Both taxi services and public transit adopted new technologies as they became available. Electric battery-powered taxis became available in the streets of London in 1897, and were introduced in New York city the same year. The late 1800s saw the emergence of electric and motor buses. Taxis became widespread in the early 20th century, adopting taxi meters and then, in the late 1940s, two-way radios allowing for communications between drivers and dispatching offices. The automation and optimization of these dispatching services started in the 1980s, but no major evolution took place for several decades thereafter.
This radically changed in the late 2000s through the convergence of multiple technologies, and their embodiment into a single device: the smartphone (the iPhone initially). Transportation network companies (TNCs), such as Uber and Lyft, translated the unique opportunity to connect drivers, riders, and dispatching services everywhere and at massive scale (the "missing ingredient" of Logan Green, co-founder and CEO of Lyft) into novel business models. Ubiquitous connectivity, together with subsequent integrations of GPS navigation, location services, and mapping software, revolutionized transportation and positioned TNCs as a highly visible face of the digital "gig economy." GPS-enabled devices also became sensors, collecting the mobility trajectories of millions of users, nowcasting traffic volumes, and estimating travel times. Food, grocery delivery services, as well as crowdsourced "on the way" deliveries for enterprises and small businesses quickly followed. Simultaneously, e-commerce was in the process of fundamentally transforming the shopping experience and the supply chains necessary to sustain it. Packages could now be delivered to front doors, creating massive supply chains and significant challenges in last-mile deliveries.
These last two decades also witnessed impressive progress in optimization technology far from the public view. For instance, mixed integer programming solvers improved by two orders of magnitude from 1998 to 2012, both in terms of speedups in computational times and instances solved within predefined time limits. Optimization solvers were already running significant parts of the economy, dispatching electricity every five minutes to balance generation and consumption, clearing markets for organ exchanges, running steel plants from the furnace to the end products used to build cars, scheduling supply chains, and dispatching logistic systems. But, interestingly, these new economy innovations rely on the ability to connect customers, drivers, and optimization technology through mobile applications and a cloud computing infrastructure.
How this convergence of technologies will impact the economy of the future and society at large is an interesting question to ponder. Will it remain the exclusivity of large corporations and a few startups, or will the software platforms driving this innovation ecosystem become widely available for a wide range of businesses? This open question is precisely why the following paper is exciting: It makes accessible, for the first time, an end-to-end cloud service that produces traffic-aware, real-time dispatching of agents under complex constraints. The platform leverages GPS traces, traffic predictions, state-of-the-art algorithms for time-dependent shortest paths, large neighborhood search (an optimization technique to find high-quality solutions quickly), and cloud computing to provide multi-itinerary optimization as a service. The authors show that each of these components is critical for the success of the service.
Ignoring traffic conditions (for example, using free-flow speeds) significantly degrades the quality of the service, while optimizing for the worst-case results in largely suboptimal solutions. Similarly, advanced optimization techniques that originated from constraint programming enable the platform to meet the runtime constraints, while capturing the complexity of real-world applications. The paper is particularly timely, partly because of business implications as society may be slowly emerging from a pandemic, and partly because of the agenda it sets for the scientific community. The wide availability of such platforms may be the "missing ingredient" for many businesses to transition to a new economy, democratizing access to technologies that require considerable expertise in many branches of computer science and related disciplines. The paper also highlights the need to model the world with high fidelity in the next generation of optimization algorithms. This is important at a time where society may expect another wave of technology innovations, including drones, autonomous robots, and massive electrification of transportation systems and supply chains.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.
No entries found