We consider semi-decentralised fair divisions in the context of emerging VRPs, where not just the preferences of drivers play a crucial role, but also the feasibilities of their vehicles. For such settings, we propose three new fairness notions: responsive FEF1, responsive FEQX, and responsive FEFX, which capture the responsiveness of drivers for requests. For such settings, we also give two new algorithms. Our first algorithm returns responsive FEF1 assignments. Our second algorithm returns responsive FEQX assignments, as well as responsive FEFX assignments in a practical case.
Let us consider the classical Vehicle Routing Problem (VRPs) (Dantzig and Ramser 1959). In this problem, there is a single vehicle and a set of visit requests. Generalisations of the VRP consider a fleet of multiple vehicles and a set of pickup-and-delivery requests (Savelsbergh and Sol 1995). We initiate a study of emerging VRPs. Applications of such problems include autonomous vehicles, connected vehicles, electric vehicles, garbage vehicles, and data-driven logistics. The 2020 EU Strategy for Sustainable and Smart Mobility has formulated public mobility Transport Policy Flagships, according to which the transition to emerging VRPs must involve the preferences of individuals. One objective in this strategy is achieving trust. Among explainability and safety, trust requires that vehicles are used fairly.
In this paper, we provide an early qualitative analysis of fairness for drivers. We thus propose a fair division assignment model, where a fleet of vehicles and a set of requests are available in a fixed time interval, and each driver charge the customer of each given request with some cost. We consider driver-dependent costs (i.e. request costs depend on drivers) and driver-independent costs for customers. We also consider additive profits for drivers (i.e. the profit for some requests is sum of the request costs). Like in many mod-els for fair division (Brams and Taylor 1996) and fair public decision making (Conitzer, Freeman, and Shah 2017), addi-tivity is a common assumption. Unlike many such models, we consider two additional features: vehicle feasibilities and driver responsiveness.
That is, a given vehicle may be feasible or not for a given request. We model this by using a hard feasibility indicator. For instance, suppose that a given vehicle is feasible only for packages that can be loaded inside its trunk, subject to maximising the total number of packages. This is known as the loading problem and it is NP-hard in general (Männel and Bortfeldt 2018). In this context, if a given request can be loaded in the trunk of a given vehicle in some solution to the loading problem, then we set the corresponding feasibility indicator to one, and else we set it to zero. We partly overcome such intractabilities by decentralising some of the feasibilities of vehicles and letting their drivers decide whether they are feasible or not for requests. In addition, we consider the possibility of decentralising not just hard feasibilities of vehicles, but also some of the profit preferences of their drivers. Indeed, many real-world applications are actually semi-decentralised. In such applications, drivers can therefore be responsive or not.
Realistic features such as feasibilities and responsiveness require that we modify centralised fairness notions and centralised fairness algorithms so that they reflect the nature of our model. We do such modifications in our work. Our model can thus be simulated in centralised, decentralised, as well as on various Internet and mobile settings, where some request information is known and some missing information is revealed as drivers are prompted for responses. If drivers respond, then they are online. Otherwise, they are offline until the next time they are prompted for responses. For example, the dispatchers of Bonds Express often communicate for work with drivers via SMS messages (Aleksandrov et al. 2013). We next give an outline of our paper.
Outline: We explain our contributions in Section 2 and review related literature in Section 3. We define formally our model in Section 4. For this model, in Sections 5, 6, and 7, we show that existing fairness notions such as EF1, EQX, and EFX need to be modified. In response, we propose three new notions: responsive FEF1, responsive FEQX, and responsive FEFX. With driver-dependent costs, we prove in Section 8 that a responsive FEF1 assignment can be computed in polynomial time and in Section 9 that a responsive 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. Finally, we draw our conclusions in Section 11.