Decentralizing Coordination in Open Vehicle Fleets for Scalableand Dynamic Task Allocation

One of the major challenges in the coordination of large, open, collaborative, and commercial vehicle fleets is dynamic taskallocation. Self-concerned individually rational vehicle drivers have both local and global objectives, which require coordinationusing some fair and efficient task allocation method. In this paper, we review the literature on scalable and dynamic task allocationfocusing on deterministic and dynamic two-dimensional linear assignment problems. We focus on multiagent system repre-sentation of open vehicle fleets where dynamically appearing vehicles are represented by software agents that should be allocatedto a set of dynamically appearing tasks. We give a comparison and critical analysis of recent research results focusing oncentralized, distributed, and decentralized solution approaches. Moreover, we propose mathematical models for dynamic versionsof the following assignment problems well known in combinatorial optimization: the assignment problem, bottleneck assignmentproblem, fair matching problem, dynamic minimum deviation assignment problem,Σk-assignment problem, the semiassignmentproblem, the assignment problem with side constraints, and the assignment problem while recognizing agent qualification; allwhile considering the main aspect of open vehicle fleets: random arrival of tasks and vehicles (agents) that may become availableafter assisting previous tasks or by participating in the fleet at times based on individual intere