TY - GEN
T1 - Drive less but finish more
T2 - 31st ACM International Conference on Information and Knowledge Management, CIKM 2022
AU - Xu, Xiaojia
AU - Liu, An
AU - Liu, Guanfeng
AU - Li, Zhixu
AU - Zhao, Lei
PY - 2022/10
Y1 - 2022/10
N2 - 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.
AB - 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.
KW - online food delivery
KW - spatial crowdsourcing
KW - task assignment
UR - http://www.scopus.com/inward/record.url?scp=85140849585&partnerID=8YFLogxK
U2 - 10.1145/3511808.3557297
DO - 10.1145/3511808.3557297
M3 - Conference proceeding contribution
AN - SCOPUS:85140849585
T3 - International Conference on Information and Knowledge Management, Proceedings
SP - 2331
EP - 2340
BT - CIKM 2022 - Proceedings of the 31st ACM International Conference on Information and Knowledge Management
PB - Association for Computing Machinery (ACM)
CY - New York, NY
Y2 - 17 October 2022 through 21 October 2022
ER -