A Rolling Horizon Auction Mechanism and Virtual Pricing of Shipping Capacity for Urban Consolidation Centers

Chen Wang, Hoong Chuin Lau, Yun Fong LimICCL 2015 · DOI

TL;DR

This paper introduces a novel rolling horizon auction mechanism for urban consolidation centers (UCCs) to improve the efficiency and profitability of last-mile deliveries. By allowing bids for future delivery slots and incorporating virtual pricing for unused capacity, the system aims to better anticipate demand and secure more profitable contracts.

What Problem Does This Paper Address?

Urban areas face significant challenges with last-mile deliveries, including environmental impact (pollution, congestion), social issues (noise), and economic losses (traffic, low vehicle utilization). To combat these, cities often implement restrictions like time windows and vehicle type mandates. Urban Consolidation Centers (UCCs) emerge as a solution by consolidating goods from various shippers before delivery into the city center, allowing for more efficient use of larger trucks outside the city and freeing up delivery time.

However, existing UCCs often operate on a first-come, first-serve basis, which can be inefficient. While previous work proposed an auction mechanism, it was limited to immediate delivery periods. This paper addresses the need for a more flexible system that accounts for shippers' longer-term planning horizons (weeks in advance) while still allowing for last-minute bids. The core challenge is to design an auction that can effectively allocate limited UCC resources over time, anticipating future demand and maximizing profit, especially in the face of uncertain future bids.

Methods

The paper proposes a rolling horizon auction mechanism for UCCs. This means that instead of a single auction for immediate delivery, auctions are conducted repeatedly, with each auction considering a future planning horizon that overlaps with previous ones. For example, an auction held at the start of Week 1 might accept bids for deliveries in Weeks 1 through 4, while the next auction at the start of Week 2 accepts bids for Weeks 2 through 5.

A key innovation is the introduction of virtual pricing for unused truck capacity. This is achieved by augmenting the profit function of the winner determination problem. This augmentation effectively introduces "virtual bids" that represent the potential future value of unused capacity. This allows the UCC to reserve capacity for potentially more profitable bids in upcoming auctions, even if current bids don't offer sufficient consolidation opportunities. The paper also proposes two approaches for determining these virtual prices: one for known price/volume distributions and another, more realistic approach using Target-oriented Robust Optimization to handle uncertainties in future demand.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and uses simulated data for its experiments.

Key Insights and Ideas

  • Rolling Horizon is Crucial for Real-World Planning: Shippers and carriers often plan deliveries weeks in advance. A rolling horizon auction better reflects this reality than a single-period auction, offering greater flexibility for bidders.
  • Virtual Pricing Unlocks Future Profit: By assigning a "virtual price" to unused capacity, the UCC can strategically reserve resources for more profitable future bids, rather than accepting less profitable current bids that might lead to suboptimal consolidation.
  • Robust Optimization for Uncertainty: In logistics, future demand is inherently uncertain. The paper's use of Target-oriented Robust Optimization provides a method to determine virtual prices that are resilient to these uncertainties, aiming to meet a profit target rather than just maximizing profit in a best-case scenario.
  • Balancing Immediate and Future Gains: The rolling horizon and virtual pricing mechanism allow the UCC to balance securing immediate revenue with positioning itself for higher profits in future auctions.

Key Results

The paper demonstrates the efficacy of its proposed rolling horizon auction through computational experiments.

  • Increased Revenue: Simulation results suggest that by setting virtual prices appropriately, UCCs can generate more revenue from their auctions. Figure 4 shows how revenue changes with different virtual pricing strategies, indicating an optimal range for the virtual price.
  • Commitment in Advance: Figure 2 and 3 show that a significant portion (around 50%) of weekly truck load can be committed one week in advance, validating the rolling horizon approach. The profit associated with these advance commitments is also shown to be substantial.
  • Robust Virtual Pricing: Figure 6 illustrates the convergence of upper and lower bounds for the virtual price parameter ($\gamma$) using the robust optimization approach. Figure 7 shows that the average daily revenue achieved in simulations is very close to the theoretically highest possible revenue, validating the virtual pricing approach's effectiveness.

Limitations and Future Work

  • Assumptions: The model makes assumptions about bid characteristics (e.g., price-volume ratio distribution) and the nature of uncertainties. The robustness of the approach to deviations from these assumptions could be further explored.
  • Computational Complexity: While the paper proposes efficient algorithms, the computational cost of solving the winner determination problem and robust optimization problems in a real-time rolling horizon setting might be a consideration for very large-scale operations.
  • Future Work: The authors suggest further research into more complex scenarios, such as incorporating more detailed truck characteristics, dynamic changes in demand, and exploring different robust optimization formulations. The paper also hints at the need for more sophisticated methods to determine the virtual price in scenarios with unknown distributions and uncertain total volumes.

Summary updated

BibTeX
@inproceedings{wang2015rolling,
  author = {Chen Wang and Hoong Chuin Lau and Yun Fong Lim},
  title = {{A Rolling Horizon Auction Mechanism and Virtual Pricing of Shipping Capacity for Urban Consolidation Centers}},
  booktitle = {ICCL},
  year = {2015},
  doi = {10.1007/978-3-319-24264-4\_29},
}
Figure