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.


    Access

    Download


    Export, share and cite



    Title :

    Control of mobile networks using dynamic vehicle routing


    Contributors:

    Publication date :

    2007


    Size :

    144 pages


    Remarks:

    Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2007.
    Includes bibliographical references (p. 141-144).


    Type of media :

    Theses


    Type of material :

    Electronic Resource


    Language :

    English




    DYNAMIC V2X NETWORKS AND VEHICLE ROUTING

    ROSALES RAFAEL / GEISSLER FLORIAN / PAULITSCH MICHAEL et al. | European Patent Office | 2022

    Free access

    DYNAMIC V2X NETWORKS AND VEHICLE ROUTING

    ROSALES RAFAEL / GEISSLER FLORIAN / PAULITSCH MICHAEL et al. | European Patent Office | 2021

    Free access

    Dynamic vehicle routing

    Goel, Asvin | Springer Verlag | 2008


    An experimental comparison of dynamic routing protocols in mobile networks

    Vadim, Glazunov / Oleg, Gusikhin / Leonid, Kurochkin et al. | IEEE | 2014


    Mobile delivery vehicle management and routing

    JAVIDAN ALI / LEVINSON JESSE SOL / STOFFEL CHRISTOPHER JOHN | European Patent Office | 2024

    Free access