{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T21:23:20Z","timestamp":1773523400276,"version":"3.50.1"},"reference-count":16,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[2004,11]]},"abstract":"<jats:p> We consider the multiple vehicle pickup and delivery problem (MVPDP) with the objective of minimizing the total travel cost and the fixed vehicle cost. Most of the optimization-based approaches for solving the MVPDP are developed for a restrictive hard time window or tight capacity environment that depend significantly on the reduction of the feasible solution space. We develop an alternative optimization solution approach for the MVPDP that does not require these constraints to be tight. The problem is formulated as a 0\u20131 integer-programming problem. A branch-and-cut algorithm is developed to optimally solve the problem. Four classes of valid inequalities for the MVPDP are proposed. By using the proposed solution approach, we were able to optimally solve problem instances of up to 5 vehicles and 17 customers on problems without clusters and up to 5 vehicles and 25 customers on problems with clusters within a stopping criterion of three CPU hours on a SUN Fire 4800 server. <\/jats:p>","DOI":"10.1287\/trsc.1030.0040","type":"journal-article","created":{"date-parts":[[2004,11,11]],"date-time":"2004-11-11T11:47:42Z","timestamp":1100173662000},"page":"503-514","source":"Crossref","is-referenced-by-count":113,"title":["An Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem"],"prefix":"10.1287","volume":"38","author":[{"given":"Quan","family":"Lu","sequence":"first","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089-0193"}]},{"given":"Maged","family":"Dessouky","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089-0193"}]}],"member":"109","reference":[{"key":"B1","first-page":"225","volume-title":"The Vehicle Routing Problems","author":"Desaulniers G.","year":"2001"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1080\/01966324.1986.10737198"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(91)90319-Q"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.2.319"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.29.1.63"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(85)90257-7"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.5.1050"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02031946"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580850"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1137\/1033004"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.14.2.130"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.17.3.351"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(97)00090-4"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.29.1.17"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.4.474"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.31.1.60"}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.1030.0040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T19:44:11Z","timestamp":1680464651000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/pubsonline.informs.org\/doi\/10.1287\/trsc.1030.0040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,11]]}},"alternative-id":["10.1287\/trsc.1030.0040"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1287\/trsc.1030.0040","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,11]]}}}