Online Trichromatic Pickup and Delivery Scheduling in Spatial Crowdsourcing

Bolong Zheng, Chenze Huang, Christian S. Jensen, Lu Chen, Nguyen Quoc Viet Hung, Guanfeng Liu, Guohui Li, Kai Zheng

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

2 Citations (Scopus)

Abstract

In Pickup-and-Delivery problems (PDP), mobile workers are employed to pick up and deliver items with the goal of reducing travel and fuel consumption. Unlike most existing efforts that focus on finding a schedule that enables the delivery of as many items as possible at the lowest cost, we consider trichromatic (worker-item-task) utility that encompasses worker reliability, item quality, and task profitability. Moreover, we allow customers to specify keywords for desired items when they submit tasks, which may result in multiple pickup options, thus further increasing the difficulty of the problem. Specifically, we formulate the problem of Online Trichromatic Pickup and Delivery Scheduling (OTPD) that aims to find optimal delivery schedules with highest overall utility. In order to quickly respond to submitted tasks, we propose a greedy solution that finds the schedule with the highest utility-cost ratio. Next, we introduce a skyline kinetic tree-based solution that materializes intermediate results to improve the result quality. Finally, we propose a density-based grouping solution that partitions streaming tasks and efficiently assigns them to the workers with high overall utility. Extensive experiments with real and synthetic data offer evidence that the proposed solutions excel over baselines with respect to both effectiveness and efficiency.

Original languageEnglish
Title of host publication2020 IEEE 36th International Conference on Data Engineering
Number of pages12
PublisherIEEE
Publication date2020
Pages973-984
Article number9101586
ISBN (Print)978-1-7281-2903-7
DOIs
Publication statusPublished - 2020
EventInternational Conference on Data Engineering - Dallas, United States
Duration: 20 Apr 202024 Apr 2020
Conference number: 36th

Conference

ConferenceInternational Conference on Data Engineering
Number36th
CountryUnited States
CityDallas
Period20/04/202024/04/2020
SeriesProceedings of the International Conference on Data Engineering
ISSN1063-6382

Keywords

  • Pickup and delivery
  • Query optimization
  • Real-time
  • Scheduling
  • Spatial Crowdsourcing

Fingerprint Dive into the research topics of 'Online Trichromatic Pickup and Delivery Scheduling in Spatial Crowdsourcing'. Together they form a unique fingerprint.

Cite this