Decentralised Vehicle Allocation for Community-Based Ride-Sharing Services
摘要
This paper presents the design, implementation and evaluation of the vehicle fleet allocation in a community-based ride-sharing service. Independent communities of a city compete for the allocation of vehicle resources, which use to handle the transport requests of its own neighbours via ride-sharing. This vehicle allocation problem (VAP) is formulated as a decentralised, iterative negotiation process among independent communities with the underlying ride-sharing service operated by each community is formulated as a vehicle routing problem with both dynamic resources and requests. Two separate solution designs are evaluated: on the one hand, a Multi-Objective and Multi-Agent Reinforcement Learning algorithm, involving Deep Q-Learning with Graph Convolutional Networks, is applied to compute the vehicle allocation; on the other hand, a reactive-based simulation on top of a greedy decision-making process is applied to compute the underlying ride-sharing problem of each community. Existing benchmarks (e.g. Google HashCode) and public datasets (e.g. NYC taxis) are aligned to the proposed problem formulation, evaluating the solution approach under different community connectivity-levels and transport request distributions. Ride-sharing services have demonstrated scalable efficiency. This efficiency is achieved through a centralised Mixed-Integer Programming formulation, which optimally addresses the vehicle allocation problem.