Search

Over the past decade, GPS-enabled traffic applications such as Google Maps and Waze have become ubiquitous and have had a significant influence on billions of daily commuters' travel patterns. A consequence of the online route suggestions of such applications, for example, via greedy routing, has often been an increase in traffic congestion since the induced travel patterns may be far from the system optimum. Spurred by the widespread impact of traffic applications on travel patterns, this work studies online traffic routing in the context of capacity-constrained parallel road networks and analyzes this problem from two perspectives. First, we perform a worst-case analysis to identify the limits of deterministic online routing. Although we find that deterministic online algorithms achieve finite, problem/instance-dependent competitive ratios in special cases, we show that for a general setting the competitive ratio is unbounded. This result motivates us to move beyond worst-case analysis. Here, we consider algorithms that exploit knowledge of past problem instances and show how to design data-driven algorithms whose performance can be quantified and formally generalized to unseen future instances. We then present numerical experiments based on an application case for the San Francisco Bay Area to evaluate the performance of the proposed data-driven algorithms compared with the greedy algorithm and two look-ahead heuristics with access to additional information on the values of time and arrival time parameters of users. Our results show that the developed data-driven algorithms outperform commonly used greedy online-routing algorithms. Furthermore, our work sheds light on the interplay between data availability and achievable solution quality. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Funding: This work was supported by National Science Foundation (NSF) Award 1830554 and by the German Research Foundation (DFG) under [Grant 449261765]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.1275. [ABSTRACT FROM AUTHOR]

In e-commerce warehouses, online retailers increase their efficiency by using a mixed-shelves (or scattered storage) concept, where unit loads are purposefully broken down into single items, which are individually stored in multiple locations. Irrespective of the stock keeping units a customer jointly orders, this storage strategy increases the likelihood that somewhere in the warehouse the items of the requested stock keeping units will be in close vicinity, which may significantly reduce an order picker's unproductive walking time. This paper optimizes picker routing through such mixed-shelves warehouses. Specifically, we introduce a generic exact algorithmic framework that covers a multitude of picking policies, independently of the underlying picking zone layout, and is suitable for real-time applications. This framework embeds a bidirectional layered graph algorithm that provides the best known performance for the simple picking problem with a single depot and no further attributes. We compare three different real-world e-commerce warehouse settings that differ slightly in their application of scattered storage and in their picking policies. Based on these, we derive additional layouts and settings that yield further managerial insights. Our results reveal that the right combination of drop-off points, dynamic batching, the utilization of picking carts, and the picking zone layout can greatly improve the picking performance. In particular, some combinations of policies yield efficiency increases of more than 30% compared with standard policies currently used in practice. This paper was accepted by Chung Piaw Teo, optimization. [ABSTRACT FROM AUTHOR]

Scheduling High-Capacity Shared Rides via Hypergraph Matchings Sharing economies, such as Uber Pool and Lyft Shared Saver, are becoming ubiquitous in modern transportation services. "Online Hypergraph Matching with Delays" by M. Pavone, A. Saberi, M. Schiffer, and M. Tsao studies an online hypergraph matching problem inspired by on-demand scheduling of shared rides in ridehailing systems. They formulate a ridesharing problem through a weighted hypergraph in which riders are represented by vertices and hyperedges and the associated weights represent the utility of serving the associated vertices groups of riders with a single vehicle. A ridesharing algorithm is, thus, a matching algorithm for the hypergraph. To model the on-demand nature of ridesharing, riders arrive sequentially and must either be quickly and irrevocably matched or discarded. In this work, the authors present a polynomial-time algorithm based on randomized batching and prove that it has the optimal worst-case performance. We study an online hypergraph matching problem inspired by ridesharing and delivery applications. The vertices of a hypergraph are revealed sequentially and must be matched shortly thereafter, otherwise they will leave the system in favor of an outside option. Hyperedges are revealed to the algorithm once all of its vertices have arrived, and can only be included into the matching before any of its vertices leave the system. The cardinality of hyperedges are bounded by a small constant which represents the capacity of service vehicles. We study utility maximization and cost minimization objectives in this model. In the utility maximization setting, we present a polynomial time algorithm which provably achieves the optimal competitive ratio provided that the vehicle capacity is at least 3. For the cost minimization setting, we assume costs are monotone, which is a natural assumption in ridesharing and delivery problems. When the vehicle capacity is 2, we present a polynomial-time thresholding algorithm and prove that it has the optimal competitive ratio among deterministic algorithms. For higher vehicle capacities, we show that the performance of a randomized batching algorithm is within a small constant of the optimal competitive ratio achievable in polynomial time. [ABSTRACT FROM AUTHOR]