Efficient technique for online crowdshipping based package delivery with daily commuters

Abstract

Theadvancementoflocation-awaretechnologiesenablesgeneratinganunprecedented amount of trajectories representing the daily commuting patterns ofdwellers in a city. A wide variety of location-based services have started capitalizingon these spatio-temporal footprints of users in enhancing existing services anddeveloping new services. In this thesis, we propose a new location-based service,namelycrowdshipping, that enables a service delivery company to exploit users’dailycommutingpatternstodeliverapacketfromoneplacetoanotherusingcrowd.In particular, our proposed service engages users in shipping goods near their regularitinerary (with a small detour) while minimizing the total cost of the delivery. Wetake into account the commuters’ choice of transport and the involvement of multiplecommuters in delivering a package.A major challenge in solving such a query isto select a set of candidate trajectories (i.e., users) from a large trajectory databasethatcandeliverapacketwithminimumcost.Toaddressthischallenge,weproposea solution based on two indexes.We first build a summary index to capture theoverall commuting patterns of the users in the space. This index sets up a regionalconnectivity network with the trajectories passing through them, which helps us toidentify the initial search space for a package to be delivered. We then use a secondindexbygroupingthetrajectoriesbasedontheirspatio-temporalco-visitingpatterns.It helps prune the trajectories in temporal domain while searching for an answer.Besides,ithelpsgroupthetrajectorieswithspatialandtemporallocalitytogetherinthe physical disk pages. To evaluate our proposed approach we compare it with abaseline based on a traditional spatial index (quadtree) on large real-world trajectorydatasets. ExperimentsshowthatourefficientindexperformsanorderofmagnitudebetterthanthebaselineontherealdatabothintermsofruntimeandI/Ocost.