{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:41Z","timestamp":1750220921652,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,30]],"date-time":"2019-06-30T00:00:00Z","timestamp":1561852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["FT180100140 and DP180103411"],"award-info":[{"award-number":["FT180100140 and DP180103411"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>In this article, we introduce generalized group trip scheduling (GGTS) queries that enable friends and families to perform activities at different points of interest (POIs), such as a shopping center, a restaurant and a pharmacy with the minimum total travel distance. Trip planning and scheduling for groups, an important class of location-based services (LBSs), have recently received attention from researchers. However, both group trip planning (GTP) and group trip scheduling (GTS) queries have restrictions: a GTP query assumes that all group members visit all required POIs together, whereas a GTS query requires that each POI is visited by a single group member. A GGTS query is more general and allows any number of group members to visit a POI together. We propose an efficient algorithm to evaluate the exact answers for GGTS queries in road networks. Since finding the answer for a GGTS query is an NP-hard problem, to reduce the processing overhead for a large group size or a large number of required POI types or a large POI dataset, we propose two heuristic solutions\u2014trip-scheduling heuristic (TSH) and search region refinement heuristic (SRH)\u2014for processing GGTS queries. Extensive experiments with real datasets show that our optimal algorithm is preferable for small parameter settings, and the heuristic solutions reduce the processing overhead significantly in return for sacrificing the accuracy slightly.<\/jats:p>","DOI":"10.1145\/3325915","type":"journal-article","created":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T12:34:33Z","timestamp":1564058073000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Scheduling of Generalized Group Trips in Road Networks"],"prefix":"10.1145","volume":"5","author":[{"given":"Yeasir","family":"Rayhan","sequence":"first","affiliation":[{"name":"Bangladesh University of Engineering and Technology, Dhaka, Bangladesh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1288-5785","authenticated-orcid":false,"given":"Tanzima","family":"Hashem","sequence":"additional","affiliation":[{"name":"Bangladesh University of Engineering and Technology, Dhaka, Bangladesh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roksana","family":"Jahan","sequence":"additional","affiliation":[{"name":"Bangladesh University of Engineering and Technology, Dhaka, Bangladesh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Muhammad Aamir","family":"Cheema","sequence":"additional","affiliation":[{"name":"Monash University, Clayton, VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00289-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2015.49"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996994"},{"volume-title":"Optimal meeting points for public transit users. In Proceedings of the MDM. 15--23","author":"Ahmadi Elham","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0477-7"},{"volume-title":"Proceedings of the EDBT. 522--525","year":"2017","author":"Anwar Anika","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3091478.3091485"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.05.004"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505643"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463434.1463448"},{"key":"e_1_2_1_11_1","unstructured":"Dataset. 2005. California road network data. Retrieved from: https:\/\/www.cs.utah.edu\/ lifeifei\/SpatialDataset.htm.  Dataset. 2005. California road network data. Retrieved from: https:\/\/www.cs.utah.edu\/ lifeifei\/SpatialDataset.htm."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64367-0_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-018-0331-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2559893"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806433"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40235-7_15"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1771592.1771614"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739100"},{"volume-title":"Proceedings of the EDBT. OpenProceedings.org, 390--401","year":"2017","author":"Jahan Roksana","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2009.76"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_16"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1097064.1097092"},{"key":"e_1_2_1_23_1","unstructured":"R-tree. {n.d.}. Retrieved from: http:\/\/rtreeportal.org.  R-tree. {n.d.}. Retrieved from: http:\/\/rtreeportal.org."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544888"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2015.68"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0038-6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-016-0384-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085584"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325915","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3325915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:08Z","timestamp":1750204388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,30]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3325915"],"URL":"https:\/\/doi.org\/10.1145\/3325915","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2019,6,30]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}