A generalized Benders decomposition approach for the mean-standard deviation shortest path problem

References

• Babaei, M., M. Rajabi-Bahaabadi, and A. Shariat-Mohaymany. 2016. “Estimation of Travel Time Reliability in large-scale Networks.” Transportation Letters 8: 229–240. doi:10.1080/19427867.2015.1122141.
   Web of Science ®Google Scholar
• Benders, J. F. 1962. “Partitioning Procedures for Solving mixed-variables Programming Problems.” Numerische Mathematik 4: 238–252. doi:10.1007/BF01386316.
   Google Scholar
• Chen, B. Y., W. H. K. Lam, and Q. Li. 2016a. “Efficient Solution Algorithm for Finding Spatially Dependent Reliable Shortest Path in Road Networks.” Journal of Advanced Transportation 50: 1413–1431. doi:10.1002/atr.1408.
   Web of Science ®Google Scholar
• Chen, B. Y., Q. Li, and W. H. K. Lam. 2016b. “Finding the K Reliable Shortest Paths under Travel Time Uncertainty.” Transportation Research Part B: Methodological 94: 189–203. doi:10.1016/j.trb.2016.09.013.
   Web of Science ®Google Scholar
• Chen, B. Y., C. Shi, J. Zhang, W. H. K. Lam, Q. Li, and S. Xiang. 2016c. “Most Reliable path-finding Algorithm for Maximizing on-time Arrival Probability.” Transportmetrica B: Transport Dynamics 5: 248–264.
   Web of Science ®Google Scholar
• Chen, P., R. Tong, B. Yu, and Y. Wang. 2020. “Reliable Shortest Path Finding in Stochastic time-dependent Road Network with spatial-temporal Link Correlations: A Case Study from Beijing.” In Expert Syst Appl, 147.
   Google Scholar
• Fischetti, M., I. Ljubić, and M. Sinnl. 2017. “Redesigning Benders Decomposition for Large-Scale Facility Location.” Management Science 63: 2146–2162. doi:10.1287/mnsc.2016.2461.
   Web of Science ®Google Scholar
• Fisher, M. L. 1981. “The Lagrangian Relaxation Method for Solving Integer Programming Problems.” Management Science 27: 1–18. doi:10.1287/mnsc.27.1.1.
   Web of Science ®Google Scholar
• Geoffrion, A. M. 1972. “Generalized Benders Decomposition.” Journal of Optimization Theory and Applications 10: 237–260. doi:10.1007/BF00934810.
   Google Scholar
• Guo, H., X. Hou, Z. Cao, and J. Zhang. 2021a. “GP3: Gaussian Process Path Planning for Reliable Shortest Path in Transportation Networks.” IEEE Transactions on Intelligent Transportation Systems, no. 1–16: 1–16. doi:10.1109/TITS.2021.3105415.
   Google Scholar
• Guo, H., X. Hou, and Q. Peng. 2021b. “CTD: Cascaded Temporal Difference Learning for the Mean-Standard Deviation Shortest Path Problem.” IEEE Transactions on Intelligent Transportation Systems 1–19.
   Web of Science ®Google Scholar
• Handler, G. Y., and I. Zang. 1980. “A Dual Algorithm for the Constrained Shortest Path Problem.” 10: 293–309.
   Google Scholar
• Hoang, H. 1982. “Topological Optimization of Networks: A Nonlinear Mixed Integer Model Employing Generalized Benders Decomposition.” IEEE Transactions on Automatic Control 27: 164–169. doi:10.1109/TAC.1982.1102873.
   Web of Science ®Google Scholar
• Ilog, I., 2009. “IBM ILOG CPLEX V12.1: User’s Manual for CPLEX.”
   Google Scholar
• Khani, A., and S. D. Boyles. 2015. “An Exact Algorithm for the mean–standard Deviation Shortest Path Problem.” Transport Res B-Meth 81: 252–266. doi:10.1016/j.trb.2015.04.002.
   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. doi:10.1007/s10288-009-0097-9.
   Google Scholar
