Fair and Distributed Vehicle‑Request Assignment Using Auctions and Rebalancing in Mobility‑On‑Demand

:::info Authors:

(1) Kaier Liang, with the Mechanical Engineering and Mechanics Department at Lehigh University, PA, USA;

(2) Cristian-Ioan Vasile, with the Mechanical Engineering and Mechanics Department at Lehigh University, PA, USA.

:::

Table of Links

Abstract and I. Introduction

II. Preliminaries

III. Problem Formulation

IV. Solution

V. Simulation

VI. Conclusions and References

\ Abstract— In this paper, we consider fair assignment of complex requests for Mobility-On-Demand systems. We model the transportation requests as temporal logic formulas that must be satisfied by a fleet of vehicles. We require that the assignment of requests to vehicles is performed in a distributed manner based only on communication between vehicles while ensuring fair allocation. Our approach to the vehicle-request assignment problem is based on a distributed auction scheme with no centralized bidding that leverages utility history correction of bids to improve fairness. Complementarily, we propose a rebalancing scheme that employs rerouting vehicles to more rewarding areas to increase the potential future utility and ensure a fairer utility distribution. We adopt the max-min and deviation of utility as the two criteria for fairness. We demonstrate the methods in the mid-Manhattan map with a large number of requests generated in different probability settings. We show that we increase the fairness between vehicles based on the fairness criteria without degenerating the servicing quality.

\

I. INTRODUCTION

Mobility-On-Demand systems have been recognized as a promising solution to reduce travel costs, traffic congestion, and emissions [1], [2]. Passengers can specify their demands and share vehicles with others, and it can greatly improve transportation for people and goods. However, most research in this area has been focused on the passenger’s perspective, and less attention has been paid to the problem from the driver’s perspective. The assignment objectives are usually centered on minimizing the travel cost, which may not be in accord with the driver’s preferences [3], [4]. Moreover, within the vehicle fleet, due to competition, unfairness may arise due to the uneven distribution of requests, resulting in some vehicles being underutilized.

\ Furthermore, the vehicle assignment problem is usually done via a centralized method, such as optimization [5]– [7]. However, this method requires drivers to share a lot of information with all other vehicles and adhere to the assignment provided by the centralized solver. Although fleets belonging to the same company may be willing to follow the centralized assignment, it may not be suitable for situations with numerous competitors or a large number of independent drivers. As a result, using distributed methods that require vehicles to share limited information with only limited groups can be more favorable [8], [9].

\ Rebalancing policy is also studied to improve efficiency and alleviate congestion problems [10]–[12]. Rebalancing works by moving idle vehicles to another location based on different criteria and purposes, e.g., directly serving other unassigned requests, avoiding congestion, increasing the likelihood of picking up requests, and thus improving performance. However, rebalancing can be also effective in terms of fairness for the vehicles. As idle vehicles being mobilized by rebalancing can also receive more utilities in the future. In this paper, we use the rebalancing approach to improve the fairness for drivers, specifically to balance their collected utilities over a period of time.

\ Another aspect that has received increasing attention, is the idea of moving from simple pick-up and drop-off requests to more complex demands that do not require customers to plan out trips for their tasks. This is especially important for unmanned transportation. Moreover, requests may need to share the same vehicle or use more than one. To accommodate these two problems, we use Linear Temporal Logic (LTL) to model requests in the vehicle routing problem [13]. Temporal logics have been successful in specifying and automating the synthesis of control and motion policies for robots [14]–[17] and dynamical systems [18]–[20]. In this work, we leverage automata-based techniques [21] to compute small routing problems with LTL requests, and employ a distributed auction algorithm to assign the requests to vehicles.

\ The contributions of this work are the following: 1) We define a distributed auction assignment algorithm with temporal logic demands where all computation is performed based on inter-vehicle communication and no vehicle has a special role (e.g., centralized bidding), 2) We propose a rebalancing scheme to move idle vehicles to more rewarding locations that takes into account fair distribution of vehicles’ cumulated utility, 3) We show via case studies in a large environment in mid-Manhattan with a large fleet of vehicles and a number of requests that our distributed assignment method does not degenerate the performance of the Mobilityon-Demand system compared to a centralized approach. Moreover, our algorithms significantly reduce the deviation of utility and increase the minimum utility, which leads to fairer distribution for vehicles.

\

II. PRELIMINARIES

\

\

\

\

:::info This paper is available on arxiv under CC by 4.0 Deed (Attribution 4.0 International) license.

:::

\