Fairness and Efficiency in Social Vehicle Routing Problems

We define Social Vehicle Routing Problems (SVRPs), where preferences of drivers and vehicles, feasibility constraints between vehicles and requests, and network metrics, inform the management of the feet. We propose new algorithms for SVRPs, first returning a feasible matching between drivers and customers and then an optimizing feasible plan for routing the vehicles through their matched locations. We give matching algorithms for achieving fairness (i.e. FEF1, FEQX, FEFX) for drivers, efficiency (i.e. FSW max ) for drivers, and fairness and efficiency (i.e. FSW min ) for customers. Finally, we also give fixed-parameter tractable routing algorithms for fleet fairness (i.e. maxTRAVEL) and fleet efficiency (i.e. totTRAVEL).