{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T18:13:18Z","timestamp":1743012798788,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031496134"},{"type":"electronic","value":"9783031496141"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-49614-1_6","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T14:02:45Z","timestamp":1702044165000},"page":"97-110","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Earliest Deadline First Is a\u00a02-Approximation for\u00a0DARP with\u00a0Time Windows"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2493-1251","authenticated-orcid":false,"given":"Barbara M.","family":"Anthony","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3580-9275","authenticated-orcid":false,"given":"Christine","family":"Chung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9445-1475","authenticated-orcid":false,"given":"Ananya","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9827-0962","authenticated-orcid":false,"given":"David","family":"Yuen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"key":"6_CR1","unstructured":"Anthony, B.M., et al.: Maximizing the number of rides served for dial-a-ride. In: 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, vol. 75, pp. 11:1\u201311:15 (2019)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Anthony, B.M., Christman, A.D., Chung, C., Yuen, D.: Serving rides of equal importance for time-limited dial-a-ride. In: Mathematical Optimization Theory and Operations Research, pp. 35\u201350 (2021)","DOI":"10.1007\/978-3-030-77876-7_3"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Anthony, B.M., Chung, C., Das, A., Yuen, D.: Earliest deadline first is a 2-approximation for DARP with time windows (2023). http:\/\/cs.conncoll.edu\/cchung\/research\/publications\/cocoa2023full.pdf","DOI":"10.1007\/978-3-031-49614-1_6"},{"key":"6_CR4","doi-asserted-by":"publisher","unstructured":"Balig\u00e1cs, J., Disser, Y., Mosis, N., Weckbecker, D.: An improved algorithm for open online dial-a-ride. In: Chalermsook, P., Laekhanukit, B. (eds.) Approximation and Online Algorithms. WAOA 2022. Lecture Notes in Computer Science, vol. 13538, pp. 154\u2013171. Springer International Publishing, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-18367-6_8","DOI":"10.1007\/978-3-031-18367-6_8"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. In: 36th Annual ACM Symposium on Theory of Computing, pp. 166\u2013174 (2004)","DOI":"10.1145\/1007352.1007385"},{"issue":"2","key":"6_CR6","doi-asserted-by":"publisher","first-page":"1409","DOI":"10.1137\/19M1268513","volume":"34","author":"A Birx","year":"2020","unstructured":"Birx, A., Disser, Y.: Tight analysis of the Smartstart algorithm for online dial-a-ride on the line. SIAM J. Discret. Math. 34(2), 1409\u20131443 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"5","key":"6_CR7","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1007\/s00453-022-01061-4","volume":"85","author":"A Birx","year":"2023","unstructured":"Birx, A., Disser, Y., Schewior, K.: Improved bounds for open online dial-a-ride on the line. Algorithmica 85(5), 1372\u20131414 (2023)","journal-title":"Algorithmica"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Charikar, M., Raghavachari, B.: The finite capacity dial-a-ride problem. In: 39th Annual Symposium on Foundations of Computer Science, pp. 458\u2013467 (1998)","DOI":"10.1109\/SFCS.1998.743496"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Chen, S., He, T., Wong, H.Y.S., Lee, K.W., Tong, L.: Secondary job scheduling in the cloud with deadlines. In: IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, pp. 1009\u20131016 (2011)","DOI":"10.1109\/IPDPS.2011.246"},{"issue":"10","key":"6_CR10","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.1109\/TSE.1989.559777","volume":"15","author":"H Chetto","year":"1989","unstructured":"Chetto, H., Chetto, M.: Some results of the earliest deadline scheduling algorithm. IEEE Trans. Software Eng. 15(10), 1261\u20131269 (1989)","journal-title":"IEEE Trans. Software Eng."},{"key":"6_CR11","unstructured":"Christman, A., Chung, C., Jaczko, N., Milan, M., Vasilchenko, A., Westvold, S.: Revenue maximization in online dial-a-ride. In: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, vol. 59, pp. 1:1\u20131:15. Dagstuhl, Germany (2017)"},{"issue":"3","key":"6_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s43069-021-00076-x","volume":"2","author":"AD Christman","year":"2021","unstructured":"Christman, A.D., et al.: Improved bounds for revenue maximization in time-limited online dial-a-ride. Oper. Res. Forum 2(3), 1\u201338 (2021). https:\/\/doi.org\/10.1007\/s43069-021-00076-x","journal-title":"Oper. Res. Forum"},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s10479-007-0170-8","volume":"153","author":"JF Cordeau","year":"2007","unstructured":"Cordeau, J.F., Laporte, G.: The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153(1), 29\u201346 (2007)","journal-title":"Ann. Oper. Res."},{"key":"6_CR14","unstructured":"Dertouzos, M.L.: Control robotics: the procedural control of physical processes. In: Proceedings IFIP Congress, 1974 (1974)"},{"issue":"12","key":"6_CR15","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/32.58762","volume":"15","author":"ML Dertouzos","year":"1989","unstructured":"Dertouzos, M.L., Mok, A.K.: Multiprocessor online scheduling of hard-real-time tasks. IEEE Trans. Software Eng. 15(12), 1497\u20131506 (1989)","journal-title":"IEEE Trans. Software Eng."},{"issue":"3\u20134","key":"6_CR16","first-page":"301","volume":"6","author":"J Desrosiers","year":"1986","unstructured":"Desrosiers, J., Dumas, Y., Soumis, F.: A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows. Am. J. Math. Manag. Sci. 6(3\u20134), 301\u2013325 (1986)","journal-title":"Am. J. Math. Manag. Sci."},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: 17th Annual Symposium on Foundations of Computer Science, pp. 216\u2013227 (1976)","DOI":"10.1109\/SFCS.1976.6"},{"key":"6_CR18","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. Transp. Res. Part B: Methodol. 111, 395\u2013421 (2018)","journal-title":"Transp. Res. Part B: Methodol."},{"issue":"3","key":"6_CR19","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0191-2615(86)90020-2","volume":"20","author":"JJ Jaw","year":"1986","unstructured":"Jaw, J.J., Odoni, A.R., Psaraftis, H.N., Wilson, N.H.: A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transp. Res. Part B: Methodol. 20(3), 243\u2013257 (1986)","journal-title":"Transp. Res. Part B: Methodol."},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Leung, J.Y.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press (2004)","DOI":"10.1201\/9780203489802"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02031946","volume":"60","author":"OB Madsen","year":"1995","unstructured":"Madsen, O.B., Ravn, H.F., Rygaard, J.M.: A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Ann. Oper. Res. 60, 193\u2013208 (1995)","journal-title":"Ann. Oper. Res."},{"key":"6_CR22","unstructured":"Medina, A., Anthony, B.M.: Evaluating an earliest deadline first algorithm for a dial-a-ride problem [poster]. Tapia Celebration of Diversity in Computing (2023)"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10479-017-2525-0","volume":"3","author":"Y Molenbruch","year":"2017","unstructured":"Molenbruch, Y., Braekers, K., Caris, A.: Typology and literature review for dial-a-ride problems. Ann. Oper. Res. 3, 295\u2013325 (2017). https:\/\/doi.org\/10.1007\/s10479-017-2525-0","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"6_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/trsc.22.1.1","volume":"22","author":"MM Solomon","year":"1988","unstructured":"Solomon, M.M., Desrosiers, J.: Survey paper-time window constrained routing and scheduling problems. Transp. Sci. 22(1), 1\u201313 (1988)","journal-title":"Transp. Sci."},{"key":"6_CR25","doi-asserted-by":"publisher","unstructured":"Stankovic, J.A., Spuri, M., Ramamritham, K., Buttazzo, G.C.: Fundamentals of EDF Scheduling. In: Deadline Scheduling for Real-Time Systems. The Springer International Series in Engineering and Computer Science, vol. 460, pp. 27\u201365. Springer, US, Boston, MA (1998). https:\/\/doi.org\/10.1007\/978-1-4615-5535-3_3","DOI":"10.1007\/978-1-4615-5535-3_3"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Yi, F., Song, Y., Xin, C., Walter, I., Kai, K.W.: Online dial-a-ride problem with unequal-length time-windows. In: 2009 International Conference on Management and Service Science, pp. 1\u20135 (2009)","DOI":"10.1109\/ICMSS.2009.5303885"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/11496199_11","volume-title":"Algorithmic Applications in Management","author":"F Yi","year":"2005","unstructured":"Yi, F., Tian, L.: On the online dial-a-ride problem with time-windows. In: Megiddo, N., Xu, Y., Zhu, B. (eds.) AAIM 2005. LNCS, vol. 3521, pp. 85\u201394. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11496199_11"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Yi, F., Xu, Y., Xin, C.: Online dial-a-ride problem with time-windows under a restricted information model. In: Algorithmic Aspects in Information and Management, pp. 22\u201331 (2006)","DOI":"10.1007\/11775096_4"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49614-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T16:50:36Z","timestamp":1730825436000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49614-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031496134","9783031496141"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49614-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawai, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOA2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"117","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"62% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}