Promoting Two-sided Fairness in Dynamic Vehicle Routing Problem

The document introduces a novel Genetic Algorithm-based approach, 2FairGA, which integrates two-sided fairness and utility optimization to address the Dynamic Vehicle Routing Problem, demonstrating its effectiveness in balancing fairness and utility optimization.

Abstract

Dynamic Vehicle Routing Problem (DVRP), is an extension of the classic Vehicle Routing Problem (VRP), which is a fundamental problem in logistics and transportation. Typically, DVRPs involve two stakeholders: service providers that deliver services to customers and customers who raise requests from different locations. Many real-world applications can be formulated as DVRP such as ridesharing and non-compliance capture. Apart from original objectives like optimising total utility or efficiency, DVRP should also consider fairness for all parties. Unfairness can induce service providers and customers to give up on the systems, leading to negative financial and social impacts. However, most existing DVRP-related applications focus on improving fairness from a single side, and there have been few works considering two-sided fairness and utility optimisation concurrently. To this end, we propose a novel framework, a Two-sided Fairness-aware Genetic Algorithm (named 2FairGA), which expands the genetic algorithm from the original objective solely focusing on utility to multi-objectives that incorporate two-sided fairness. Subsequently, the impact of injecting two fairness definitions into the utility-focused model and the correlation between any pair of the three objectives are explored. Extensive experiments demonstrate the superiority of our proposed framework compared to the state-of-the-art.

Method

The method proposed in this document is a novel Genetic Algorithm-based approach called 2FairGA, which integrates two-sided fairness and utility optimization to address the Dynamic Vehicle Routing Problem (DVRP). It introduces two distinct fairness objectives, service provider-based fairness and customer-based fairness, and integrates them into the Genetic Algorithm. The approach also emphasizes the importance of initial sampling of service providers and utilizes clustering to determine their starting locations, impacting fairness and utility optimization. The method aims to balance utility optimization, improving fairness among service providers, and enhancing fairness among customers in DVRPs. Additionally, it incorporates a Leader-based Random Keys Encoding Scheme (LERK) to handle the dynamic environment and multiple agents in DVRPs. The proposed approach effectively balances fairness and utility optimization, outperforming existing methods that focus solely on utility optimization or fairness.

Main Finding

The main finding of this document is the proposal of a novel Genetic Algorithm-based approach, 2FairGA, which effectively balances two-sided fairness and utility optimization in solving Dynamic Vehicle Routing Problems (DVRP), such as the traveling officer problem and ridesharing. This approach introduces two distinct fairness objectives, service provider-based fairness and customer-based fairness, and integrates them into the Genetic Algorithm, demonstrating superior performance in achieving fairness and utility optimization compared to existing methods. Additionally, the study highlights the importance of initial sampling of service providers and the use of clustering to determine their starting locations, which significantly impacts fairness and utility optimization. The proposed approach addresses the challenge of balancing fairness and utility optimization in DVRP, offering a valuable contribution to the field.

Conclusion

The conclusion of the document is that it proposes a novel approach, 2FairGA, to address the Dynamic Vehicle Routing Problem (DVRP) by integrating two-sided fairness and utility optimization. The study introduces two distinct fairness objectives, service provider-based fairness and customer-based fairness, and integrates them into a Genetic Algorithm. It emphasizes the importance of initial sampling of service providers and the use of clustering to determine their starting locations, impacting fairness and utility optimization. The proposed approach effectively balances fairness and utility optimization, outperforming existing methods that focus solely on utility optimization or fairness. The study's findings contribute to the understanding of fairness and utility optimization in DVRP and offer a novel approach to addressing these challenges.

Keywords

Two-sided fairness, utility optimization, Genetic Algorithm, Dynamic Vehicle Routing Problem, service provider-based fairness, customer-based fairness, fairness metrics, initial sampling, clustering, multi-objective optimization, evolutionary computation, fairness-aware Genetic Algorithm, ablation study, real-world scenarios, constrained K-means clustering, fairness issues, trade-off function, capture effectiveness, ablation study, main contributions.