Drive less but finish more: food delivery based on multi-level workers in spatial crowdsourcing

Xiaojia Xu, An Liu*, Guanfeng Liu, Zhixu Li, Lei Zhao

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

2 Citations (Scopus)

Abstract

In this paper, we study the problem of on-demand food delivery in a new setting where two groups of workers - riders and taxi drivers (drivers for short) - cooperate with each other for better service. The riders are responsible for the first and the last mile, and the drivers are in charge of the cross-community transportation. We show this problem is generally NP-hard by a reduction from the well-known 3-dimensional matching (3DM). To tackle with this problem, we first reduce it to the maximum independent set problem and use a simple greedy strategy to design an approximate algorithm which has a polynomial time. Considering the exponents in the polynomial are not very small, we then transform the 3DM into two rounds of 2-dimensional matching and propose a fast algorithm to solve it. Though 3DM problem is NP-hard, we find the cooperation between riders and drivers form a special tripartite graph, based on which we construct a flow network and employ the min-cost max-flow algorithm to efficiently compute the exact solution. We conduct extensive experiments to show the efficiency and the effectiveness of our proposed algorithms.

Original languageEnglish
Title of host publicationCIKM 2022 - Proceedings of the 31st ACM International Conference on Information and Knowledge Management
Place of PublicationNew York, NY
PublisherAssociation for Computing Machinery (ACM)
Pages2331-2340
Number of pages10
ISBN (Electronic)9781450392365
DOIs
Publication statusPublished - Oct 2022
Event31st ACM International Conference on Information and Knowledge Management, CIKM 2022 - Atlanta, United States
Duration: 17 Oct 202221 Oct 2022

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Conference

Conference31st ACM International Conference on Information and Knowledge Management, CIKM 2022
Country/TerritoryUnited States
CityAtlanta
Period17/10/2221/10/22

Keywords

  • online food delivery
  • spatial crowdsourcing
  • task assignment

Fingerprint

Dive into the research topics of 'Drive less but finish more: food delivery based on multi-level workers in spatial crowdsourcing'. Together they form a unique fingerprint.

Cite this