The capacitated-vehicle routing problem (CVRP) is a classical problem that has been well studied by the transportation science community. A special case of the CVRP in which the network is constrained to have a tree structure (TCVRP) is studied here. Such tree networks arise when the cost of constructing and maintaining roads 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 new variant of the TCVRP, in which the customers are divided into two subsets—line haul and backhaul customers (TCVRPB)—is introduced in this paper. Line haul customers require delivery from the depot, and backhaul customers have supply that needs to be delivered to the depot. In any vehicle tour, line haul customers must be serviced before backhaul customers. The TCVRPB's relationship to the two-dimensional bin-packing problem is studied and, with the use of that problem, conditions for the lower bound on the problem are derived. An integer-programming (IP) formulation of the problem is presented. A two-approximation algorithm, which gives a feasible set of vehicle routes and customer assignments, is also presented. The problem is tested on two real-world treelike networks of varying sizes and on a randomly generated test network. The IP formulation works exceptionally well on small and medium-sized networks, and the gap between the approximation algorithm and the IP solution did not exceed 2% for nine of the 12 problem instances tested.


    Zugriff

    Download

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Capacitated-Vehicle Routing Problem with Backhauls on Trees


    Untertitel :

    Model, Properties, Formulation, and Algorithm


    Weitere Titelangaben:

    Transportation Research Record


    Beteiligte:


    Erscheinungsdatum :

    2011-01-01




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Genetic Algorithm for Vehicle Routing Problem with Backhauls

    WA, W.Nurfahizul Ifwah. / Shaiful, M. / Shamsunarnie, M.Z et al. | BASE | 2012

    Freier Zugriff

    A Heuristic Algorithm for the Vehicle Routing Problem with Backhauls

    Toth, P. / Vigo, D. / Italian National Research Council; Progetto Finalizzato Transporti et al. | British Library Conference Proceedings | 1996



    An Exact Algorithm for the Vehicle Routing Problem with Backhauls

    Toth, P. / Vigo, D. | British Library Online Contents | 1997