{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:07:59Z","timestamp":1750219679444,"version":"3.41.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T00:00:00Z","timestamp":1716595200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T00:00:00Z","timestamp":1716595200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"ANR","award":["ANR-19-CE48-0016"],"award-info":[{"award-number":["ANR-19-CE48-0016"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10107-024-02094-z","type":"journal-article","created":{"date-parts":[[2024,5,25]],"date-time":"2024-05-25T06:02:04Z","timestamp":1716616924000},"page":"115-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A tight $$(1.5+\\epsilon )$$-approximation for unsplittable capacitated vehicle routing on trees"],"prefix":"10.1007","volume":"212","author":[{"given":"Claire","family":"Mathieu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1059-4909","authenticated-orcid":false,"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,25]]},"reference":[{"key":"2094_CR1","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.asoc.2015.01.013","volume":"29","author":"Muhammad Al-Salamah","year":"2015","unstructured":"Al-Salamah, Muhammad: Constrained binary artificial bee colony to minimize the makespan for single machine batch processing with non-identical job sizes. Appl. Soft Comput. 29, 379\u2013385 (2015)","journal-title":"Appl. Soft Comput."},{"issue":"4","key":"2094_CR2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0167-6377(87)90012-5","volume":"6","author":"Kemal Altinkemer","year":"1987","unstructured":"Altinkemer, Kemal, Gavish, Bezalel: Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4), 149\u2013158 (1987)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"2094_CR3","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1023\/A:1011461300596","volume":"5","author":"Tetsuo Asano","year":"2001","unstructured":"Asano, Tetsuo, Katoh, Naoki, Kawashima, Kazuhiro: A new approximation algorithm for the capacitated vehicle routing problem on a tree. J. Comb. Optim. 5(2), 213\u2013231 (2001)","journal-title":"J. Comb. Optim."},{"key":"2094_CR4","unstructured":"Becker, Amariah: A tight 4\/3 approximation for capacitated vehicle routing in trees. In: International Conference on Approximation Algorithms for Combinatorial Optimization Problems, 116, pp. 31\u20133:15, (2018)"},{"key":"2094_CR5","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-030-24766-9_9","volume-title":"Workshop on Algorithms and Data Structures","author":"A Becker","year":"2019","unstructured":"Becker, A., Paul, A.: A framework for vehicle routing approximation schemes in trees. In: Workshop on Algorithms and Data Structures, pp. 112\u2013125. Springer, Newyork (2019)"},{"key":"2094_CR6","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-022-01841-4","volume":"197","author":"Jannis Blauth","year":"2023","unstructured":"Blauth, Jannis, Traub, Vera, Vygen, Jens: Improving the approximation ratio for capacitated vehicle routing. Math. Program. 197, 451\u2013497 (2023)","journal-title":"Math. Program."},{"issue":"19","key":"2094_CR7","doi-asserted-by":"publisher","first-page":"5755","DOI":"10.1080\/00207543.2010.512620","volume":"49","author":"Huaping Chen","year":"2011","unstructured":"Chen, Huaping, Bing, Du., Huang, George Q.: Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. Int. J. Prod. Res. 49(19), 5755\u20135778 (2011)","journal-title":"Int. J. Prod. Res."},{"key":"2094_CR8","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-642-45030-3_56","volume-title":"International Symposium on Algorithms and Computation","author":"Jing Chen","year":"2013","unstructured":"Chen, Jing, Guo, He., Han, Xin, Iwama, Kazuo: The train delivery problem revisited. In: International Symposium on Algorithms and Computation, pp. 601\u2013611. Springer, Berlin (2013)"},{"issue":"2","key":"2094_CR9","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1016\/j.ijpe.2006.02.010","volume":"103","author":"Purushothaman Damodaran","year":"2006","unstructured":"Damodaran, Purushothaman, Manjeshwar, Praveen Kumar, Srihari, Krishnaswami: Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms. Int. J. Prod. Econ. 103(2), 882\u2013891 (2006)","journal-title":"Int. J. Prod. Econ."},{"issue":"1","key":"2094_CR10","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"George B Dantzig","year":"1959","unstructured":"Dantzig, George B., Ramser, John H.: The truck dispatching problem. Manage. Sci. 6(1), 80\u201391 (1959)","journal-title":"Manage. Sci."},{"key":"2094_CR11","first-page":"94","volume-title":"International Workshop on Approximation and Online Algorithms","author":"Aparna Das","year":"2010","unstructured":"Das, Aparna, Mathieu, Claire, Mozes, Shay: The train delivery problem-vehicle routing meets bin packing. In: International Workshop on Approximation and Online Algorithms, pp. 94\u2013105. Springer, Berlin (2010)"},{"issue":"7","key":"2094_CR12","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1016\/S0305-0548(00)00078-2","volume":"29","author":"Lionel Dupont","year":"2002","unstructured":"Dupont, Lionel, Dhaenens-Flipo, Clarisse: Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Comput. Oper. Res. 29(7), 807\u2013819 (2002)","journal-title":"Comput. Oper. Res."},{"key":"2094_CR13","first-page":"251","volume-title":"International Conference on Integer Programming and Combinatorial Optimization","author":"Zachary Friggstad","year":"2022","unstructured":"Friggstad, Zachary, Mousavi, Ramin, Rahgoshay, Mirmahdi, Salavatipour, Mohammad R.: Improved approximations for capacitated vehicle routing with unsplittable client demands. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 251\u2013261. Springer, Berlin (2022)"},{"issue":"3","key":"2094_CR14","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1002\/net.3230110308","volume":"11","author":"Bruce L Golden","year":"1981","unstructured":"Golden, Bruce L., Wong, Richard T.: Capacitated arc routing problems. Networks 11(3), 305\u2013315 (1981)","journal-title":"Networks"},{"key":"2094_CR15","first-page":"63:1","volume":"251","author":"Fabrizio Grandoni","year":"2023","unstructured":"Grandoni, Fabrizio, Mathieu, Claire, Zhou, Hang: Unsplittable Euclidean capacitated vehicle routing: a $$(2+\\epsilon )$$-approximation algorithm. Innov. Theor. Comput. Sci. (ITCS) 251, 63:1-63:13 (2023)","journal-title":"Innov. Theor. Comput. Sci. (ITCS)"},{"issue":"4","key":"2094_CR16","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1287\/moor.10.4.527","volume":"10","author":"Mordecai Haimovich","year":"1985","unstructured":"Haimovich, Mordecai, Rinnooy Kan, Alexander H. G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527\u2013542 (1985)","journal-title":"Math. Oper. Res."},{"key":"2094_CR17","doi-asserted-by":"crossref","unstructured":"Hamaguchi, Shin-ya, Katoh, Naoki: A capacitated vehicle routing problem on a tree. In: International Symposium on Algorithms and Computation, pp 399\u2013407. Springer, (1998)","DOI":"10.1007\/3-540-49381-6_42"},{"issue":"2","key":"2094_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3582500","volume":"19","author":"Aditya Jayaprakash","year":"2023","unstructured":"Jayaprakash, Aditya, Salavatipour, Mohammad R.: Approximation schemes for capacitated vehicle routing on graphs of bounded treewidth, bounded doubling, or highway dimension. ACM Trans. Algor. (TALG) 19(2), 1\u201336 (2023)","journal-title":"ACM Trans. Algor. (TALG)"},{"issue":"12","key":"2094_CR19","doi-asserted-by":"publisher","first-page":"2337","DOI":"10.1080\/00207540500525254","volume":"44","author":"Ali Husseinzadeh Kashan","year":"2006","unstructured":"Kashan, Ali Husseinzadeh, Karimi, Behrooz, Jolai, Fariborz: Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes. Int. J. Prod. Res. 44(12), 2337\u20132360 (2006)","journal-title":"Int. J. Prod. Res."},{"issue":"4","key":"2094_CR20","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1287\/opre.39.4.616","volume":"39","author":"Martine Labb\u00e9","year":"1991","unstructured":"Labb\u00e9, Martine, Laporte, Gilbert, Mercure, H\u00e9lene.: Capacitated vehicle routing on trees. Oper. Res. 39(4), 616\u2013622 (1991)","journal-title":"Oper. Res."},{"key":"2094_CR21","doi-asserted-by":"crossref","unstructured":"Mathieu, Claire, Zhou, Hang: A PTAS for capacitated vehicle routing on trees. ACM Trans. Algor. (TALG) 19(2), 1\u201328 (2023)","DOI":"10.1145\/3575799"},{"issue":"2","key":"2094_CR22","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0925-5273(03)00092-6","volume":"87","author":"Sharif Melouk","year":"2004","unstructured":"Melouk, Sharif, Damodaran, Purushothaman, Chang, Ping-Yu.: Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ. 87(2), 141\u2013147 (2004)","journal-title":"Int. J. Prod. Econ."},{"issue":"2","key":"2094_CR23","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.ejor.2020.01.065","volume":"285","author":"\u0130brahim Muter","year":"2020","unstructured":"Muter, \u0130brahim: Exact algorithms to minimize makespan on single and parallel batch processing machines. Eur. J. Oper. Res. 285(2), 470\u2013483 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"10","key":"2094_CR24","doi-asserted-by":"publisher","first-page":"1720","DOI":"10.1016\/j.cor.2009.12.007","volume":"37","author":"N Rafiee Parsa","year":"2010","unstructured":"Rafiee Parsa, N., Karimi, Behrooz, Kashan, Ali Husseinzadeh: A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes. Comput. Oper. Res. 37(10), 1720\u20131730 (2010)","journal-title":"Comput. Oper. Res."},{"key":"2094_CR25","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, Thomas: The entropy rounding method in approximation algorithms. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 356\u2013372. SIAM, (2012)","DOI":"10.1137\/1.9781611973099.32"},{"issue":"7","key":"2094_CR26","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1080\/00207549408957026","volume":"32","author":"Reha Uzsoy","year":"1994","unstructured":"Uzsoy, Reha: Scheduling a single batch processing machine with non-identical job sizes. Int. J. Prod. Res. 32(7), 1615\u20131635 (1994)","journal-title":"Int. J. Prod. Res."},{"key":"2094_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"David P Williamson","year":"2011","unstructured":"Williamson, David P., Shmoys, David B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"key":"2094_CR28","first-page":"1","volume":"44","author":"Yuanxiao Wu","year":"2020","unstructured":"Wu, Yuanxiao, Xiwen, L.: Capacitated vehicle routing problem on line with unsplittable demands. J. Comb. Optim. 44, 1\u201311 (2020)","journal-title":"J. Comb. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02094-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02094-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02094-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:02:51Z","timestamp":1750176171000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02094-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,25]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2094"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02094-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2024,5,25]]},"assertion":[{"value":"29 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}