TY - JOUR
T1 - A cut-and-solve-based algorithm for optimal lane reservation with dynamic link travel times
AU - Fang, Yunfei
AU - Chu, Feng
AU - Mammar, Saïd
AU - Che, Ada
PY - 2014/2/16
Y1 - 2014/2/16
N2 - This paper investigates an optimal lane reservation problem with dynamic link travel times via a lane reservation strategy. This strategy is to select some existing general-purpose lanes from a transportation network and convert them to reserved lanes for some special road users only so that a time-guaranteed transportation can be ensured. However, such conversion may cause traffic impact such as an increase of link travel times on adjacent lanes due to the disallowing utilisation of reserved lanes by general-purpose vehicles. Thus, the considered problem aims to design reserved lane-based paths for the time-guaranteed transportation with the objective of minimising the total traffic impact caused by the conversion. Different from lane reservation problems with constant link travel times in the literature, the considered problem assumes dynamic link travel times, which is proved NP-hard. The problem is initially formulated as a mixed integer non-linear programming model. In order to solve it, the non-linear model is reformulated as an equivalent linear model and a cut-and-solve-based algorithm is proposed to obtain optimal solutions. Experimental tests on randomly generated instances show that the overall performance of the proposed algorithm outperforms a direct use of a commercial CPLEX MIP solver.
AB - This paper investigates an optimal lane reservation problem with dynamic link travel times via a lane reservation strategy. This strategy is to select some existing general-purpose lanes from a transportation network and convert them to reserved lanes for some special road users only so that a time-guaranteed transportation can be ensured. However, such conversion may cause traffic impact such as an increase of link travel times on adjacent lanes due to the disallowing utilisation of reserved lanes by general-purpose vehicles. Thus, the considered problem aims to design reserved lane-based paths for the time-guaranteed transportation with the objective of minimising the total traffic impact caused by the conversion. Different from lane reservation problems with constant link travel times in the literature, the considered problem assumes dynamic link travel times, which is proved NP-hard. The problem is initially formulated as a mixed integer non-linear programming model. In order to solve it, the non-linear model is reformulated as an equivalent linear model and a cut-and-solve-based algorithm is proposed to obtain optimal solutions. Experimental tests on randomly generated instances show that the overall performance of the proposed algorithm outperforms a direct use of a commercial CPLEX MIP solver.
KW - cut-and-solve method
KW - dynamic link travel times
KW - mixed integer programming model
KW - optimal lane reservation
UR - http://www.scopus.com/inward/record.url?scp=84892913301&partnerID=8YFLogxK
U2 - 10.1080/00207543.2013.828169
DO - 10.1080/00207543.2013.828169
M3 - 文章
AN - SCOPUS:84892913301
SN - 0020-7543
VL - 52
SP - 1003
EP - 1015
JO - International Journal of Production Research
JF - International Journal of Production Research
IS - 4
ER -