Incorporating travel time means and standard deviations into transportation network design problem: a hybrid method based on column generation and Lagrangian relaxation

References

• Chen, L., M. Gendreau, M. H. Hà, and A. Langevin. 2016. “A Robust Optimization Approach for the Road Network Daily Maintenance Routing Problem with Uncertain Service Time.” Transportation Research Part E: Logistics and Transportation Review 85: 40–51. doi:10.1016/j.tre.2015.11.006.
   Web of Science ®Google Scholar
• Chow, J. Y. J., and A. C. Regan. 2011. “Network-based Real Option Models.” Transportation Research Part B: Methodological 45 (4): 682–695. doi:10.1016/j.trb.2010.11.005.
   Web of Science ®Google Scholar
• Deng, W., H. Ni, Y. Liu, H. Chen, and H. Zhao. 2022a. “An Adaptive Differential Evolution Algorithm Based on Belief Space and Generalized opposition-based Learning for Resource Allocation.” Applied Soft Computing 127: 109419. doi:10.1016/j.asoc.2022.109419.
   Web of Science ®Google Scholar
• Deng, W., J. Xu, X.-Z. Gao, and H. Zhao. 2022b. “An Enhanced MSIQDE Algorithm with Novel Multiple Strategies for Global Optimization Problems.” IEEE Transactions on Systems, Man, and Cybernetics: Systems 52 (3): 1578–1587. doi:10.1109/TSMC.2020.3030792.
   Web of Science ®Google Scholar
• Deng, W., L. Zhang, X. Zhou, Y. Zhou, Y. Sun, W. Zhu, H. Chen, W. Deng, H. Chen, and H. Zhao. 2022c. “Multi-strategy Particle Swarm and Ant Colony Hybrid Optimization for Airport Taxiway Planning Problem.” Information Sciences 612: 576–593. doi:10.1016/j.ins.2022.08.115.
   Web of Science ®Google Scholar
• Desaulniers, G., J. Desrosiers, and M. M. Solomon. 2005. Column Generation. Springer.
   Google Scholar
• Erbeyoğlu, G., and Ü. Bilge. 2020. “A Robust Disaster Preparedness Model for Effective and Fair Disaster Response.” European Journal of Operational Research 280 (2): 479–494. doi:10.1016/j.ejor.2019.07.029.
   Web of Science ®Google Scholar
• Fragkos, I., J.-F. Cordeau, and R. Jans. 2021. “Decomposition Methods for large-scale Network Expansion Problems.” Transportation Research Part B: Methodological 144: 60–80. doi:10.1016/j.trb.2020.12.002.
   Web of Science ®Google Scholar
• Frangioni, A., and B. Gendron. 2012. “A Stabilized Structured Dantzig–Wolfe Decomposition Method.” Mathematical Programming 140 (1): 45–76. doi:10.1007/s10107-012-0626-8.
   Web of Science ®Google Scholar
• Guimaraes, L. R., J. P. de Sousa, and B. D. Prata. 2022. “Variable Fixing Heuristics for the Capacitated Multicommodity Network Flow Problem with Multiple Transport Lines, a Heterogeneous Fleet and Time Windows.” Transportation Letters-the International Journal of Transportation Research 14: 84–93.
   Web of Science ®Google Scholar
• Holmberg, K., and J. Hellstrand. 1998. “Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound.” Operations Research 46 (2): 247–259. doi:10.1287/opre.46.2.247.
   Web of Science ®Google Scholar
• Holmberg, K., and D. Yuan. 2000. “A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem.” Operations Research 48 (3): 461–481. doi:10.1287/opre.48.3.461.12439.
   Web of Science ®Google Scholar
• Hulagu, S., and H. B. Celikoglu. 2022a. “Electric Vehicle Location Routing Problem with Vehicle Motion Dynamics-Based Energy Consumption and Recovery.” IEEE Transactions on Intelligent Transportation Systems 23 (8): 10275–10286. doi:10.1109/TITS.2021.3089675.
   Web of Science ®Google Scholar
• Hulagu, S., and H. B. Celikoglu. 2022b. “An Electric Vehicle Routing Problem with Intermediate Nodes for Shuttle Fleets.” IEEE Transactions on Intelligent Transportation Systems 23 (2): 1223–1235. doi:10.1109/TITS.2020.3023673.
   Web of Science ®Google Scholar
• Jin, J. G., J. Zhao, and D.-H. Lee. 2013. “A Column Generation Based Approach for the Train Network Design Optimization Problem.” Transportation Research Part E: Logistics and Transportation Review 50: 1–17. doi:10.1016/j.tre.2012.11.004.
   Web of Science ®Google Scholar
• Khani, A., and S. D. Boyles. 2015. “An Exact Algorithm for the mean–standard Deviation Shortest Path Problem.” Transportation Research Part B: Methodological 81: 252–266. doi:10.1016/j.trb.2015.04.002.
   Web of Science ®Google Scholar
