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

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

5 Citationer (Scopus)

Abstrakt

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.

OriginalsprogEngelsk
Titel2020 IEEE 36th International Conference on Data Engineering
Antal sider12
ForlagIEEE
Publikationsdato2020
Sider973-984
Artikelnummer9101586
ISBN (Trykt)978-1-7281-2903-7
DOI
StatusUdgivet - 2020
BegivenhedInternational Conference on Data Engineering - Dallas, USA
Varighed: 20 apr. 202024 apr. 2020
Konferencens nummer: 36th

Konference

KonferenceInternational Conference on Data Engineering
Nummer36th
LandUSA
ByDallas
Periode20/04/202024/04/2020
NavnProceedings of the International Conference on Data Engineering
ISSN1063-6382

Fingeraftryk

Dyk ned i forskningsemnerne om 'Online Trichromatic Pickup and Delivery Scheduling in Spatial Crowdsourcing'. Sammen danner de et unikt fingeraftryk.

Citationsformater