Highlights We tackle the uncapacitated multiple allocation hub location problem with economies of scale and congestion. An efficient Benders decomposition algorithm is proposed to solve the resulting MIP. The proposed algorithm outperforms CPLEX and is able to solve much larger instances. Computational experiments are presented analyzing the differences between the congested and uncongested problem. Results show that switching from single allocation to multiple allocation yields large cost reductions.

    Abstract This paper is the first to consider a novel and more realistic variant of the uncapacitated hub location problem where both flow-dependent economies of scale and congestion considerations are incorporated into the multiple-allocation version of the problem. Given an undirected graph with edge per-unit costs and flow requirements for a given set of source-destination pairs of nodes, the goal is to decide where to locate hub nodes and then to route flow through these hubs in a way that minimizes total cost. Transportation costs are influenced by two conflicting effects: consolidation discounts on hub-to-hub flow due to economies of scale, and congestion penalties due to excessive demand through hubs. The problem is formulated as a mixed-integer linear program by piecewise-linearizing non-linear cost elements. Since the resulting model is found to be difficult to solve directly using commercial solvers, a specialized Benders decomposition approach is devised to solve the problem. The proposed method is tested on two standard testbeds (the Civil Aeronautics Board and Australian Post datasets). While the commercial solver is unable to obtain any feasible solution for networks larger than 25 nodes, the proposed algorithm is shown to be able to obtain optimal solutions for networks as large as 70 nodes, and is able to obtain small-gap feasible solutions for networks with up to 100 nodes. Whenever both algorithms are able to solve instances to optimality, the Benders algorithm is able to do so in a fraction of the time needed by the commercial solver. The incorporation of congestion costs into the multiple-allocation topology as opposed to the single-allocation one is also found to lead to significant cost savings.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion


    Beteiligte:
    Najy, Waleed (Autor:in) / Diabat, Ali (Autor:in)


    Erscheinungsdatum :

    2019-12-09


    Format / Umfang :

    23 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Benders Decomposition for Hub Location Problems with Economies of Scale

    de Camargo, Ricardo Saraiva | Online Contents | 2009


    Benders Decomposition for Hub Location Problems with Economies of Scale

    de Camargo, R.S. / de Miranda, G. / Luna, H.P.L. | British Library Online Contents | 2009


    Design of Hub-and-Spoke Network Based on Congestion Problems

    Zhang, Zaifang / Lu, Shunlu / Bao, Shengrui | IEEE | 2023


    Hub-and-spoke network design under congestion: A learning based metaheuristic

    Karimi-Mamaghan, Maryam / Mohammadi, Mehrdad / Pirayesh, Amir et al. | Elsevier | 2020