Algorithms for Trip-Vehicle Assignment in Ride-Sharing

AAAI 2018 pp. 3-9

doi:10.1609/AAAI.V32I1.11298 /aaai/2018/bei2018aaai-algorithms/

Abstract

We investigate the ride-sharing assignment problem from an algorithmic resource allocation point of view. Given a number of requests with source and destination locations, and a number of available car locations, the task is to assign cars to requests with two requests sharing one car. We formulate this as a combinatorial optimization problem, and show that it is NP-hard. We then design an approximation algorithm which guarantees to output a solution with at most 2.5 times the optimal cost. Experiments are conducted showing that our algorithm actually has a much better approximation ratio (around 1.2) on synthetically generated data.

PDF AAAI Semantic Scholar

Cite

Text

Bei and Zhang. "Algorithms for Trip-Vehicle Assignment in Ride-Sharing." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11298

Markdown

[Bei and Zhang. "Algorithms for Trip-Vehicle Assignment in Ride-Sharing." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/bei2018aaai-algorithms/) doi:10.1609/AAAI.V32I1.11298

BibTeX

@inproceedings{bei2018aaai-algorithms,
  title     = {{Algorithms for Trip-Vehicle Assignment in Ride-Sharing}},
  author    = {Bei, Xiaohui and Zhang, Shengyu},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {3-9},
  doi       = {10.1609/AAAI.V32I1.11298},
  url       = {https://mlanthology.org/aaai/2018/bei2018aaai-algorithms/}
}