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.
Single-path service network design problem with resource constraints
2020-04-12
Article (Journal)
Electronic Resource
English
Service Network Design with Resource Constraints
British Library Online Contents | 2016
|Service Network Design with Resource Constraints
Online Contents | 2016
|An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints
Online Contents | 2016
|An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints
British Library Online Contents | 2016
|AIRLINE NETWORK DESIGN PROBLEM WITH DIFFERENT AIRPORT CAPACITY CONSTRAINTS
Taylor & Francis Verlag | 2008
|