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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Control of mobile networks using dynamic vehicle routing


    Beteiligte:

    Erscheinungsdatum :

    2007


    Format / Umfang :

    144 pages


    Anmerkungen:

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


    Medientyp :

    Hochschulschrift


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    DYNAMIC V2X NETWORKS AND VEHICLE ROUTING

    ROSALES RAFAEL / GEISSLER FLORIAN / PAULITSCH MICHAEL et al. | Europäisches Patentamt | 2022

    Freier Zugriff

    DYNAMIC V2X NETWORKS AND VEHICLE ROUTING

    ROSALES RAFAEL / GEISSLER FLORIAN / PAULITSCH MICHAEL et al. | Europäisches Patentamt | 2021

    Freier Zugriff

    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 | Europäisches Patentamt | 2024

    Freier Zugriff