Vehicle Routing Problem with Fair Profits and Time Windows (VRP-FPTW)

Abstract

In crowdsourced delivery organizations, where individual vehicles with shared common goals may have conflicting individual interests, the preference is for collaboration over competition, provided it is less costly. However, achieving a balance between the efficiency of individual vehicles and the overall fleet poses a challenge. This paper introduces a novel Vehicle Routing Problem with Fair Profits and Time Windows (VRP-FPTW), which aims to meet customer demand and stringent time windows while maximizing the profit of the worst-off vehicle in the fleet. We propose a centralized and distributed vehicle routing model for this problem, both with quality of solution guarantees. The distributed approach is tailored for multiagent systems relying on a coordination mechanism where each vehicle modeled as an individually rational agent finds its route autonomously in coordination with a fleet coordinator agent, without sharing its private information. The objective of a vehicle agent is to maximize its own profit while following the fleet’s norms and regulations based on shared values. Simulation experiments provide compelling evidence of the robustness and scalability of the proposed distributed approach, showcasing significant enhancements in both solution quality and computational efficiency, particularly when dealing with larger vehicle fleets.