Abstract
In this paper, we study the problem of Utility Driven Job Selection on Road Networks for which the inputs are: a road network with the vertices as the set of Point-Of-Interests (Henceforth mentioned as POI) and the edges are road segments joining the POIs, a set of jobs with their originating POI, starting time, duration, and the utility. A worker can earn the utility associated with the job if (s)he performs this. As the jobs are originating at different POIs, the worker has to move from one POI to the other one to take up the job. Some budget is available for this purpose. Any two jobs can be taken up by the worker only if the finishing time of the first job plus traveling time from the POI of the first job to the second one should be less than or equal to the starting time of the second job. We call this constraint as the temporal constraint. The goal of this problem is to choose a subset of the jobs to maximize the earned utility such that the budget and temporal constraints should not be violated. We present two solution approaches with detailed analysis. First one of them works based on finding the locally optimal job at the end of every job and we call this approach as the Best First Search Approach. The other approach is based on the Nearest Neighbor Search on road networks. We perform a set of experiments with real-world trajectory datasets to demonstrate the efficiency and effectiveness of the proposed solution approaches. We observe that the proposed approaches lead to more utility compared to baseline methods.
The work of Suman Banerjee is supported by the Seed Grant (SGT-100047) provided by the Indian Institute of Technology Jammu, India. Both the authors have contributed equally in this work.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Brakatsoulas, S., Pfoser, D., Theodoridis, Y.: Revisiting R-tree construction principles. In: Manolopoulos, Y., Návrat, P. (eds.) ADBIS 2002. LNCS, vol. 2435, pp. 149–162. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45710-0_13
Dai, H., Tao, J., Jiang, H., Chen, W.: O2o on-demand delivery optimization with mixed driver forces. IFAC-PapersOnLine 52(13), 391–396 (2019)
Dai, J., Yang, B., Guo, C., Ding, Z.: Personalized route recommendation using big trajectory data. In: 2015 IEEE 31st International Conference on Data Engineering, pp. 543–554. IEEE (2015)
Diestel, R.: Graph Theory, 3rd ed. Grad. Texts Math. 173, 33 (2005)
Hashem, T., Hashem, T., Ali, M.E., Kulik, L.: Group trip planning queries in spatial databases. In: Nascimento, M.A., et al. (eds.) SSTD 2013. LNCS, vol. 8098, pp. 259–276. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40235-7_15
Ji, S., Zheng, Y., Wang, Z., Li, T.: Alleviating users’ pain of waiting: effective task grouping for online-to-offline food delivery services. In: The World Wide Web Conference, pp. 773–783 (2019)
Jiang, Y., Li, X.: Travel time prediction based on historical trajectory data. Ann. GIS 19(1), 27–35 (2013)
Liao, L., et al.: Hierarchical quantitative analysis to evaluate unsafe driving behaviour from massive trajectory data. IET Intel. Transp. Syst. 14(8), 849–856 (2020)
Luo, W., Tan, H., Chen, L., Ni, L.M.: Finding time period-based most frequent path in big trajectory data. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 713–724 (2013)
Palanisamy, B., Ravichandran, S., Liu, L., Han, B., Lee, K., Pu, C.: Road network mix-zones for anonymous location based services. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 1300–1303. IEEE (2013)
Qu, B., Yang, W., Cui, G., Wang, X.: Profitable taxi travel route recommendation based on big taxi trajectory data. IEEE Trans. Intell. Transp. Syst. 21(2), 653–668 (2019)
Reyes, D., Erera, A., Savelsbergh, M., Sahasrabudhe, S., O’Neil, R.: The meal delivery routing problem. Optim. Online, 6571 (2018)
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). https://networkrepository.com
Wang, S., Bao, Z., Culpepper, J.S., Cong, G.: A survey on trajectory data management, analytics, and learning. ACM Comput. Surv. (CSUR) 54(2), 1–36 (2021)
Yildiz, B., Savelsbergh, M.: Provably high-quality solutions for the meal delivery routing problem. Transp. Sci. 53(5), 1372–1388 (2019)
Ying, J.J.C., Lu, E.H.C., Kuo, W.N., Tseng, V.S.: Urban point-of-interest recommendation by mining user check-in behaviors. In: Proceedings of the ACM SIGKDD International Workshop on Urban Computing, pp. 63–70 (2012)
Zeng, Y., Tong, Y., Chen, L.: Last-mile delivery made practical: an efficient route planning framework with theoretical guarantees. Proc. VLDB Endowment 13(3), 320–333 (2019)
Zheng, Y.: Trajectory data mining: an overview. ACM Trans. Intell. Syst. Technol. (TIST) 6(3), 1–41 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Singhal, M., Banerjee, S. (2022). Utility Driven Job Selection Problem on Road Networks. In: Szczerbicki, E., Wojtkiewicz, K., Nguyen, S.V., Pietranik, M., Krótkiewicz, M. (eds) Recent Challenges in Intelligent Information and Database Systems. ACIIDS 2022. Communications in Computer and Information Science, vol 1716. Springer, Singapore. https://doi.org/10.1007/978-981-19-8234-7_45
Download citation
DOI: https://doi.org/10.1007/978-981-19-8234-7_45
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-8233-0
Online ISBN: 978-981-19-8234-7
eBook Packages: Computer ScienceComputer Science (R0)