{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T06:06:23Z","timestamp":1648620383228},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T00:00:00Z","timestamp":1595462400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T00:00:00Z","timestamp":1595462400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"THD - Technische Hochschule Deggendorf"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Efficient feasibility tests are important in many heuristics for routing problems. This paper considers several variants of pickup-and-delivery problems with trailers. Its contribution consists in the description of constant-time procedures for testing observance of capacity constraints when inserting tasks into routes. It is demonstrated that the presence of vehicles with detachable trailers makes capacity feasibility tests considerably more involved.\n<\/jats:p>","DOI":"10.1007\/s10288-020-00452-z","type":"journal-article","created":{"date-parts":[[2020,7,23]],"date-time":"2020-07-23T17:02:41Z","timestamp":1595523761000},"page":"289-307","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On efficient testing of capacity constraints in pickup-and-delivery problems with trailers"],"prefix":"10.1007","volume":"19","author":[{"given":"Michael","family":"Drexl","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,23]]},"reference":[{"key":"452_CR1","doi-asserted-by":"crossref","unstructured":"Battarra M, Cordeau JF, Iori M (2014) Pickup-and-delivery problems for goods transportation. In: Toth P, Vigo D (eds) Vehicle routing: problems, methods, and applications. Society for industrial and applied mathematics, Philadelphia, pp 161\u2013191","DOI":"10.1137\/1.9781611973594.ch6"},{"key":"452_CR2","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1080\/08839510050119253","volume":"14","author":"H B\u00fcrckert","year":"2000","unstructured":"B\u00fcrckert H, Fischer K, Vierke G (2000) Holonic transport scheduling with TELETRUCK. Appl Artif Intell 14:697\u2013725","journal-title":"Appl Artif Intell"},{"issue":"2","key":"452_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tre.2007.07.009","volume":"44","author":"R Cheung","year":"2008","unstructured":"Cheung R, Shi N, Powell W, Sim\u00e3o H (2008) An attribute-decision model for cross-border drayage problem. Transp Res Part E 44(2):217\u2013234","journal-title":"Transp Res Part E"},{"key":"452_CR4","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.cor.2014.06.008","volume":"55","author":"R Cuda","year":"2015","unstructured":"Cuda R, Guastaroba G, Speranza M (2015) A survey on two-echelon routing problems. Comput Oper Res 55:185\u2013199","journal-title":"Comput Oper Res"},{"key":"452_CR5","doi-asserted-by":"crossref","unstructured":"Doerner K, Salazar-Gonz\u00e1lez J (2014) Pickup-and-delivery problems for people transportation. In: Vigo D, Toth P (eds) Vehicle routing: problems, methods, and applications. Society for industrial and applied mathematics, Philadelphia, pp 193\u2013212","DOI":"10.1137\/1.9781611973594.ch7"},{"key":"452_CR6","unstructured":"Drexl M (2018) On the one-to-one pickup-and-delivery problem with time windows and trailers. Technical Report 1816, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz"},{"issue":"1","key":"452_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.orl.2010.11.004","volume":"39","author":"M Firat","year":"2011","unstructured":"Firat M, Woeginger G (2011) Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh. Oper Res Lett 39(1):32\u201335","journal-title":"Oper Res Lett"},{"issue":"4","key":"452_CR8","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s10732-005-1997-2","volume":"11","author":"B Funke","year":"2005","unstructured":"Funke B, Gr\u00fcnert T, Irnich S (2005) Local search for vehicle routing and scheduling problems: review and conceptual integration. J Heuristics 11(4):267\u2013306","journal-title":"J Heuristics"},{"issue":"1","key":"452_CR9","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.ejor.2016.03.040","volume":"254","author":"P Grangier","year":"2016","unstructured":"Grangier P, Gendreau M, Lehu\u00e9d\u00e9 F, Rousseau LM (2016) An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. Eur J Oper Res 254(1):80\u201391","journal-title":"Eur J Oper Res"},{"issue":"2","key":"452_CR10","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1287\/trsc.2018.0837","volume":"53","author":"T Gschwind","year":"2019","unstructured":"Gschwind T, Drexl M (2019) Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transp Sci 53(2):480\u2013491","journal-title":"Transp Sci"},{"key":"#cr-split#-452_CR11.1","doi-asserted-by":"crossref","unstructured":"Haugland D, Ho S (2010) Feasibility testing for dial-a-ride problems. In: Chen B","DOI":"10.1007\/978-3-642-14355-7_18"},{"key":"#cr-split#-452_CR11.2","unstructured":"(ed) Algorithmic aspects in information and management. AAIM 2010. Lecture notes in computer science 6124. Springer, Berlin. pp 170-179"},{"issue":"3","key":"452_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0167-6377(02)00120-7","volume":"30","author":"B Hunsaker","year":"2002","unstructured":"Hunsaker B, Savelsbergh M (2002) Efficient feasibility testing for dial-a-ride problems. Oper Res Lett 30(3):169\u2013173","journal-title":"Oper Res Lett"},{"issue":"1","key":"452_CR13","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00291-007-0083-6","volume":"30","author":"S Irnich","year":"2008","unstructured":"Irnich S (2008a) Resource extension functions: properties, inversion, and generalization to segments. OR Spectrum 30(1):113\u2013148","journal-title":"OR Spectrum"},{"issue":"2","key":"452_CR14","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/ijoc.1070.0239","volume":"20","author":"S Irnich","year":"2008","unstructured":"Irnich S (2008b) A unified modeling and solution framework for vehicle routing and local search-based metaheuristics. INFORMS J Comput 20(2):270\u2013287","journal-title":"INFORMS J Comput"},{"issue":"8","key":"452_CR15","doi-asserted-by":"publisher","first-page":"2405","DOI":"10.1016\/j.cor.2005.02.020","volume":"33","author":"S Irnich","year":"2006","unstructured":"Irnich S, Funke B, Gr\u00fcnert T (2006) Sequential search and its application to vehicle-routing problems. Comput Oper Res 33(8):2405\u20132429","journal-title":"Comput Oper Res"},{"key":"452_CR16","first-page":"337","volume-title":"Local search in combinatorial optimization","author":"G Kindervater","year":"1997","unstructured":"Kindervater G, Savelsbergh M (1997) Vehicle routing: handling edge exchanges. In: Aarts E, Lenstra J (eds) Local search in combinatorial optimization. Wiley, Chichester, pp 337\u2013360"},{"issue":"3","key":"452_CR17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.orl.2013.01.007","volume":"41","author":"R Masson","year":"2013","unstructured":"Masson R, Lehu\u00e9d\u00e9 F, P\u00e9ton O (2013) Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers. Oper Res Lett 41(3):211\u2013215","journal-title":"Oper Res Lett"},{"key":"452_CR18","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.cor.2017.01.020","volume":"83","author":"S Parragh","year":"2017","unstructured":"Parragh S, Cordeau JF (2017) Branch-and-price and adaptive large neighborhood search for the truck and trailer routing problem with time windows. Comput Oper Res 83:28\u201344","journal-title":"Comput Oper Res"},{"issue":"1","key":"452_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s11301-008-0033-7","volume":"58","author":"S Parragh","year":"2008","unstructured":"Parragh S, Doerner K, Hartl R (2008a) A survey on pickup and delivery models part I: transportation between customers and depot. J Betriebswirtschaft 58(1):21\u201351","journal-title":"J Betriebswirtschaft"},{"issue":"2","key":"452_CR20","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s11301-008-0036-4","volume":"58","author":"S Parragh","year":"2008","unstructured":"Parragh S, Doerner K, Hartl R (2008b) A survey on pickup and delivery models part II: transportation between pickup and delivery locations. J Betriebswirtschaft 58(2):81\u2013117","journal-title":"J Betriebswirtschaft"},{"issue":"1","key":"452_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2014.01.005","volume":"238","author":"C Prodhon","year":"2014","unstructured":"Prodhon C, Prins C (2014) A survey of recent research on location-routing problems. Eur J Oper Res 238(1):1\u201317","journal-title":"Eur J Oper Res"},{"issue":"3","key":"452_CR22","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.ejor.2004.09.004","volume":"171","author":"S Ropke","year":"2006","unstructured":"Ropke S, Pisinger D (2006) A Unified Heuristic for a Large Class of Vehicle Routing Problems with Backhauls. Eur J Oper Res 171(3):750\u2013775","journal-title":"Eur J Oper Res"},{"issue":"5","key":"452_CR23","doi-asserted-by":"publisher","first-page":"1174","DOI":"10.1287\/trsc.2017.0765","volume":"52","author":"AK Rothenb\u00e4cher","year":"2018","unstructured":"Rothenb\u00e4cher AK, Drexl M, Irnich S (2018) Branch-and-price-and-cut for the truck-and-trailer routing problem with time windows. Transp Sci 52(5):1174\u20131190","journal-title":"Transp Sci"},{"issue":"1","key":"452_CR24","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF02022044","volume":"4","author":"M Savelsbergh","year":"1985","unstructured":"Savelsbergh M (1985) Local search in routing problems with time windows. Ann Oper Res 4(1):285\u2013305","journal-title":"Ann Oper Res"},{"issue":"1","key":"452_CR25","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0377-2217(90)90091-O","volume":"47","author":"M Savelsbergh","year":"1990","unstructured":"Savelsbergh M (1990) An efficient implementation of local search algorithms for constrained routing problems. Eur J Oper Res 47(1):75\u201385","journal-title":"Eur J Oper Res"},{"issue":"2","key":"452_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1287\/ijoc.4.2.146","volume":"4","author":"M Savelsbergh","year":"1992","unstructured":"Savelsbergh M (1992) The vehicle routing problem with time windows: minimizing route duration. ORSA J Comput 4(2):146\u2013154","journal-title":"ORSA J Comput"},{"issue":"2","key":"452_CR27","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1287\/trsc.2016.0730","volume":"52","author":"C Tilk","year":"2018","unstructured":"Tilk C, Bianchessi N, Drexl M, Irnich S, Meisel F (2018) Branch-and-price-and-cut for the active-passive vehicle-routing problem. Transp Sci 52(2):300\u2013319","journal-title":"Transp Sci"},{"issue":"3","key":"452_CR28","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1016\/j.ejor.2013.09.045","volume":"234","author":"T Vidal","year":"2014","unstructured":"Vidal T, Crainic TG, Gendreau M, Prins C (2014) A unified solution framework for multi-attribute vehicle routing problems. Eur J Oper Res 234(3):658\u2013673","journal-title":"Eur J Oper Res"},{"key":"452_CR29","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.tre.2013.12.007","volume":"62","author":"Z Xue","year":"2014","unstructured":"Xue Z, Zhang C, Lin W, Miao L, Yang P (2014) A Tabu search heuristic for the local container drayage problem under a new operation mode. Transp Res Part E 62:136\u2013150","journal-title":"Transp Res Part E"},{"issue":"1","key":"452_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1023\/A:1009873324187","volume":"3","author":"M Yagiura","year":"1999","unstructured":"Yagiura M, Ibaraki T (1999) Analyses on the 2 and 3-flip neighborhoods for the MAX SAT. J Comb Opt 3(1):95\u2013114","journal-title":"J Comb Opt"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00452-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10288-020-00452-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-020-00452-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T23:48:33Z","timestamp":1626997713000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10288-020-00452-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,23]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["452"],"URL":"https:\/\/doi.org\/10.1007\/s10288-020-00452-z","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"value":"1619-4500","type":"print"},{"value":"1614-2411","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,23]]},"assertion":[{"value":"14 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The author declares that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}