Contract-based Inter-user Usage Coordination in Free-floating Car Sharing

Kentaro Takahira, Shigeo MatsubaraAAAI 2021 · DOI

Abstract

Free-floating car-sharing (FFCS) services provide high flexibility but often suffer from vehicle distribution imbalances. This paper proposes a distributed coordination mechanism using a Vickrey-Clarke-Groves (VCG) auction to facilitate negotiation between pick-up and drop-off users. By incorporating a calculated "relocation value" ($v_R$) for vehicles, the system effectively reduces imbalances and increases social surplus without the need for complex centralized demand predictions.

Introduction

Free-floating car-sharing (FFCS) platforms allow users to pick up and drop off vehicles at any location within a designated service area. While this flexibility is a core value proposition, it leads to significant operational challenges, primarily the "imbalance problem," where vehicles accumulate in low-demand areas while high-demand zones face shortages.

Existing solutions typically rely on centralized regulation, where operators use historical data to predict demand and set incentives. However, these approaches face hurdles in data accuracy at the GPS level, computational scalability, and the limitations of rigid spatial partitioning. This research shifts the paradigm from centralized control to distributed negotiation among users, treating the car-sharing system as a multi-agent environment.

Methodology

The proposed system coordinates users through a contract-based auction mechanism that treats the service area as a continuous space rather than a grid.

The VCG Auction Mechanism

When a pick-up request is made, the system initiates a VCG auction involving the pick-up user and nearby drop-off users.

  • User Bids: Pick-up users bid based on their disutility (walking and waiting costs). Drop-off users bid based on the additional cost of changing their intended destination to a location more convenient for the pick-up user.
  • Relocation Value ($v_R$): A key innovation is the inclusion of a "social value" for vehicle relocation. This value quantifies the future utility of a vehicle based on its drop-off location's demand potential, derived from the probability of finding a subsequent user at that specific location.
  • Strategy-Proofness: By utilizing the VCG mechanism, the system ensures that it is in every user's best interest to report their true costs and intended destinations.

Experimental Setup

The mechanism was evaluated using a custom FFCS simulator designed to reflect real-world urban dynamics, with parameters derived from Car2go data and existing literature.

Table 1: Simulation parameters including service area dimensions, speeds, and demand configurations.

The study tested three demand structures—Uniform (0 Hubs), Concentrated (1 Hub), and Multi-hub (5 Hubs)—comparing the auction-based method against a non-regulation scenario and a state-of-the-art centralized incentive baseline (DBP-UCB).

Results and Discussion

The experimental results demonstrate the superiority of the auction-based coordination mechanism across various metrics and demand scenarios.

Table 2: Experimental results comparing Service Level, Social Surplus, and Operator's Profit.

Key Findings

  • Increased Social Surplus: The auction-based method consistently outperformed the baseline in terms of social surplus. Notably, the inclusion of the relocation value ($v_R$) was most effective in scenarios with lower vehicle density (50 vehicles).
  • Enhanced Service Levels: The percentage of users successfully finding a vehicle increased in nearly all experimental cases, particularly in high-concentration "1 Hub" scenarios, which are common in real-world urban centers.
  • Scalability and Speed: The system demonstrated high computational efficiency, with contracts determined in under 0.1 seconds. A simulation of 1,000 vehicles and 1,000 requests finished in under 100 seconds on standard hardware.

Conclusion

This research highlights that local, peer-to-peer negotiations can effectively drive global system improvements in FFCS. By treating the service area as a continuous space and quantifying the value of vehicle locations, the proposed mechanism offers a scalable alternative to centralized regulation. Future work will focus on addressing the operator's deficit inherent in VCG payments and incorporating real-world uncertainties such as traffic congestion and parking difficulties.

Summary updated

BibTeX
@inproceedings{takahira2021contract,
  author = {Kentaro Takahira and Shigeo Matsubara},
  title = {{Contract-based Inter-user Usage Coordination in Free-floating Car Sharing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17354},
}
Figure