期刊
TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW
卷 140, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.tre.2020.101945
关键词
Transportation; Service network design; Single-path constraints; Resource constraints; Column generation heuristic
类别
资金
- Natural Science Foundation of China [71672126, 71532015]
- Shanghai Education Development Foundation
- Shanghai Municipal Education Commission [18SG23]
- Research Grants Council of Hong Kong [PolyU 155077/18B]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据