Probabilistic on-line transportation problems with carrying-capacity constraints

This thesis presents new insights and techniques for the analysis and design of autonomous or technology-assisted ("intelligent") transportation systems. The focus is on cooperative, on-line planning and control, of a fleet of transport vehicles with limited carrying capacity, where new transportation demands enter the system in real time. The study extends an existing probabilistic framework which has provided numerous insights about vehicle scheduling and routing problems since its inception. Additionally, the thesis provides algorithms and new probabilistic cost bounds, for optimal bipartite matchings between large sets of random points and optimal stacker crane tours through large sets of random demands. A recurrent theme of the thesis is that capacity-constrained vehicles must drive passenger-less, inescapably, for some positive fraction of time (in almost any practical setting). Moreover, under probabilistic modelling for the uncertainty of demand, one can predict the aforementioned fraction precisely, using strong Laws of Large Numbers arguments; it relates to a quantity known as the Earth Mover's distance (EMD), described by a fundamental problem in transportation theory. Since the existence of an unavoidable extra cost term has significant implications, e.g., for operational budgets of shared-vehicle systems, the results illuminate a phenomenon whose neglect could prove an unfortunate oversight. To the author's knowledge, this connection of the EMD to on-line vehicle routing is novel. The thesis also provides a new study of the practical considerations imposed by the "street rules" ubiquitous among ground-based transport problems. A new efficient algorithm for the Bipartite Matching problem for points on a roadmap is given. Also given is a new explicit formulation of the EMD on road networks; very few explicit formulas for EMDs have been known previously.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Treleaven, Kyle (Kyle Ballantyne)

Advisor dc:contributor.advisor

• Emilio Frazzoli.

• Aeronautics and Astronautics.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/90730

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/90730