Control of mobile networks using dynamic vehicle routing

This thesis considers the Dynamic Pickup and Delivery Problem (DPDP), a dynamic multi-stage vehicle routing problem in which each demand requires two spatially separated services: pickup service at its source location and then delivery service at its destination location. The Dynamic Pickup and Delivery Problem arises in many practical applications, including taxi and courier services, manufacturing and inventory routing, emergency services, mobile sensor networks, Unmanned Aerial Vehicle (UAV) routing, and delay tolerant wireless networks. The main contribution of this thesis is the quantification of the delay performance of the Dynamic Pickup and Delivery Problem as a function of the number of vehicles, the total arrival rate of messages, the required message service times, the vehicle velocity, and the network area. Two lower bounds are derived. First, the Universal Lower Bound quantifies the impact of spatially separated service locations and system loading on average delay. The second lower bound is derived by reducing the two-stage Dynamic Pickup and Delivery Problem to the single-stage Dynamic Traveling Repairperson Problem (DTRP). Policies are then presented for which these lower bounds are tight as a function of the system scaling parameters (up to a constant). The impact of information and inter-vehicle relays is also studied. The last part of this thesis examines the application of the Dynamic Pickup and Delivery Problem to mobile multi-agent wireless networks from a physical layer perspective, seeking insights for the control of the network to achieve trade-offs between throughput and delay.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2007

Author dc:creator

• Waisanen-Hatipoglu, Holly A

Advisor dc:contributor.advisor

• Munther A. Dahleh and Devavrat Shah.

• Electrical Engineering and Computer Science.

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/42244

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/42244