## 2 Task Allocation and Dispatching
### Stable Marriage Problem  
As we are re-evaluating all uncommitted assignments simultaneously, we can use a stable matching algorithm to compute the assignments. In fact, we can formulate this setting in terms of a Stable Marriage Problem (SMP). Thereby a stable matching (bijection) is sought that matches the elements of two disjoint sets according to mutually stated preferences. Here, at each evaluation step, we wish to match all idle or uncommitted agents \(a_{i}\in A_{idle}\cup A_{uncommitted}\) with any one unassigned or uncommitted move request \(r_{j}\in R_{unassigned}\cup R_{uncommitted}\). The preference of an agent \(a_{i}\) towards a move request \(r_{j}\) is derived from the travel distance \(\tau_{ij}\), such that a move request ranks higher in preference, the lower the associated travel distance \(\tau_{ij}\). Symmetrically, the preference of a move request \(r_{j}\) towards an agent \(a_{i}\) is received in the same way. Thereby the matching is said to be stable in the sense that no pair of agent and move request could be formed that both rank each other higher in preference than their assigned matches. The solution to this formulation can be obtained by the application of the _Gale-Shapley Algorithm_[35]. According to this algorithm stable matching between two equal sized sets of suitors and reviewers are formed iteratively. New matches are formed tentatively by iterating the suitors' preference lists in order. During this process previously formed matches are compared to newly proposed matches until all suitors eventually find a match. If during this procedure previously matched suitors are released by more preferable candidates to the reviewer, they are enqueued again to propose to the next preferable reviewer (c.f., Algorithm 1). This matching is equivalent to the outcome of the asynchronous evaluation of the STTF assignment rule, as thereby agents would be released and reassigned until the matching would arrive at the same stable state in the same way. In order to extend this formulation to resemble the B\({}^{2}\)D\({}^{2}\) method, one would just need to add vehicles committed to their move request to the input set \(a_{i}\in A_{committed}\), whose preference would be derived from the travel distance to complete their current task, plus the empty travel distance to pick up the next. The original formulation of the SMP and the presented solution algorithm assumes both sets are equal in size. In our case, that would correspond to an equal number of agents and move requests. This assumption will obviously not hold true in practice. [PERSON] and [PERSON] [36] investigate this situation and propose different strategies to handle it. Theyrecognise that the algorithm's solution speed degrades significantly when the number of suitors exceeds the number of reviewers. In that case the preference lists of the unmatched suitors need to be iterated exhaustively before they can conclude they will not receive a match. One of the approaches they propose is to swap the role of the two sets depending on their size, such that the smaller set is put into the role of the suitor and the larger acts as the reviewer. They note that, by doing this, a different stable solution may be returned (_female-optimal vs. male-optimal_). We assume the solutions will not actually differ in our case, due to the symmetry in the preference calculation we employ for both sets. Therefore, we integrated this mechanism to achieve the best efficiency for our implementation.