• Lee, J., S. Joung, and K. Lee. 2022. “A Fully Polynomial Time Approximation Scheme for the Probability Maximizing Shortest Path Problem.” European Journal of Operational Research 300: 35–45. doi:10.1016/j.ejor.2021.10.018.
   Web of Science ®Google Scholar
• Loustau, P., C. Morency, M. Trépanier, and L. Gourvil. 2013. “Travel Time Reliability on a Highway Network: Estimations Using Floating Car Data.” Transportation Letters 2: 27–37. doi:10.3328/TL.2010.02.01.27-37.
   Google Scholar
• Mahey, P., A. Benchakroun, and F. Boyer. 2001. “Capacity and Flow Assignment of Data Networks by Generalized Benders Decomposition.” Journal of Global Optimization 20: 169–189. doi:10.1023/A:1011280023547.
   Web of Science ®Google Scholar
• Nikfarjam, A., and A. Moosavi. 2020. “An Integrated (1, T) Inventory Policy and Vehicle Routing Problem under Uncertainty: An Accelerated Benders Decomposition Algorithm.” Transportation Letters 13: 104–124. doi:10.1080/19427867.2020.1714843.
   Web of Science ®Google Scholar
• Optimization, I.G. 2014. “Gurobi Optimizer Reference Manual.”
   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: 801–817. doi:10.1016/j.ejor.2016.12.005.
   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
• Shen, L., H. Shao, T. Wu, E. Z. Fainman, and W. H. K. Lam. 2020. “Finding the Reliable Shortest Path with Correlated Link Travel Times in Signalized Traffic Networks under Uncertainty.” In Transportation Research Part E: Logistics and Transportation Review, 144.
   Google Scholar
• Shen, Z.-J. M., C. Coullard, and M. S. Daskin. 2003. “A Joint Location-Inventory Model.” Transportation Science 37: 40–55. doi:10.1287/trsc.37.1.40.12823.
   Web of Science ®Google Scholar
• Sivakumar, R. A., and R. Batta. 1994. “The Variance-Constrained Shortest Path Problem.” In 28, 309–316.
   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. “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
• Taylor, M. A. P. 2013. “Travel through Time: The Story of Research on Travel Time Reliability.” Transportmetrica B: Transport Dynamics 1: 174–194.
   Web of Science ®Google Scholar
• Tu, Q., L. Cheng, T. Yuan, Y. Cheng, and M. Li. 2020. “The Constrained Reliable Shortest Path Problem for Electric Vehicles in the Urban Transportation Network.” In J Clean Prod, 261.
   Google Scholar
• Wang, Z., K. You, S. Song, and Y. Zhang. 2020. “Wasserstein Distributionally Robust Shortest Path Problem.” European Journal of Operational Research 284: 31–43. doi:10.1016/j.ejor.2020.01.009.
   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: 1660–1679. doi:10.1016/j.trb.2011.06.004.
   Web of Science ®Google Scholar
• Yang, L. X., and X. S. Zhou. 2017. “Optimizing on-time Arrival Probability and Percentile Travel Time for Elementary Path Finding in time-dependent Transportation Networks: Linear Mixed Integer Programming Reformulations.” Transportation Research Part B: Methodological 96: 68–91. doi:10.1016/j.trb.2016.11.012.
   Web of Science ®Google Scholar
• Zeng, W., T. Miwa, Y. Wakita, and T. Morikawa. 2015. “Application of Lagrangian Relaxation Approach to α -reliable Path Finding in Stochastic Networks with Correlated Link Travel Times.” Transportation Research Part C: Emerging Technologies 56: 309–334. doi:10.1016/j.trc.2015.04.018.
   Web of Science ®Google Scholar
• Zhang, Y., and A. Khani. 2019. “An Algorithm for Reliable Shortest Path Problem with Travel Time Correlations.” Transportation Research Part B: Methodological 121: 92–113. doi:10.1016/j.trb.2018.12.011.
   Web of Science ®Google Scholar
• Zhang, Y., Z.-J. Max Shen, and S. Song. 2017. “Lagrangian Relaxation for the Reliable Shortest Path Problem with Correlated Link Travel Times.” Transportation Research Part B: Methodological 104: 501–521. doi:10.1016/j.trb.2017.04.006.
   Web of Science ®Google Scholar