{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:26:47Z","timestamp":1787318807894,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Control Optim."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>In this paper we introduce a dynamic vehicle routing problem in which there are multiple vehicles and multiple priority classes of service demands. Service demands of each priority class arrive in the environment randomly over time and require a random amount of on-site service that is characteristic of the class. To service a demand, one of the vehicles must travel to the demand location and remain there for the required on-site service time. The quality of service provided to each class is given by the expected delay between the arrival of a demand in the class and that demand's service completion. The goal is to design a routing policy for the service vehicles which minimizes a convex combination of the delays for each class. First, we provide a lower bound on the achievable values of the convex combination of delays. Then, we propose a novel routing policy and analyze its performance under heavy-load conditions (i.e., when the fraction of time the service vehicles spend performing on-site service approaches one). The policy performs within a constant factor of the lower bound, where the constant depends only on the number of classes, and is independent of the number of vehicles, the arrival rates of demands, the on-site service times, and the convex combination coefficients.<\/jats:p>","DOI":"10.1137\/090749347","type":"journal-article","created":{"date-parts":[[2010,1,15]],"date-time":"2010-01-15T18:09:05Z","timestamp":1263578945000},"page":"3224-3245","source":"Crossref","is-referenced-by-count":46,"title":["Dynamic Vehicle Routing with Priority Classes of Stochastic Demands"],"prefix":"10.1137","volume":"48","author":[{"given":"Stephen L.","family":"Smith","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Pavone","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Bullo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emilio","family":"Frazzoli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,1,15]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2002.805653"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005200"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.4.601"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.1.60"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, P. Raghavan, and M. Sudan,\n                      The minimum latency problem\n                      , in Proceedings of the ACM Symposium on the Theory of Computing, Montreal, Canada, 1994, pp. 163\u2013171.","DOI":"10.1145\/195058.195125"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/050645464"},{"key":"R7","unstructured":"S. D. Bopardikar, S. L. Smith, F. Bullo, and J. P. Hespanha,\n                      Dynamic vehicle routing for translating demands: Stability analysis and receding-horizon policies\n                      , IEEE Trans. Automat. Control, to appear."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.3.810"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"E. Frazzoli and F. Bullo,\n                      Decentralized algorithms for vehicle routing in a stochastic time-varying environment\n                      , in Proceedings of the IEEE Conference on Decision and Control, Paradise Island, Bahamas, 2004, pp. 3357\u20133363.","DOI":"10.1109\/CDC.2004.1429220"},{"key":"R10","unstructured":"L. Kleinrock,\n                      Queueing Systems. Volume\n                      II\n                      : Computer Applications\n                      , John Wiley, New York, 1976."},{"key":"R11","unstructured":"A. Larsen,\n                      The Dynamic Vehicle Routing Problem\n                      , Ph.D. thesis, Technical University of Denmark, Lyngby, Denmark, 2000."},{"key":"R12","unstructured":"R. C. Larson and A. R. Odoni,\n                      Urban Operations Research\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1981."},{"key":"R13","unstructured":"D. G. Luenberger,\n                      Linear and Nonlinear Programming\n                      , 2nd ed., Addison\u2013Wesley, Reading, MA, 1984."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00189-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-008-0101-1"},{"key":"R16","unstructured":"M. Pavone, E. Frazzoli, and F. Bullo,\n                      Distributed and adaptive algorithms for vehicle routing in a stochastic and dynamic environment\n                      , IEEE Trans. Automat. Control, to appear; available online from http:\/\/arxiv.org\/abs\/0903.3624."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Pavone, S. L. Smith, F. Bullo, and E. Frazzoli,\n                      Dynamic multi-vehicle routing with multiple classes of demands\n                      , in Proceedings of the American Control Conference, St. Louis, MO, 2009, pp. 604\u2013609.","DOI":"10.1109\/ACC.2009.5160557"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.1188"},{"key":"R19","unstructured":"H. N. Psaraftis,\n                      Dynamic vehicle routing problems\n                      , in Vehicle Routing: Methods and Studies, B. Golden and A. Assad, eds., North\u2013Holland, Amsterdam, 1988, pp. 223\u2013248."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysconle.2009.07.001"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"S. L. Smith, M. Pavone, F. Bullo, and E. Frazzoli,\n                      Dynamic traveling repairperson with priority demands\n                      , in Proceedings of the IEEE Conference on Decision and Control, Canc\u00fan, M\u00e9xico, 2008, pp. 1206\u20131211.","DOI":"10.1109\/CDC.2008.4739284"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1030.0073"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.4.749"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.925849"},{"key":"R25","unstructured":"R. W. Wolff,\n                      Stochastic Modeling and the Theory of Queues\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1989."},{"key":"R26","unstructured":"H. Xu,\n                      Optimal Policies for Stochastic and Dynamic Vehicle Routing Problems\n                      , Ph.D. thesis, Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, MA, 1995."}],"container-title":["SIAM Journal on Control and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090749347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:40:46Z","timestamp":1787316046000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090749347"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090749347"],"URL":"https:\/\/doi.org\/10.1137\/090749347","relation":{},"ISSN":["0363-0129","1095-7138"],"issn-type":[{"value":"0363-0129","type":"print"},{"value":"1095-7138","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}