{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T22:54:17Z","timestamp":1743116057633,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031826962"},{"type":"electronic","value":"9783031826979"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82697-9_7","type":"book-chapter","created":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:26Z","timestamp":1739614646000},"page":"85-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of\u00a0Counting Turns in\u00a0the\u00a0Line-Based Dial-a-Ride Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9093-3443","authenticated-orcid":false,"given":"Antonio","family":"Lauerbach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7281-6516","authenticated-orcid":false,"given":"Kendra","family":"Reiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9563-9955","authenticated-orcid":false,"given":"Marie","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,16]]},"reference":[{"issue":"5","key":"7_CR1","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1016\/j.trc.2009.12.006","volume":"19","author":"C Archetti","year":"2011","unstructured":"Archetti, C., Feillet, D., Gendreau, M., Grazia Speranza, M.: Complexity of the VRP and SDVRP. Trans. Res. Part C: Emerg. Technol. 19(5), 741\u2013750 (2011). https:\/\/doi.org\/10.1016\/j.trc.2009.12.006","journal-title":"Trans. Res. Part C: Emerg. Technol."},{"key":"7_CR2","doi-asserted-by":"publisher","unstructured":"Bjelde, A., et al.: Tight bounds for online TSP on the line. ACM Trans. Algorithms 17(1), 3:1\u20133:58 (2021). https:\/\/doi.org\/10.1145\/3422362","DOI":"10.1145\/3422362"},{"key":"7_CR3","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman (1979)"},{"issue":"3","key":"7_CR4","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1016\/J.EJOR.2021.11.053","volume":"301","author":"D Gaul","year":"2022","unstructured":"Gaul, D., Klamroth, K., Stiglmayr, M.: Event-based MILP models for ridepooling applications. Eur. J. Oper. Res. 301(3), 1048\u20131063 (2022). https:\/\/doi.org\/10.1016\/J.EJOR.2021.11.053","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"7_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0020-0190(02)00474-X","volume":"86","author":"DR Gaur","year":"2003","unstructured":"Gaur, D.R., Gupta, A., Krishnamurti, R.: A 53-approximation algorithm for scheduling vehicles on a path with release and handling times. Inf. Process. Lett. 86(2), 87\u201391 (2003). https:\/\/doi.org\/10.1016\/S0020-0190(02)00474-X","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0166-218X(97)00074-7","volume":"81","author":"DJ Guan","year":"1998","unstructured":"Guan, D.J.: Routing a vehicle of capacity greater than one. Discret. Appl. Math. 81(1), 41\u201357 (1998). https:\/\/doi.org\/10.1016\/S0166-218X(97)00074-7","journal-title":"Discret. Appl. Math."},{"key":"7_CR7","doi-asserted-by":"publisher","unstructured":"Haugland, D., Ho, S.C.: Feasibility testing for dial-a-ride problems. In: Chen, B. (ed.) Algorithmic Aspects in Information and Management, pp. 170\u2013179. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14355-7_18","DOI":"10.1007\/978-3-642-14355-7_18"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.trb.2018.02.001","volume":"111","author":"SC Ho","year":"2018","unstructured":"Ho, S.C., Szeto, W., Kuo, Y.H., Leung, J.M., Petering, M., Tou, T.W.: A survey of dial-a-ride problems: literature review and recent developments. Trans. Res. Part B: Methodological 111, 395\u2013421 (2018). https:\/\/doi.org\/10.1016\/j.trb.2018.02.001","journal-title":"Trans. Res. Part B: Methodological"},{"key":"7_CR9","doi-asserted-by":"publisher","unstructured":"Hougardy, S.: Classes of perfect graphs. Discrete Math. 306(19), 2529\u20132571 (2006). https:\/\/doi.org\/10.1016\/j.disc.2006.05.021. creation and Recreation: A Tribute to the Memory of Claude Berge","DOI":"10.1016\/j.disc.2006.05.021"},{"issue":"26\u201328","key":"7_CR10","doi-asserted-by":"publisher","first-page":"2467","DOI":"10.1016\/J.TCS.2010.02.016","volume":"411","author":"Q Hua","year":"2010","unstructured":"Hua, Q., Wang, Y., Yu, D., Lau, F.C.M.: Dynamic programming based algorithms for set multicover and multiset multicover problems. Theor. Comput. Sci. 411(26\u201328), 2467\u20132474 (2010). https:\/\/doi.org\/10.1016\/J.TCS.2010.02.016","journal-title":"Theor. Comput. Sci."},{"key":"7_CR11","doi-asserted-by":"publisher","unstructured":"Karuno, Y., Nagamochi, H.: A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times. In: auf\u00a0der Heide, F.M. (ed.) Algorithms \u2014 ESA 2001, pp. 218\u2013229. Springer Berlin Heidelberg, Berlin, Heidelberg (2001). https:\/\/doi.org\/10.1016\/S0166-218X(02)00596-6","DOI":"10.1016\/S0166-218X(02)00596-6"},{"issue":"4","key":"7_CR12","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1002\/net.10028","volume":"39","author":"Y Karuno","year":"2002","unstructured":"Karuno, Y., Nagamochi, H., Ibaraki, T.: Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks 39(4), 203\u2013209 (2002). https:\/\/doi.org\/10.1002\/net.10028","journal-title":"Networks"},{"key":"7_CR13","unstructured":"Lauerbach, A., Reiter, K., Schmidt, M.: The complexity of counting turns in the line-based dial-a-ride problem (2024). https:\/\/arxiv.org\/abs\/2409.15192"},{"issue":"2","key":"7_CR14","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1287\/IJOC.1030.0052","volume":"16","author":"W de Paepe","year":"2004","unstructured":"de Paepe, W., Lenstra, J.K., Sgall, J., Sitters, R.A., Stougie, L.: Computer-aided complexity classification of dial-a-ride problems. INFORMS J. Comput. 16(2), 120\u2013132 (2004). https:\/\/doi.org\/10.1287\/IJOC.1030.0052","journal-title":"INFORMS J. Comput."},{"key":"7_CR15","doi-asserted-by":"publisher","unstructured":"Reiter, K., Schmidt, M., Stiglmayr, M.: The line-based dial-a-ride problem. In: Bouman, P.C., Kontogiannis, S.C. (eds.) 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024), pp. 14:1 \u2013 14:20. Open Access Series in Informatics (OASIcs), Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/OASIcs.ATMOS.2024.14","DOI":"10.4230\/OASIcs.ATMOS.2024.14"},{"issue":"3","key":"7_CR16","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/net.3230220305","volume":"22","author":"JN Tsitsiklis","year":"1992","unstructured":"Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks 22(3), 263\u2013282 (1992). https:\/\/doi.org\/10.1002\/net.3230220305","journal-title":"Networks"},{"key":"7_CR17","doi-asserted-by":"publisher","unstructured":"Vansteenwegen, P., Melis, L., Akta\u015f, D., Montenegro, B.D.G., Sartori\u00a0Vieira, F., S\u00f6rensen, K.: A survey on demand-responsive public bus systems. Trans. Res. Part C: Emerg. Technol. 137, 103573 (2022). https:\/\/doi.org\/10.1016\/j.trc.2022.103573","DOI":"10.1016\/j.trc.2022.103573"},{"issue":"2","key":"7_CR18","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1002\/net.20393","volume":"57","author":"W Yu","year":"2011","unstructured":"Yu, W., Liu, Z.: Single-vehicle scheduling problems with release and service times on a line. Networks 57(2), 128\u2013134 (2011). https:\/\/doi.org\/10.1002\/net.20393","journal-title":"Networks"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82697-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T10:17:33Z","timestamp":1739614653000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82697-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826962","9783031826979"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82697-9_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"16 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}