Highlights A new graph representation for the Flying Sidekick TSP is proposed. An original Integer Programming formulation for this problem is provided. A branch-and-cut algorithm coupled with a column generation procedure is developed. Optimal solution of literature instances with 20 customers.

    Abstract The flying sidekick traveling salesman problem (FS-TSP) is a parcel delivery problem arising in the last-mile logistics, where the distribution plan of a driver-operated truck assisted by a drone (unmanned aerial vehicle, UAV) has to be defined. The FS-TSP is a variant of the TSP where routing decisions are integrated with customer-to-drone and customer-to-truck assignment decisions and truck-and-drone synchronization constraints. The objective is the minimization of the time required to serve all the customers, taking into account drone payload capacity and battery power constraints. In this work we provide a new representation of the FS-TSP based on the definition of an extended graph. This representation allows to model the problem by a new and compact integer linear programming formulation, where the synchronization issue is tackled in a column generation fashion, thus avoiding the usage of big-M constraints, representing one of the main drawbacks of the models present in literature. The proposed formulation has been solved by an exact approach which combines a Branch-and-Cut algorithm and a column generation procedure, strengthened by variable fixing strategies and new valid inequalities specifically defined for the problem. The proposed method has been experienced on a large set of benchmark instances. Computational results show that the proposed approach either is competitive or outperforms the best exact approach present in literature for the FS-TSP. Indeed, it is able to provide the optimal solution for all small size instances with 10 customers and for several medium size instances with 20 customers, some of them never solved before.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A column-and-row generation approach for the flying sidekick travelling salesman problem


    Beteiligte:
    Boccia, Maurizio (Autor:in) / Masone, Adriano (Autor:in) / Sforza, Antonio (Autor:in) / Sterle, Claudio (Autor:in)


    Erscheinungsdatum :

    2020-11-30




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch







    On the Discretized Dubins Travelling Salesman Problem

    Epstein, C. / Cohen, I. / Shima, T. et al. | British Library Conference Proceedings | 2014


    Intuitionistic Fuzzy Modeling to Travelling Salesman Problem

    Garai, Arindam / Roy, Tapan Kumar | BASE | 2013

    Freier Zugriff