{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T01:37:37Z","timestamp":1773106657431,"version":"3.50.1"},"reference-count":18,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[1999,8]]},"abstract":"<jats:p> We consider the problem in which a fleet of vehicles located at a central depot is to be optimally used to serve a set of customers partitioned into two subsets of linehaul and backhaul customers. Each route starts and ends at the depot and the backhaul customers must be visited after the linehaul customers. A new (0\u20131) integer programming formulation of this problem is presented. We describe a procedure that computes a valid lower bound to the optimal solution cost by combining different heuristic methods for solving the dual of the LP-relaxation of the exact formulation. An algorithm for the exact solution of the problem is presented. Computational tests on problems proposed in the literature show the effectiveness of the proposed algorithms in solving problems up to 100 customers. <\/jats:p>","DOI":"10.1287\/trsc.33.3.315","type":"journal-article","created":{"date-parts":[[2008,10,31]],"date-time":"2008-10-31T22:50:20Z","timestamp":1225493420000},"page":"315-329","source":"Crossref","is-referenced-by-count":91,"title":["An Exact Method for the Vehicle Routing Problem with Backhauls"],"prefix":"10.1287","volume":"33","author":[{"given":"Aristide","family":"Mingozzi","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Bologna, Piazza di Porta S. Donato, 5, 40127 Bologna, Italy"}]},{"given":"Simone","family":"Giorgi","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Bologna, Piazza di Porta S. Donato, 5, 40127 Bologna, Italy"}]},{"given":"Roberto","family":"Baldacci","sequence":"additional","affiliation":[{"name":"The Management School, Imperial College, 53 Prince's Gate Exhibition Road, London SW7 2PG, United Kingdom"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(199604)43:3<415::AID-NAV7>3.0.CO;2-C"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1990.166"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1080\/10556789408805563"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589353"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110207"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.4.568"},{"key":"B9","first-page":"75","volume-title":"Proc. Babson Conf. Software Uses Transportation Logist. Management","author":"Deif I.","year":"1984"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"B11","volume-title":"Computers and Intractability: A Guide to the Theory of NP Completeness","author":"Garey M. R.","year":"1979"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.4.639"},{"key":"B13","unstructured":"Giorgi S.  Metodi esatti per il vehicle routing con backhauls.  (1995) . Thesis, University of Bologna, Italy"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(89)90057-X"},{"key":"B16","first-page":"90","volume-title":"Proc. XXI Annual Meeting S.E. TIMS","author":"Golden B. L.","year":"1985"},{"key":"B17","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"Martello S.","year":"1990"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(96)00018-4"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-85256-5_26"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.31.4.372"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1287\/inte.17.2.52"}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.33.3.315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T21:11:35Z","timestamp":1680469895000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/trsc.33.3.315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,8]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1999,8]]}},"alternative-id":["10.1287\/trsc.33.3.315"],"URL":"https:\/\/doi.org\/10.1287\/trsc.33.3.315","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,8]]}}}