{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T12:56:29Z","timestamp":1774356989984,"version":"3.50.1"},"reference-count":21,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2003,6,3]],"date-time":"2003-06-03T00:00:00Z","timestamp":1054598400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2003,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we describe a new integer programming formulation for the Traveling Salesman Problem with mixed Deliveries and Collections (TSPDC) based on a two\u2010commodity network flow approach. We present new lower bounds that are derived from the linear relaxation of the new formulation by adding valid inequalities, in a cutting\u2010plane fashion. The resulting lower bounds are embedded in a branch\u2010and\u2010cut algorithm for the optimal solution of the TSPDC. Computational results on different classes of test problems taken from the literature indicate the effectiveness of the proposed method. \u00a9 2003 Wiley Periodicals, Inc.<\/jats:p>","DOI":"10.1002\/net.10079","type":"journal-article","created":{"date-parts":[[2003,7,22]],"date-time":"2003-07-22T10:11:40Z","timestamp":1058868700000},"page":"26-41","source":"Crossref","is-referenced-by-count":41,"title":["An exact algorithm for the Traveling Salesman Problem with Deliveries and Collections"],"prefix":"10.1002","volume":"42","author":[{"given":"R.","family":"Baldacci","sequence":"first","affiliation":[]},{"given":"E.","family":"Hadjiconstantinou","sequence":"additional","affiliation":[]},{"given":"A.","family":"Mingozzi","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(94)90016-7"},{"key":"e_1_2_1_3_2","unstructured":"D.Applegate R.Bixby V.Chv\u00e1tal andW.Cook Special session on tsp 15th Int Symp on Mathematical Programming University of Michigan 1994."},{"key":"e_1_2_1_4_2","volume-title":"Finding cuts in the tsp","author":"Applegate D.","year":"1995"},{"key":"e_1_2_1_5_2","unstructured":"D.Applegate R.Bixby V.Chv\u00e1tal andW.Cook Concorde: A code for solving traveling salesman problems World Wide Web http:\/\/www.math.princeton.edu\/tsp\/concorde.html 2001."},{"key":"e_1_2_1_6_2","volume-title":"Computational results with a branch and cut code for the capacitated vehicle routing problem","author":"Augerat P.","year":"1995"},{"key":"e_1_2_1_7_2","volume-title":"New heuristic methods for the traveling salesman problem with mixed deliveries and collections","author":"Baldacci R.","year":"1999"},{"key":"e_1_2_1_8_2","volume-title":"An exact algorithm for the capacitated vehicle routing problem based on a two\u2010commodity network flow formulation","author":"Baldacci R.","year":"1999"},{"key":"e_1_2_1_9_2","first-page":"167","article-title":"A two\u2010commodity network flow approach to the traveling salesman problem","volume":"41","author":"Finke G.","year":"1984","journal-title":"Congr Numer"},{"key":"e_1_2_1_10_2","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(95)00036-4"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(98)00085-9"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718515.ch10"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_1_15_2","unstructured":"K.Halse Modelling and solving complex vehicle routing problems Ph.D. thesis IMSOR Technical University of Denmark 1992."},{"key":"e_1_2_1_16_2","unstructured":"ILOG CPLEX 6.5 callable library 2001."},{"key":"e_1_2_1_17_2","series-title":"The traveling salesman problem","first-page":"225","volume-title":"Network Models, Handbooks in Operations Research and Management Science","author":"J\u00fcnger M.","year":"1995"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230706"},{"key":"e_1_2_1_19_2","unstructured":"A.Lucena Exact solution approaches for the vehicle routing problem Ph.D. thesis Management Science Dept. Imperial College London 1986."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90360-3"},{"key":"e_1_2_1_21_2","volume-title":"The traveling salesman polytope revisited","author":"Naddef D.","year":"1998"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580850"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.10079","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.10079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,18]],"date-time":"2023-11-18T00:46:42Z","timestamp":1700268402000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.10079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,8]]}},"alternative-id":["10.1002\/net.10079"],"URL":"https:\/\/doi.org\/10.1002\/net.10079","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,6,3]]}}}