Optimal lane reservation in transportation network

Yunfei Fang, Feng Chu, Sad Mammar, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

67 Scopus citations


This work studies a lane reservation problem in a transportation network. It aims to design task paths and optimally select lanes to be reserved in a transportation network. In this problem, each lane has limited residual capacity, which is the lane capacity that can be used for the tasks causing no delay in this lane. If the residual capacity of a lane is not large enough to allow tasks to use it, the reservation of this lane is necessary. Once reserved, the lane can be used by the tasks only. Therefore, the travel time in this reserved lane is less than that when it is not reserved. Such lane reservation strategy ensures that each task can transport the commodity from its source to destination within a given travel time. However, this reserved lane generates traffic impact on nonreserved lanes. The objective of the problem is to minimize the total impact of all reserved lanes on nonreserved lanes subject to the timely completion of all the concerned tasks. In this paper, two integer linear programming models are, for the first time, formulated. The complexity of the problem is demonstrated to be non-deterministic polynomial-time hard. Then, an optimal algorithm based on the cut-and-solve method is developed for the problem. The computational results of randomly generated network instances up to 120 nodes and 468 arcs show that the proposed algorithm significantly outperforms the direct use of an optimization solver of CPLEX.

Original languageEnglish (US)
Article number6099683
Pages (from-to)482-491
Number of pages10
JournalIEEE Transactions on Intelligent Transportation Systems
Issue number2
StatePublished - 2012

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications


  • Cut-and-solve method
  • linear programming
  • optimization
  • traffic control
  • transportation systems


Dive into the research topics of 'Optimal lane reservation in transportation network'. Together they form a unique fingerprint.

Cite this