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.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:


    Publication date :

    2012-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    A Generalized Assignment Heuristic for Vehicle Routing

    M. L. Fisher / R. Jaikumar | NTIS | 1979


    A generalized assignment heuristic for vehicle routing

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


    The Pallet-Packing Vehicle Routing Problem

    Zachariadis, Emmanouil E. | Online Contents | 2012


    The Pallet-Packing Vehicle Routing Problem

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