=Paper=
{{Paper
|id=Vol-3276/SSS-22_FinalPaper_30
|storemode=property
|title=Fairness for Drivers with Additive Profits in
Emerging Vehicle Routing Problems
|pdfUrl=https://ceur-ws.org/Vol-3276/SSS-22_FinalPaper_30.pdf
|volume=Vol-3276
|authors=Martin Aleksandrov
|dblpUrl=https://dblp.org/rec/conf/aaaiss/Aleksandrov22
}}
==Fairness for Drivers with Additive Profits in
Emerging Vehicle Routing Problems==
https://ceur-ws.org/Vol-3276/SSS-22_FinalPaper_30.pdf
Fairness for Drivers with Additive Profits
in Emerging Vehicle Routing Problems
Martin Aleksandrov
Technische Universität Berlin
Ernst-Reuter-Platz, 10587 Berlin, Germany
martin.aleksandrov@tu-berlin.de
Abstract That is, a given vehicle may be feasible or not for a given
We consider semi-decentralised fair divisions in the context
request. We model this by using a hard feasibility indicator.
of emerging VRPs, where not just the preferences of drivers For instance, suppose that a given vehicle is feasible only for
play a crucial role, but also the feasibilities of their vehicles. packages that can be loaded inside its trunk, subject to max-
For such settings, we propose three new fairness notions: imising the total number of packages. This is known as the
responsive FEF1, responsive FEQX, and responsive FEFX, loading problem and it is NP-hard in general (Männel and
which capture the responsiveness of drivers for requests. For Bortfeldt 2018). In this context, if a given request can be
such settings, we also give two new algorithms. Our first al- loaded in the trunk of a given vehicle in some solution to the
gorithm returns responsive FEF1 assignments. Our second al- loading problem, then we set the corresponding feasibility
gorithm returns responsive FEQX assignments, as well as re- indicator to one, and else we set it to zero. We partly over-
sponsive FEFX assignments in a practical case. come such intractabilities by decentralising some of the fea-
sibilities of vehicles and letting their drivers decide whether
1 Introduction they are feasible or not for requests. In addition, we con-
Let us consider the classical Vehicle Routing Problem sider the possibility of decentralising not just hard feasibil-
(VRPs) (Dantzig and Ramser 1959). In this problem, there ities of vehicles, but also some of the profit preferences of
is a single vehicle and a set of visit requests. Generalisations their drivers. Indeed, many real-world applications are ac-
of the VRP consider a fleet of multiple vehicles and a set tually semi-decentralised. In such applications, drivers can
of pickup-and-delivery requests (Savelsbergh and Sol 1995). therefore be responsive or not.
We initiate a study of emerging VRPs. Applications of such Realistic features such as feasibilities and responsiveness
problems include autonomous vehicles, connected vehicles, require that we modify centralised fairness notions and cen-
electric vehicles, garbage vehicles, and data-driven logistics. tralised fairness algorithms so that they reflect the nature
The 2020 EU Strategy for Sustainable and Smart Mobility of our model. We do such modifications in our work. Our
has formulated public mobility Transport Policy Flagships, model can thus be simulated in centralised, decentralised,
according to which the transition to emerging VRPs must as well as on various Internet and mobile settings, where
involve the preferences of individuals. One objective in this some request information is known and some missing infor-
strategy is achieving trust. Among explainability and safety, mation is revealed as drivers are prompted for responses. If
trust requires that vehicles are used fairly. drivers respond, then they are online. Otherwise, they are of-
In this paper, we provide an early qualitative analysis of fline until the next time they are prompted for responses. For
fairness for drivers. We thus propose a fair division assign- example, the dispatchers of Bonds Express often communi-
ment model, where a fleet of vehicles and a set of requests cate for work with drivers via SMS messages (Aleksandrov
are available in a fixed time interval, and each driver charge et al. 2013). We next give an outline of our paper.
the customer of each given request with some cost. We con- Outline: We explain our contributions in Section 2 and re-
sider driver-dependent costs (i.e. request costs depend on view related literature in Section 3. We define formally our
drivers) and driver-independent costs for customers. We model in Section 4. For this model, in Sections 5, 6, and 7,
also consider additive profits for drivers (i.e. the profit for we show that existing fairness notions such as EF1, EQX,
some requests is sum of the request costs). Like in many and EFX need to be modified. In response, we propose three
mod-els for fair division (Brams and Taylor 1996) and fair new notions: responsive FEF1, responsive FEQX, and re-
public decision making (Conitzer, Freeman, and Shah sponsive FEFX. With driver-dependent costs, we prove in
2017), addi-tivity is a common assumption. Unlike many Section 8 that a responsive FEF1 assignment can be com-
such models, we consider two additional features: vehicle puted in polynomial time and in Section 9 that a respon-
feasibilities and driver responsiveness. sive FEQX assignment can also be computed in polynomial
time. With driver-independent costs, we give in Section 10 a
___________________________________ similar tractability result for a responsive FEFX assignment.
In T. Kido, K. Takadama (Eds.), Proceedings of the AAAI 2022 Spring Symposium Finally, we draw our conclusions in Section 11.
“How Fair is Fair? Achieving Wellbeing AI”, Stanford University, Palo Alto, California,
USA, March 21–23, 2022. Copyright © 2022 for this paper by its authors. Use
permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
55