Dynamic Vehicle Routing with Priority Classes of Stochastic Demands
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 characteristi...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society of Industrial and Applied Mathematics
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/57470 https://orcid.org/0000-0002-0505-1400 |
| _version_ | 1826203385487949824 |
|---|---|
| author | Smith, Stephen L. Pavone, Marco Bullo, Francesco Frazzoli, Emilio |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Smith, Stephen L. Pavone, Marco Bullo, Francesco Frazzoli, Emilio |
| author_sort | Smith, Stephen L. |
| collection | MIT |
| description | 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 |
| first_indexed | 2024-09-23T12:35:46Z |
| format | Article |
| id | mit-1721.1/57470 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:35:46Z |
| publishDate | 2010 |
| publisher | Society of Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/574702022-10-01T09:59:34Z Dynamic Vehicle Routing with Priority Classes of Stochastic Demands Smith, Stephen L. Pavone, Marco Bullo, Francesco Frazzoli, Emilio Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Frazzoli, Emilio Smith, Stephen L. Pavone, Marco Frazzoli, Emilio vehicle routing optimization multiagent systems heterogeneous systems 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 National Science Foundation (grants 0705451 and 0705453) Office of Naval Research (grant N00014-07-1-0721) Air Force Office of Scientific Research (grant FA9550-07-1-0528) 2010-08-04T14:12:45Z 2010-08-04T14:12:45Z 2010-01 2009-02 Article http://purl.org/eprint/type/JournalArticle 0363-0129 1095-7138 http://hdl.handle.net/1721.1/57470 Smith, Stephen L. et al. “Dynamic Vehicle Routing with Priority Classes of Stochastic Demands.” SIAM Journal on Control and Optimization 48.5 (2010): 3224-3245. ©2010 Society for Industrial and Applied Mathematics https://orcid.org/0000-0002-0505-1400 en_US http://dx.doi.org/10.1137/090749347 SIAM Journal on Control and Optimization Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society of Industrial and Applied Mathematics SIAM |
| spellingShingle | vehicle routing optimization multiagent systems heterogeneous systems Smith, Stephen L. Pavone, Marco Bullo, Francesco Frazzoli, Emilio Dynamic Vehicle Routing with Priority Classes of Stochastic Demands |
| title | Dynamic Vehicle Routing with Priority Classes of Stochastic Demands |
| title_full | Dynamic Vehicle Routing with Priority Classes of Stochastic Demands |
| title_fullStr | Dynamic Vehicle Routing with Priority Classes of Stochastic Demands |
| title_full_unstemmed | Dynamic Vehicle Routing with Priority Classes of Stochastic Demands |
| title_short | Dynamic Vehicle Routing with Priority Classes of Stochastic Demands |
| title_sort | dynamic vehicle routing with priority classes of stochastic demands |
| topic | vehicle routing optimization multiagent systems heterogeneous systems |
| url | http://hdl.handle.net/1721.1/57470 https://orcid.org/0000-0002-0505-1400 |
| work_keys_str_mv | AT smithstephenl dynamicvehicleroutingwithpriorityclassesofstochasticdemands AT pavonemarco dynamicvehicleroutingwithpriorityclassesofstochasticdemands AT bullofrancesco dynamicvehicleroutingwithpriorityclassesofstochasticdemands AT frazzoliemilio dynamicvehicleroutingwithpriorityclassesofstochasticdemands |