This paper studies the precedence-constrained task assignment problem for a team of heterogeneous vehicles to deliver packages to a set of dispersed customers subject to precedence constraints that specify which customers need to be visited before which other customers. A truck and a micro drone with complementary capabilities are employed where the truck is restricted to travel in a street network and the micro drone, restricted by its loading capacity and operation range, can fly from the truck to perform the last-mile package deliveries. The objective is to minimize the time to serve all the customers respecting every precedence constraint. The problem is shown to be NP-hard, and a lower bound on the optimal time to serve all the customers is constructed by using tools from graph theory. Then, integrating with a topological sorting technique, several heuristic task assignment algorithms are proposed to solve the task assignment problem. Numerical simulations show the superior performances of the proposed algorithms compared with popular genetic algorithms. Note to Practitioners - This paper presents several task assignment algorithms for the precedence-constrained package delivery for the team of a truck and a micro drone. The truck can carry the drone moving in a street network, while the drone completes the last-mile package deliveries. The practical contributions of this paper are fourfold. First, the precedence constraints on the ordering of the customers to be served are considered, which enables complex logistic scheduling for customers prioritized according to their urgency or importance. Second, the package delivery optimization problem is shown to be NP-hard, which clearly shows the need for creative approximation algorithms to solve the problem. Third, the constructed lower bound on the optimal time to serve all the customers helps to clarify for practitioners the limiting performance of a feasible solution. Fourth, the proposed task assignment algorithms are efficient and can be adapted for real ...


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles


    Beteiligte:
    Bai, Xiaoshan (Autor:in) / Cao, Ming (Autor:in) / Yan, Weisheng (Autor:in) / Ge, Shuzhi Sam (Autor:in)

    Erscheinungsdatum :

    12.01.2020


    Anmerkungen:

    Bai , X , Cao , M , Yan , W & Ge , S S 2020 , ' Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles ' , IEEE Transactions on Automation Science and Engineering , vol. 17 , no. 1 , 8725908 , pp. 248-260 . https://doi.org/10.1109/TASE.2019.2914113



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    000




    Multi-way stop intersection precedence for autonomous vehicles

    PARASURAM AISHWARYA / LUDERS BRANDON | Europäisches Patentamt | 2023

    Freier Zugriff

    MULTI-WAY STOP INTERSECTION PRECEDENCE FOR AUTONOMOUS VEHICLES

    PARASURAM AISHWARYA / LUDERS BRANDON | Europäisches Patentamt | 2020

    Freier Zugriff

    Multi-way stop intersection precedence for autonomous vehicles

    PARASURAM AISHWARYA / LUDERS BRANDON | Europäisches Patentamt | 2021

    Freier Zugriff

    MULTI-WAY STOP INTERSECTION PRECEDENCE FOR AUTONOMOUS VEHICLES

    PARASURAM AISHWARYA / LUDERS BRANDON | Europäisches Patentamt | 2021

    Freier Zugriff