Highlights We study the single-path service network design problem with resource constraints. We present two mathematical formulations: node-arc model and arc-cycle model. We present a column-generation-based two-stage approach. Computational results demonstrate effectiveness and efficiency of our method.

    Abstract We study a new service network design problem, where the number of available resources at each terminal is limited, and each commodity is delivered along a single path that prevents flow partition. Such a single-path constraint is motivated by currently emerging requirements in bulk transportation, express delivery, hazardous material transportation, etc. We model this problem with two mathematical formulations, i.e., node-arc and arc-cycle formulations, both of which lead to large-scale and computationally difficult mixed-integer programs. The node-arc formulation faces a significant computation burden. To that end, we develop a two-stage mathematical integer programming based heuristic for the arc-cycle formulation to produce high-quality solutions. In the first stage, a column generation procedure is executed to generate an optimal solution for the linear relaxation of the restricted master problem, and in the second stage, four heuristic strategies are designed to efficiently generate integer feasible solutions for the original problem. We conduct extensive experiments to verify the effectiveness of our proposed approach by comparing it with a commercial solver (CPLEX). We also examine the performance differences among four heuristic strategies, in terms of the frequency of finding integer feasible solutions and the quality of solutions.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Single-path service network design problem with resource constraints


    Beteiligte:
    Li, Xiangyong (Autor:in) / Ding, Yi (Autor:in) / Pan, Kai (Autor:in) / Jiang, Dapei (Autor:in) / Aneja, Y.P. (Autor:in)


    Erscheinungsdatum :

    2020-04-12




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Service Network Design with Resource Constraints

    Crainic, Teodor Gabriel / Hewitt, Mike / Toulouse, Michel et al. | British Library Online Contents | 2016


    Service Network Design with Resource Constraints

    Crainic, Teodor Gabriel | Online Contents | 2016



    An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints

    Lozano, Leonardo / Duque, Daniel / Medaglia, Andrés L. | British Library Online Contents | 2016