On balancing fairness and efficiency in routing of cooperative vehicle fleets

International audienceShared economy takes an ever increasing part of our everyday activities. Generally, resource sharing is a key to more efficient and effective smart cities and transportation, with the most known applications in car sharing and cooperative hot meal delivery (Uber, Deliveroo, Uber Eats, Glovo, etc.). These fleets are generally composed of self-concerned individually rational agents (drivers) whose interest, in general, is their own efficiency and effectiveness, but also the fairness of the system as a whole; in other words, how their individual gain relates to the gain of the others. Most of the AI state-of-the-art fleet coordination approaches focus only on the efficiency of the fleet as a whole and result in generally unfair solutions without guarantees of the distribution of the workload, cost, or profit or without guarantees on the difference in performance between the worst-off and the best-off vehicle in the fleet. In this light, in this paper, we study the multiple Traveling Salesman problem (mTSP) and propose its two new variations that maximise utilitarian, egalitarian, and elitist social welfare and balance workload and efficiency of the fleet. Moreover, we give examples of how the proposed models influence routes of a fleet's vehicles in small but sufficiently representative problem instances. The computational results show a great diversity of routes depending on the social welfare approach considered. Thanks to the latter, we can balance solutions based on the efficiency and fairness requirements of a fleet at hand