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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Decentralised Vehicle Allocation for Community-Based Ride-Sharing Services

  • Avinash Nagarajan,
  • Alan McGibney,
  • Pio Fenton,
  • Ignacio Castiñeiras

摘要

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.