Optimal Lane Reservation in Transportation Network
- 9 December 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Intelligent Transportation Systems
- Vol. 13 (2), 482-491
- https://doi.org/10.1109/tits.2011.2171337
Abstract
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.Keywords
This publication has 32 references indexed in Scilit:
- An Introduction to Parallel Control and Management for High-Speed Railway SystemsIEEE Transactions on Intelligent Transportation Systems, 2011
- Schedulability Analysis of Short-Term Scheduling for Crude Oil Operations in Refinery With Oil Residency Time and Charging-Tank-Switch-Overlap ConstraintsIEEE Transactions on Automation Science and Engineering, 2010
- Parallel Control and Management for Intelligent Transportation Systems: Concepts, Architectures, and ApplicationsIEEE Transactions on Intelligent Transportation Systems, 2010
- Hybrid Petri Net Modeling and Schedulability Analysis of High Fusion Point Oil Transportation Under Tank Grouping Strategy for Crude Oil Operations in RefineryIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2009
- M–M Role-Transfer Problems and Their SolutionsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2008
- Short-Term Schedulability Analysis of Crude Oil Operations in Refinery With Oil Residency Time Constraint Using Petri NetsIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2008
- Short-Term Schedulability Analysis of Multiple Distiller Crude Oil Operations in Refinery With Oil Residency Time ConstraintIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2008
- Role Transfer Problems and AlgorithmsIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 2008
- Toward a Revolution in Transportation Operations: AI for Complex SystemsIEEE Intelligent Systems, 2008
- Driving into the Future with ITSIEEE Intelligent Systems, 2006