:::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
IV. SOLUTION
A. Fair Auction Based Assignment Scheme
The auction algorithm is a widely used approach for solving assignment problems in a distributed manner. The algorithm consists of two phases: the bidding phase and the assignment phase. During the bidding phase, each agent (in our case, each vehicle) makes a bid for each item (i.e., request). Then, during the assignment phase, the item is assigned to the agent with the highest bid. This process is repeated iteratively until there is no change in the assignment. The auction algorithm is known to be optimal and has a polynomial runtime for assignment problems [29].
We modify the standard algorithm to account for fair allocation in addition to optimizing an objective function. In our specific setting, the objective is to minimize the total traveling time, as defined by equation (2), with the requests as the items for auction and the vehicles as the bidders. To consider fairness, we add an intermediate Weight Correction Phase between bidding and assignment. The auction algorithm we use for our vehicle assignment problem is outlined in Alg. 1. In the algorithm, we use two communication primitives: (a) broadcasting function broadcast (msg, V) that sends message msg to all vehicles in V, and (b) receive function recv(v′) that returns the message sent by agent v′. We assume that no packages are lost, and they are received in the same order they are sent. Thus, the receive function recv() is used in blocking mode.
To find the minimum of the objective function, the auction algorithm is used in reverse. We use the travel time with opposite sign to compute the first and second most rewarding requests in lines 5-6 based on the utility value defined in equation (3). Specifically, the vehicles prefer requests that induce lower travel times. During the bidding phase, each available vehicle places a bid for the most desirable request. This utility value takes into account the constraints of maximum waiting time and the delay time for the request. The bid amount is calculated in line 7 and is the sum of the request’s price, the difference between the first and second most desirable request’s utility difference, and a slack constant variable ϵ. This constant is typically set as 1 N , where N is the number of bidders. The price of a request is initialized with the negative of the smallest travel time of any request for the vehicle at line 3. Agents broadcast their preferred request (line 8) to the fleet, and construct the bidding group G of other agents interested in the same request (line 9).
After the bidding phase, a weight correction phase is added to promote fairness. The weight correction is computed using equation (4), which adjusts the original travel utility based on the difference between the vehicle utility and the average utility of all vehicles in the same bidding group G. This allows vehicles with low history utility to increase their bids beyond their actual bidding capability, giving them a greater chance of winning the auction. The weight correction phase aims to balance the auction and prevent vehicles from continuously dominating the auction process.
Finally, during the assignment phase, the request is allocated to the vehicle that offers the highest bid (lines 14- 17), and the auction is executed iteratively. In the subsequent rounds, other vehicles can increase their bids until the highest bid and bidder remain the same. Note that the price of the request is also updated at the end of each round at line 18.
B. Automata-based Route Planning
To conduct an auction in the bidding phase, we need to determine which vehicles are eligible to bid for which requests and what the utility (essentially the route) is for each request. We obtain this information through the construction of product automata.
The formal definition of the product automaton is the following.
C. Fair Rebalancing
(1) The highest location can be the same for all vehicles, which can be seen from the independence with respect to a specific vehicle in equation (5).
(2) Rebalancing itself will require some cost as it will require idle vehicles to move to another location. Therefore the highest potential location that is far away may be less attractive than a location with a smaller value but close.
To deal with these problems, we use a slack parameter and a distance search window. The rebalancing target location is calculated in Alg. 2:
The auction and rebalancing are implemented sequentially. At a given time sample frequency, an auction is conducted to assign available vehicles to every unassigned request. Then the rebalancing is conducted to move idle vehicles to move to better locations. Therefore, vehicles are either in progress to serve requests or in rebalancing to move to another location.
:::info
This paper is available on arxiv under CC by 4.0 Deed (Attribution 4.0 International) license.
:::
