TY - JOUR
T1 - Optimal lane reservation in transportation network
AU - Fang, Yunfei
AU - Chu, Feng
AU - Mammar, Sad
AU - Zhou, Mengchu
N1 - Funding Information:
Manuscript received May 10, 2011; revised August 17, 2011 and September 27, 2011; accepted September 30, 2011. Date of publication December 9, 2011; date of current version May 30, 2012. This work was supported in part by the Cai Yuanpei Program of the French Ministries of Foreign and European Affairs and the Chinese Ministry of Education under Grant 24021SH and in part by the National Natural Science Foundation of China under Grant 61034004. The Associate Editor for this paper was L. Li.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - Cut-and-solve method
KW - linear programming
KW - optimization
KW - traffic control
KW - transportation systems
UR - http://www.scopus.com/inward/record.url?scp=84861863177&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861863177&partnerID=8YFLogxK
U2 - 10.1109/TITS.2011.2171337
DO - 10.1109/TITS.2011.2171337
M3 - Article
AN - SCOPUS:84861863177
SN - 1524-9050
VL - 13
SP - 482
EP - 491
JO - IEEE Transactions on Intelligent Transportation Systems
JF - IEEE Transactions on Intelligent Transportation Systems
IS - 2
M1 - 6099683
ER -