Strategic dynamic vehicle routing with spatio-temporal dependent demands
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2012
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/68498 |
| _version_ | 1826198432986955776 |
|---|---|
| author | Feijer, Diego (Diego Francisco Feijer Rovira) |
| author2 | Emilio Frazzoli. |
| author_facet | Emilio Frazzoli. Feijer, Diego (Diego Francisco Feijer Rovira) |
| author_sort | Feijer, Diego (Diego Francisco Feijer Rovira) |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011. |
| first_indexed | 2024-09-23T11:04:52Z |
| format | Thesis |
| id | mit-1721.1/68498 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:04:52Z |
| publishDate | 2012 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/684982019-04-11T00:28:46Z Strategic dynamic vehicle routing with spatio-temporal dependent demands Feijer, Diego (Diego Francisco Feijer Rovira) Emilio Frazzoli. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011. Cataloged from PDF version of thesis. Includes bibliographical references (p. 51-53). Dynamic vehicle routing problems address the issue of determining optimal routes for a set of vehicles, to serve a given set of demands that arrive sequentially in time. Traditionally, demands are assumed to be generated over time by an exogenous stochastic process. This thesis is concerned with the study of dynamic vehicle routing problems where demands are strategically placed in the space by an agent with selfish interests and physical constraints. In particular, we focus on the following problem: a team of vehicles seek to device dynamic routing policies that minimize the average waiting time of a typical demand, from the moment it is placed in the space until its location is visited; while an adversarial agent operating from a central depot with limited capacity aims at the opposite, strategically choosing the spatio-temporal point process according to which place demands. We model the above problem and its inherent pure conflict of interests as a zero-sum game, and characterize equilibria under heavy load regime. For the analysis we discriminate between two cases: bounded and unbounded domains. In both cases we show that a routing policy based on performing successive TSP tours through outstanding demands and a power-law spatial distribution of demands are optimal, saddle point of the utility function of the game. The latter emerges as the unique solution of maximizing a non-convex nowhere differentiable functional over the infinite-dimensional space of probability densities; the non-convexity is the result of the spatio-temporal dependence induced by the physical constraints imposed on the behavior of the agent, and the non-differentiability is due to the emptiness of the interior of the positive cone of integrable functions. We solve this problem applying Fenchel conjugate duality for partially finite programming in the case of bounded domains; and a direct duality approach exploiting the structure of a concave integral functional part of the objective and the linear equality constraints, for unbounded domains. Remarkably, all the results obtained hold for any domain with a sufficiently smooth boundary, clossedness or connectedness is not needed. We provide numerical simulations to validate the theory. by Diego Feijer. S.M. 2012-01-12T19:32:30Z 2012-01-12T19:32:30Z 2011 2011 Thesis http://hdl.handle.net/1721.1/68498 770668096 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 53 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Feijer, Diego (Diego Francisco Feijer Rovira) Strategic dynamic vehicle routing with spatio-temporal dependent demands |
| title | Strategic dynamic vehicle routing with spatio-temporal dependent demands |
| title_full | Strategic dynamic vehicle routing with spatio-temporal dependent demands |
| title_fullStr | Strategic dynamic vehicle routing with spatio-temporal dependent demands |
| title_full_unstemmed | Strategic dynamic vehicle routing with spatio-temporal dependent demands |
| title_short | Strategic dynamic vehicle routing with spatio-temporal dependent demands |
| title_sort | strategic dynamic vehicle routing with spatio temporal dependent demands |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/68498 |
| work_keys_str_mv | AT feijerdiegodiegofranciscofeijerrovira strategicdynamicvehicleroutingwithspatiotemporaldependentdemands |