{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T16:36:21Z","timestamp":1780418181463,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:p>\n            Traditionally, route recommendation systems focused on minimizing distance (or time) to travel between two points. However, recent attention has shifted to other factors beyond mere length. This paper addresses the challenge of ensuring a fair distribution of visits among network nodes when handling a high volume of point-to-point path queries. In doing so, we adopt a\n            <jats:italic toggle=\"yes\">Rawlsian<\/jats:italic>\n            notion of individual-level fairness exploiting the power of randomization. Specifically, we aim to create a probabilistic distribution over paths that maximizes the minimum probability of any eligible node being included in the recommended path.\n          <\/jats:p>\n          <jats:p>\n            A key idea of our work is the notion of\n            <jats:italic toggle=\"yes\">forward paths<\/jats:italic>\n            , i.e., paths where travelling along any edge decreases the distance to the destination. In unweighted graphs forward paths and shortest paths coincide, but in weighted graphs forward paths provide a richer set of alternative routes, involving many more nodes while remaining close in length to the shortest path. Thus, they offer diversity and a wider basis for fairness, while maintaining near-optimal path lengths. We devise an algorithm that extracts a directed acyclic graph (DAG) containing all the forward paths in the input graph, with the same computational runtime as solving a single shortest-path query. This avoids enumerating all possible forward paths, which can be exponential in the number of nodes. We then design a flow problem on this DAG to derive the probabilistic distribution over forward paths with the desired fairness property, solvable in polynomial time through a sequence of small linear programs.\n          <\/jats:p>\n          <jats:p>Our experiments on real-world datasets validate our theoretical results, demonstrating that our technique provides individual node satisfaction while maintaining near-optimal path lengths. Moreover, our experiments show that our method can handle networks with millions of nodes and edges on a commodity laptop, and scales better than the baselines when there is a large volume of path queries for the same source and destination pair.<\/jats:p>","DOI":"10.14778\/3746405.3746440","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T17:06:20Z","timestamp":1756919180000},"page":"3230-3242","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Beyond Shortest Paths: Node Fairness in Route Recommendation"],"prefix":"10.14778","volume":"18","author":[{"given":"Antonio","family":"Ferrara","sequence":"first","affiliation":[{"name":"CENTAI, Turin, Italy and TU Graz, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Garc\u00eda-Soriano","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Serra H\u00fanter Fellow, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"CENTAI, Turin, Italy and Eurecat, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2444016.2444019"},{"key":"e_1_2_1_2_1","volume-title":"On a routing problem. Quarterly of applied mathematics 16, 1","author":"Bellman Richard","year":"1958","unstructured":"Richard Bellman. 1958. On a routing problem. Quarterly of applied mathematics 16, 1 (1958), 87\u201390."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.08.023"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i10.26455"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209978.3210063"},{"key":"e_1_2_1_6_1","volume-title":"Modeling and analyzing urban networks and amenities with OSMnx. Geographical Analysis","author":"Boeing Geoff","year":"2025","unstructured":"Geoff Boeing. 2025. Modeling and analyzing urban networks and amenities with OSMnx. Geographical Analysis (2025)."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 757\u2013762","author":"Brilhante Igo","year":"2013","unstructured":"Igo Brilhante, Jose Antonio Macedo, Franco Maria Nardini, Raffaele Perego, and Chiara Renso. 2013. Where shall we go today? Planning touristic tours with TripBuilder. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 757\u2013762."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350234"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00604-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424305"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11257-023-09364-z"},{"key":"e_1_2_1_13_1","volume-title":"The shortest path problem: Ninth DIMACS implementation challenge","author":"Demetrescu Camil","unstructured":"Camil Demetrescu, Andrew V Goldberg, and David S Johnson. 2009. The shortest path problem: Ninth DIMACS implementation challenge. Vol. 74. American Mathematical Soc."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2024.3396173"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-020-00675-y"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467349"},{"key":"e_1_2_1_19_1","volume-title":"On the measure of concentration with special reference to income and statistics","author":"Gini Corrado","year":"1936","unstructured":"Corrado Gini. 1936. On the measure of concentration with special reference to income and statistics, Colorado College Publication. General series 208, 1 (1936)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1177-7"},{"key":"e_1_2_1_21_1","volume-title":"Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, Vol. 2. Springer."},{"key":"e_1_2_1_22_1","unstructured":"Gurobi Optimization LLC. 2024. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3474717.3483955"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v37i4.25511"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"36","author":"Lee Woo","year":"2022","unstructured":"Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, and Yota Otachi. 2022. Computing diverse shortest paths efficiently: A theoretical and experimental study. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 3758\u20133766."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2025.05.026"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3213586.3226206"},{"key":"e_1_2_1_28_1","volume-title":"Article 102070 (Oct.","author":"Liu Shan","year":"2020","unstructured":"Shan Liu, Hai Jiang, Shuiping Chen, Jing Ye, Renqing He, and Zhizhao Sun. 2020. Integrating Dijkstra's algorithm into deep inverse reinforcement learning for food delivery route planning. Transportation Research Part E: Logistics and Transportation Review 142, Article 102070 (Oct. 2020), 102070 pages."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/15225437.1905.10503443"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551863"},{"key":"e_1_2_1_31_1","volume-title":"Mohamed Abdur Rahman, and Saleh Basalamah.","author":"Madkour Amgad","year":"2017","unstructured":"Amgad Madkour, Walid G Aref, Faizan Ur Rehman, Mohamed Abdur Rahman, and Saleh Basalamah. 2017. A survey of shortest-path algorithms. arXiv preprint arXiv:1705.02044 (2017)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2024\/20"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2631775.2631799"},{"key":"e_1_2_1_34_1","volume-title":"A theory of justice","author":"Rawls John","unstructured":"John Rawls. 1971. A theory of justice. MA: Harvard University Press."},{"key":"e_1_2_1_35_1","volume-title":"2011 IEEE 27th International Conference on Data Engineering. IEEE, 15\u201326","author":"Roy Senjuti Basu","year":"2011","unstructured":"Senjuti Basu Roy, Gautam Das, Sihem Amer-Yahia, and Cong Yu. 2011. Interactive itinerary planning. In 2011 IEEE 27th International Conference on Data Engineering. IEEE, 15\u201326."},{"key":"e_1_2_1_36_1","volume-title":"Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems. arXiv preprint arXiv:2410.02589","author":"Salem Jad","year":"2024","unstructured":"Jad Salem, Reuben Tate, and Stephan Eidenbenz. 2024. Expected Maximin Fairness in Max-Cut and other Combinatorial Optimization Problems. arXiv preprint arXiv:2410.02589 (2024)."},{"key":"e_1_2_1_37_1","volume-title":"Sudipta Roy, and Bibudhendu Pati.","author":"Sarkar Joy Lal","year":"2023","unstructured":"Joy Lal Sarkar, Abhishek Majumder, Chhabi Rani Panigrahi, Sudipta Roy, and Bibudhendu Pati. 2023. Tourism recommendation system: A survey and future research directions. Multimedia tools and applications 82, 6 (2023), 8983\u20139027."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220088"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3011924"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139774"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547333"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389248"},{"key":"e_1_2_1_44_1","volume-title":"An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of applied mathematics 27, 4","author":"Yen Jin Y","year":"1970","unstructured":"Jin Y Yen. 1970. An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of applied mathematics 27, 4 (1970), 526\u2013530."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.inffus.2024.102413"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3746405.3746440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T19:49:54Z","timestamp":1757015394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3746405.3746440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5]]},"references-count":45,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.14778\/3746405.3746440"],"URL":"https:\/\/doi.org\/10.14778\/3746405.3746440","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,5]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}