• Lan, Z., S. He, and Y. Xu. 2020. “Combining Benders Decomposition and Column Generation for Scheduled Service Network Design Problem in Rail Freight Transportation.” Transportmetrica A: Transport Science 17 (4): 1382–1404. doi:10.1080/23249935.2020.1863505.
   Web of Science ®Google Scholar
• Lecluyse, C., T. Van Woensel, and H. Peremans. 2009. “Vehicle Routing with Stochastic time-dependent Travel Times.” 4OR 7: 363–377.
   Google Scholar
• Li, X., Y. Ding, K. Pan, D. Jiang, and Y. P. Aneja. 2020. “Single-path Service Network Design Problem with Resource Constraints.” Transportation Research Part E: Logistics and Transportation Review 140: 101945. doi:10.1016/j.tre.2020.101945.
   Web of Science ®Google Scholar
• Lin, H. Z. 2022. “Responsive Transport Network Design: Minimal Investment for Desired Travel Time Reduction.” Transportation Letters-the International Journal of Transportation Research 14: 651–659.
   Web of Science ®Google Scholar
• Li, M., X. Zhou, and N. M. Rouphail. 2016. “Quantifying Travel Time Variability at a Single Bottleneck Based on Stochastic Capacity and Demand Distributions.” Journal of Intelligent Transportation Systems 21 (2): 79–93. doi:10.1080/15472450.2016.1163639.
   Web of Science ®Google Scholar
• Lübbecke, M. E., and J. Desrosiers. 2005. “Selected Topics in Column Generation.” Operations Research 53 (6): 1007–1023. doi:10.1287/opre.1050.0234.
   Web of Science ®Google Scholar
• MirHassani, S. A., A. Khaleghi, and F. Hooshmand. 2020. “Two-stage Stochastic Programming Model to Locate Capacitated EV-charging Stations in Urban Areas under Demand Uncertainty.” Euro Journal on Transportation and Logistics 9 (4): 100025. doi:10.1016/j.ejtl.2020.100025.
   Web of Science ®Google Scholar
• Murty, K. G. J. M. P. 1980. “Computational Complexity of Parametric Linear Programming.“ Mathematical Programming 19: 213–219.
   Web of Science ®Google Scholar
• Ng, M., and D.-Y. Lin. 2015. “Sharp Probability Inequalities for Reliable Evacuation Planning.” Transportation Research Part C: Emerging Technologies 60: 161–168. doi:10.1016/j.trc.2015.08.003.
   Web of Science ®Google Scholar
• Nikolić, M., and D. Teodorović. 2013. “Transit Network Design by Bee Colony Optimization.” Expert Systems with Applications 40 (15): 5945–5955. doi:10.1016/j.eswa.2013.05.002.
   Web of Science ®Google Scholar
• Nikolić, M., and D. Teodorović. 2014. “A Simultaneous Transit Network Design and Frequency Setting: Computing with Bees.” Expert Systems with Applications 41 (16): 7200–7209. doi:10.1016/j.eswa.2014.05.034.
   Web of Science ®Google Scholar
• Noyan, N. 2012. “Risk-averse two-stage Stochastic Programming with an Application to Disaster Management.” Computers & Operations Research 39 (3): 541–559. doi:10.1016/j.cor.2011.03.017.
   Web of Science ®Google Scholar
• Noyan, N., B. Balcik, and S. Atakan. 2016. “A Stochastic Optimization Model for Designing Last Mile Relief Networks.” Transportation Science 50 (3): 1092–1113. doi:10.1287/trsc.2015.0621.
   Web of Science ®Google Scholar
• Noyan, N., M. Meraklı, and S. Küçükyavuz. 2019. Two-stage Stochastic Programming under Multivariate Risk Constraints with an Application to Humanitarian Relief Network Design. .
   Google Scholar
• Powell, W. B., and H. Topaloglu. 2003. Stochastic Programming. Elsevier. 555–635.
   Google Scholar
• Rahmaniani, R., T. G. Crainic, M. Gendreau, and W. Rei. 2017. “The Benders Decomposition Algorithm: A Literature Review.” European Journal of Operational Research 259 (3): 801–817. doi:10.1016/j.ejor.2016.12.005.
   Web of Science ®Google Scholar
• Rahmani, D., A. Zandi, E. Peyghaleh, and N. Siamakmanesh. 2018. “A Robust Model for A Humanitarian Relief Network with Backup Covering under Disruptions: A Real World Application.” International Journal of Disaster Risk Reduction 28: 56–68. doi:10.1016/j.ijdrr.2018.02.021.
   Web of Science ®Google Scholar
• Sen, S., R. Pillai, S. Joshi, and A. K. Rathi. 2001. “A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems.” Transportation Science 35 (1): 37–49. doi:10.1287/trsc.35.1.37.10141.
   Web of Science ®Google Scholar
• Shahabi, M., A. Unnikrishnan, and S. D. Boyles. 2013. “An Outer Approximation Algorithm for the Robust Shortest Path Problem.” Transportation Research Part E: Logistics and Transportation Review 58: 52–66. doi:10.1016/j.tre.2013.07.002.
   Web of Science ®Google Scholar
