A stochastic and dynamic vehicle routing problem with time windows and customer impatience
In this paper, we study the problem of designing motion strategies for a team of mobile agents, required to fulfill request for on-site service in a given planar region. In our model, each service request is generated by a spatio-temporal stochastic process; once a service request has been generated...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/58729 https://orcid.org/0000-0002-0505-1400 |
| _version_ | 1826207118789705728 |
|---|---|
| author | Pavone, Marco Frazzoli, Emilio Bisnik, N. Isler, V. |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Pavone, Marco Frazzoli, Emilio Bisnik, N. Isler, V. |
| author_sort | Pavone, Marco |
| collection | MIT |
| description | In this paper, we study the problem of designing motion strategies for a team of mobile agents, required to fulfill request for on-site service in a given planar region. In our model, each service request is generated by a spatio-temporal stochastic process; once a service request has been generated, it remains active for a certain deterministic amount of time, and then expires. An active service request is fulfilled when one of the mobile agents visits the location of the request. Specific problems we investigate are the following: what is the minimum number of mobile agents needed to ensure that a certain fraction of service requests is fulfilled before expiration? What strategy should they use to ensure that this objective is attained? This problem can be viewed as the stochastic and dynamic version of the well-known vehicle routing problem with time windows. We also extend our analysis to the case in which the time service requests remain active is itself a random variable, describing customer impatience. The customers’ impatience is only known to the mobile agents via prior statistics. In this case, it is desired to minimize the fraction of service requests missed because of impatience. Finally, we show how the routing strategies presented in the paper can be executed in a distributed fashion. |
| first_indexed | 2024-09-23T13:44:46Z |
| format | Article |
| id | mit-1721.1/58729 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:44:46Z |
| publishDate | 2010 |
| publisher | Springer |
| record_format | dspace |
| spelling | mit-1721.1/587292022-09-28T15:50:50Z A stochastic and dynamic vehicle routing problem with time windows and customer impatience Pavone, Marco Frazzoli, Emilio Bisnik, N. Isler, V. Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Frazzoli, Emilio Pavone, Marco Frazzoli, Emilio mobile robotic networks sensor networks vehicle routing problem with time windows customer impatience traveling salesman problem In this paper, we study the problem of designing motion strategies for a team of mobile agents, required to fulfill request for on-site service in a given planar region. In our model, each service request is generated by a spatio-temporal stochastic process; once a service request has been generated, it remains active for a certain deterministic amount of time, and then expires. An active service request is fulfilled when one of the mobile agents visits the location of the request. Specific problems we investigate are the following: what is the minimum number of mobile agents needed to ensure that a certain fraction of service requests is fulfilled before expiration? What strategy should they use to ensure that this objective is attained? This problem can be viewed as the stochastic and dynamic version of the well-known vehicle routing problem with time windows. We also extend our analysis to the case in which the time service requests remain active is itself a random variable, describing customer impatience. The customers’ impatience is only known to the mobile agents via prior statistics. In this case, it is desired to minimize the fraction of service requests missed because of impatience. Finally, we show how the routing strategies presented in the paper can be executed in a distributed fashion. National Science Foundation (U.S.) (grants 0325716, 0715025, 0705451, 0705453) National Science Foundation (U.S.) (CCF-0634823 and CNS-0707939) 2010-09-28T14:33:05Z 2010-09-28T14:33:05Z 2008-10 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/58729 Pavone, M. et al. “A Stochastic and Dynamic Vehicle Routing Problem with Time Windows and Customer Impatience.” Mobile Networks and Applications 14.3 (2009): 350-364. https://orcid.org/0000-0002-0505-1400 en_US http://dx.doi.org/10.1007/s11036-008-0101-1 Mobile Networds and Applications Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer MIT web domain |
| spellingShingle | mobile robotic networks sensor networks vehicle routing problem with time windows customer impatience traveling salesman problem Pavone, Marco Frazzoli, Emilio Bisnik, N. Isler, V. A stochastic and dynamic vehicle routing problem with time windows and customer impatience |
| title | A stochastic and dynamic vehicle routing problem with time windows and customer impatience |
| title_full | A stochastic and dynamic vehicle routing problem with time windows and customer impatience |
| title_fullStr | A stochastic and dynamic vehicle routing problem with time windows and customer impatience |
| title_full_unstemmed | A stochastic and dynamic vehicle routing problem with time windows and customer impatience |
| title_short | A stochastic and dynamic vehicle routing problem with time windows and customer impatience |
| title_sort | stochastic and dynamic vehicle routing problem with time windows and customer impatience |
| topic | mobile robotic networks sensor networks vehicle routing problem with time windows customer impatience traveling salesman problem |
| url | http://hdl.handle.net/1721.1/58729 https://orcid.org/0000-0002-0505-1400 |
| work_keys_str_mv | AT pavonemarco astochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience AT frazzoliemilio astochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience AT bisnikn astochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience AT islerv astochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience AT pavonemarco stochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience AT frazzoliemilio stochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience AT bisnikn stochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience AT islerv stochasticanddynamicvehicleroutingproblemwithtimewindowsandcustomerimpatience |