Prophet Inequalities for a New Class of Overbooking Problems in Container Shipping

In the container shipping industry, overbooking is largely driven by mistrust between shippers and carriers. Because contracts are often weak and unenforceable, shippers frequently fail to deliver containers as agreed. To protect themselves from these no-shows, carriers routinely overbook. This practice is estimated to cause $30–40 billion in losses each year, highlighting the urgent need for a solution. In this paper, we propose and study a deposit-based booking system that draws inspiration from current practices that are successful in mitigating no-show behavior and overbooking in the container shipping industry. Specifically, we consider a reservation system where inquiring shippers book cargo space using a customized deposit. The carrier, upon accepting the shipper’s booking request, matches the shipper’s deposit with a deposit of their own of equal size. If either party reneges on the agreement, the defaulting party loses their deposit to the more trustworthy party. However, if both parties uphold their side of the deal, the deposits are returned in full to both sides. Under this booking mechanism, we study the carrier’s sequential online booking problem, which gives rise to a new class of revenue management problems with overbooking and no-show behavior that share only superficial commonalities with existing frameworks. First, we consider the coupled show-up setting, where shippers’ show-up decisions are correlated through an external spot market that offers an outside option for each shipper. In this setting, we provide a randomized threshold-based policy that achieves a competitive ratio of 0.819. Moreover, we show no policy (randomized or deterministic) can achieve a competitive ratio that eclipses 0.853. Next, we consider an alternative setting where each shipper shows up to claim a slot independently of other shippers. In this so-called independent show-up setting, we provide a simple greedy-like policy that is $\frac{1}{2}$-competitive as the capacity of the liner is scaled to infinity. Additionally, for such large-capacity systems, we show that any deterministic policy can at best be 0.63-competitive. These theoretical developments are complemented by an extensive set of numerical experiments, where we test the efficacy of our proposed policies and find that their practical performance is near-optimal not only with regard to the profits they garner, but also from utilization and overbooking perspectives.

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2024.0842.