The vehicle routing problem (VRP) is a classical problem in logistics that aims to design minimum-cost delivery routes from a centralized depot. A special case of the VRP arises in situations in which the network has a tree structure (TVRP). Such tree networks arise when the cost of road construction and maintenance is much more than the routing cost or when the transportation network consists of a main highway (e.g., Interstate system) and the customer locations are located off the highway. A heuristic for a constrained case of TVRP in which the vehicle fleet is capacitated and heterogeneous is proposed. The heuristic first determines the customers that will be served by each vehicle by use of bin-packing and Lagrangian-based generalized assignment algorithms. The individual vehicle routes are then determined by use of a depth-first search method. A procedure for further refinement of the heuristic solution quality is also described. The heuristic algorithm was implemented on two real-world networks and on randomly generated networks that varied in size from 20 to 120 nodes. The heuristic solution was found to be between 2% and 10% for almost all of the 200 instances tested and took a fraction of the time taken to find the optimal solution.


    Zugriff

    Download

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Heuristic Scheme for Heterogeneous Vehicle Routing Problem on Trees Based on Generalized Assignment and Bin-Packing Upper Bounds


    Weitere Titelangaben:

    Transportation Research Record


    Beteiligte:


    Erscheinungsdatum :

    2012-01-01




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    A generalized assignment heuristic for vehicle routing

    Fisher, M.L. / Jaikumar, R. | Tema Archiv | 1981


    The Pallet-Packing Vehicle Routing Problem

    Zachariadis, E.E. / Tarantilis, C.D. / Kiranoudis, C.T. | British Library Online Contents | 2012


    The Pallet-Packing Vehicle Routing Problem

    Zachariadis, Emmanouil E. | Online Contents | 2012


    A column generation based heuristic for the generalized vehicle routing problem with time windows

    Yuan, Yuan / Cattaruzza, Diego / Ogier, Maxime et al. | Elsevier | 2021