• Song, Y., X. Cai, X. Zhou, B. Zhang, H. Chen, Y. Li, W. Deng, and W. Deng. 2023. “Dynamic Hybrid mechanism-based Differential Evolution Algorithm and Its Application.” Expert Systems with Applications 213: 118834. doi:10.1016/j.eswa.2022.118834.
   Web of Science ®Google Scholar
• Song, M., and L. Cheng. 2022a. “An Augmented Lagrangian Relaxation Method for the mean-standard Deviation Based Vehicle Routing Problem.” Knowledge-Based Systems 247: 108736. doi:10.1016/j.knosys.2022.108736.
   Web of Science ®Google Scholar
• Song, M., and L. Cheng, 2022b. “A Generalized Benders Decomposition Approach for the mean-standard Deviation Shortest Path Problem.” Transportation Letters, 1–11.
   Google Scholar
• Song, M., and L. Cheng. 2022c. “Solving the reliability-oriented Generalized Assignment Problem by Lagrangian Relaxation and Alternating Direction Method of Multipliers.” Expert Systems with Applications 205: 117644. doi:10.1016/j.eswa.2022.117644.
   Web of Science ®Google Scholar
• Sun, H., J. Yang, and C. Yang. 2019. “A Robust Optimization Approach to multi-interval location-inventory and Recharging Planning for Electric Vehicles.” Omega-International Journal of Management Science 86: 59–75. doi:10.1016/j.omega.2018.06.013.
   Web of Science ®Google Scholar
• Tong, L., X. S. Zhou, and H. J. Miller. 2015. “Transportation Network Design for Maximizing space-time Accessibility.” Transportation Research Part B: Methodological 81: 555–576. doi:10.1016/j.trb.2015.08.002.
   Web of Science ®Google Scholar
• Ukkusuri, S. V., and G. Patil. 2009. “Multi-period Transportation Network Design under Demand Uncertainty.” Transportation Research Part B: Methodological 43 (6): 625–642. doi:10.1016/j.trb.2009.01.004.
   Web of Science ®Google Scholar
• Veluscek, M., T. Kalganova, P. Broomhead, and A. Grichnik. 2015. “Composite Goal Methods for Transportation Network Optimization.” Expert Systems with Applications 42 (8): 3852–3867. doi:10.1016/j.eswa.2014.12.017.
   Web of Science ®Google Scholar
• Xing, T., and X. S. Zhou. 2011. “Finding the Most Reliable Path with and without Link Travel Time Correlation: A Lagrangian Substitution Based Approach.” Transportation Research Part B: Methodological 45 (10): 1660–1679. doi:10.1016/j.trb.2011.06.004.
   Web of Science ®Google Scholar
• Xu, T., H. Wei, and G. Hu. 2009. “Study on Continuous Network Design Problem Using Simulated Annealing and Genetic Algorithm.” Expert Systems with Applications 36 (2): 1322–1328. doi:10.1016/j.eswa.2007.11.023.
   Web of Science ®Google Scholar
• Yang, L. X., and X. S. Zhou. 2014. “Constraint Reformulation and a Lagrangian relaxation-based Solution Algorithm for a Least Expected Time Path Problem.” Transportation Research Part B: Methodological 59: 22–44. doi:10.1016/j.trb.2013.10.012.
   Web of Science ®Google Scholar
• Yan, Y., Z. Liu, Q. Meng, and Y. Jiang. 2013. “Robust Optimization Model of Bus Transit Network Design with Stochastic Travel Time.” Journal of Transportation Engineering / American Society of Civil Engineers 139 (6): 625–634. doi:10.1061/(ASCE)TE.1943-5436.0000536.
   Google Scholar
• Yao, B., P. Hu, X. Lu, J. Gao, and M. Zhang. 2014. “Transit Network Design Based on Travel Time Reliability.” Transportation Research Part C: Emerging Technologies 43: 233–248. doi:10.1016/j.trc.2013.12.005.
   Web of Science ®Google Scholar
• Zang, Z., X. Xu, K. Qu, R. Chen, and A. Chen. 2022. “Travel Time Reliability in Transportation Networks: A Review of Methodological Developments.” Transportation Research Part C: Emerging Technologies 143: 103866. doi:10.1016/j.trc.2022.103866.
   Web of Science ®Google Scholar
• Zhang, X. 2017. “Incorporating Travel Time Reliability into Transportation Network Modeling.”
   Google Scholar
• Zhang, X., S. T. Waller, D. Rey, and M. Duell. 2019. “Integrating Uncertainty Considerations into multi-objective Transportation Network Design Projects Accounting for Environment Disruption.” Transportation Letters-the International Journal of Transportation Research 11: 351–361.
   Web of Science ®Google Scholar
• Zhao, H., J. Liu, H. Chen, J. Chen, Y. Li, J. Xu, and W. Deng. 2022. “Intelligent Diagnosis Using Continuous Wavelet Transform and Gauss Convolutional Deep Belief Network.” IEEE Transactions on Reliability 1–11.
   Web of Science ®Google Scholar