Single-path service network design problem with resource constraints

Xiangyong Li, Yi Ding, Kai Pan, Dapei Jiang, Y. P. Aneja

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Article number101945
JournalTransportation Research Part E: Logistics and Transportation Review
Volume140
DOIs
Publication statusPublished - Aug 2020

Keywords

  • Column generation heuristic
  • Resource constraints
  • Service network design
  • Single-path constraints
  • Transportation

ASJC Scopus subject areas

  • Business and International Management
  • Civil and Structural Engineering
  • Transportation

Cite this