BO-B&amp;B: A hybrid algorithm based on Bayesian optimization and branch-and-bound for discrete network design problems

Ruyang Yin; Jiping Xing; Pengli Mo; Nan Zheng; Zhiyuan Liu; Ruyang Yin; Jiping Xing; Pengli Mo; Nan Zheng; Zhiyuan Liu

doi:10.3934/era.2022203

Electronic Research Archive

2022, Volume 30, Issue 11: 3993-4014. doi: 10.3934/era.2022203

Previous Article Next Article

Research article Special Issues

BO-B&B: A hybrid algorithm based on Bayesian optimization and branch-and-bound for discrete network design problems

1.
Institute of Transport Studies, Department of Civil Engineering, Monash University, Clayton, Victoria, Australia
2.
Jiangsu Key Laboratory of Urban ITS, Jiangsu Province Collaborative Innovation Center of Modern Urban Traffic Technologies, School of Transportation, Southeast University, China

Received: 15 July 2022 Revised: 16 August 2022 Accepted: 24 August 2022 Published: 13 September 2022

A discrete network design problem (DNDP) is conventionally formulated as an analytical bi-level programming problem to acquire an optimal network design strategy for an existing traffic network. In recent years, multimodal network design problems have benefited from simulation-based models. The nonconvexity and implicity of bi-level DNDPs make it challenging to obtain an optimal solution, especially for simulation-related models. Bayesian optimization (BO) has been proven to be an effective method for optimizing the costly black-box functions of simulation-based continuous network design problems. However, there are only discrete inputs in DNDPs, which cannot be processed using standard BO algorithms. To address this issue, we develop a hybrid method (BO-B&B) that combines Bayesian optimization and a branch-and-bound algorithm to deal with discrete variables. The proposed algorithm exploits the advantages of the cutting-edge machine-learning parameter-tuning technique and the exact mathematical optimization method, thereby balancing efficiency and accuracy. Our experimental results show that the proposed method outperforms benchmarking discrete optimization heuristics for simulation-based DNDPs in terms of total computational time. Thus, BO-B&B can potentially aid decision makers in mapping practical network design schemes for large-scale networks.
- Bayesian optimization,
- branch-and-bound,
- discrete network design problem,
- simulation-based optimization
Citation: Ruyang Yin, Jiping Xing, Pengli Mo, Nan Zheng, Zhiyuan Liu. BO-B&B: A hybrid algorithm based on Bayesian optimization and branch-and-bound for discrete network design problems[J]. Electronic Research Archive, 2022, 30(11): 3993-4014. doi: 10.3934/era.2022203

Related Papers:

Abstract

A discrete network design problem (DNDP) is conventionally formulated as an analytical bi-level programming problem to acquire an optimal network design strategy for an existing traffic network. In recent years, multimodal network design problems have benefited from simulation-based models. The nonconvexity and implicity of bi-level DNDPs make it challenging to obtain an optimal solution, especially for simulation-related models. Bayesian optimization (BO) has been proven to be an effective method for optimizing the costly black-box functions of simulation-based continuous network design problems. However, there are only discrete inputs in DNDPs, which cannot be processed using standard BO algorithms. To address this issue, we develop a hybrid method (BO-B&B) that combines Bayesian optimization and a branch-and-bound algorithm to deal with discrete variables. The proposed algorithm exploits the advantages of the cutting-edge machine-learning parameter-tuning technique and the exact mathematical optimization method, thereby balancing efficiency and accuracy. Our experimental results show that the proposed method outperforms benchmarking discrete optimization heuristics for simulation-based DNDPs in terms of total computational time. Thus, BO-B&B can potentially aid decision makers in mapping practical network design schemes for large-scale networks.

References

[1]	R. Z. Farahani, E. Miandoabchi, W. Y. Szeto, H. Rashidi, A review of urban transportation network design problems, Eur. J. Oper. Res., 229 (2013), 281–302. https://doi.org/10.1016/j.ejor.2013.01.001 doi: 10.1016/j.ejor.2013.01.001
[2]	E. Chen, Z. Ye, C. Wang, M. Xu, Subway passenger flow prediction for special events using smart card data, IEEE Trans. Intell. Transp. Syst., 21 (2019), 1109–1120. https://doi.org/10.1109/TITS.2019.2902405 doi: 10.1109/TITS.2019.2902405
[3]	H. Yang, M. G. H. Bell, Models and algorithms for road network design: a review and some new developments, Transp. Rev., 18 (1998), 257–278. https://doi.org/10.1080/01441649808717016 doi: 10.1080/01441649808717016
[4]	S. Wang, Q. Meng, H. Yang, Global optimization methods for the discrete network design problem, Transp. Res. Part B Methodol., 50 (2013), 42–60. https://doi.org/10.1016/j.trb.2013.01.006 doi: 10.1016/j.trb.2013.01.006
[5]	D. Z. Wang, H. Liu, W. Y. Szeto, A novel discrete network design problem formulation and its global optimization solution algorithm, Transp. Res. Part E Logist. Transp. Rev., 79 (2015), 213–230. https://doi.org/10.1016/j.tre.2015.04.005 doi: 10.1016/j.tre.2015.04.005
[6]	G. Wang, Z. Gao, M. Xu, Integrating link-based discrete credit charging scheme into discrete network design problem, Eur. J. Oper. Res., 272 (2019), 176–187. https://doi.org/10.1016/j.ejor.2018.05.069 doi: 10.1016/j.ejor.2018.05.069
[7]	D. Huang, J. Xing, Z. Liu, Q. An, A multi-stage stochastic optimization approach to the stop-skipping and bus lane reservation schemes, Transportmetrica A: Transp. Sci., 17 (2021), 1272–1304. https://doi.org/10.1080/23249935.2020.1858206 doi: 10.1080/23249935.2020.1858206
[8]	D. Huang, Y. Wang, S. Jia, Z. Liu, S. Wang, A Lagrangian relaxation approach for the electric bus charging scheduling optimization problem, Transportmetrica A: Transp. Sci., 2022 (2022), 1–24. https://doi.org/10.1080/23249935.2021.2023690
[9]	L. J. Leblanc, An algorithm for the discrete network design problem, Transp. Sci., 9 (1975), 183–199. https://doi.org/10.1287/trsc.9.3.183 doi: 10.1287/trsc.9.3.183
[10]	Q. Cheng, Y. Chen, Z. Liu, A bi-level programming model for the optimal lane reservation problem, Expert Syst. Appl., 189 (2022), 116147. https://doi.org/10.1016/j.eswa.2021.116147 doi: 10.1016/j.eswa.2021.116147
[11]	S. A. Bagloee, M. Sarvi, M. Patriksson, A hybrid branch-and-bound and benders decomposition algorithm for the network design problem, Comput. Aided Civ. Infrastruct. Eng., 32 (2017), 319–343. https://doi.org/10.1111/mice.12224 doi: 10.1111/mice.12224
[12]	Q. Cheng, Z. Liu, Y. Lin, X. S. Zhou, An s-shaped three-parameter (S3) traffic stream model with consistent car following relationship, Transp. Res. Part B Methodol., 153 (2021), 246–271. https://doi.org/10.1016/j.trb.2021.09.004 doi: 10.1016/j.trb.2021.09.004
[13]	Q. Cheng, Z. Liu, W. Y. Szeto, A cell-based dynamic congestion pricing scheme considering travel distance and time delay, Transportmetrica B: Transp. Dyn., 7 (2019), 1286–1304. https://doi.org/10.1080/21680566.2019.1602487 doi: 10.1080/21680566.2019.1602487
[14]	Q. Cheng, Z. Liu, J. Guo, X. Wu, R. Pendyala, B. Belezamo, et al., Estimating key traffic state parameters through parsimonious spatial queue models, Transp. Res. Part C Emerging Technol., 137 (2022), 103596. https://doi.org/10.1016/j.trc.2022.103596
[15]	C. Iliopoulou, K. Kepaptsoglou, E. Vlahogianni, Metaheuristics for the transit route network design problem: a review and comparative analysis, Public Transp., 11 (2019), 487–521. https://doi.org/10.1007/s12469-019-00211-2 doi: 10.1007/s12469-019-00211-2
[16]	H. Poorzahedy, O. M. Rouhani, Hybrid meta-heuristic algorithms for solving network design problem, Eur. J. Oper. Res., 182 (2007), 578–596. https://doi.org/10.1016/j.ejor.2006.07.038 doi: 10.1016/j.ejor.2006.07.038
[17]	L. Ahmed, C. Mumford, A. Kheiri, Solving urban transit route design problem using selection hyper-heuristics, Eur. J. Oper. Res., 274(2019), 545–559. https://doi.org/10.1016/j.ejor.2018.10.022 doi: 10.1016/j.ejor.2018.10.022
[18]	Y. Shi, Z. Liu, Z. Wang, J. Ye, W. Tong, Z. Liu, An integrated traffic and vehicle co-simulation testing framework for connected and autonomous vehicles, IEEE Intell. Transp. Syst. Mag., 2022 (2022), 2–15. https://doi.org/10.1109/MITS.2022.3188566 doi: 10.1109/MITS.2022.3188566
[19]	P. I. Frazier, A tutorial on Bayesian optimization, preprint, arXiv: 1807.02811.
[20]	L. Du, R. Gao, P. N. Suganthan, D. Z. Wang, Bayesian optimization based dynamic ensemble for time series forecasting, Inf. Sci., 591 (2022), 155–175. https://doi.org/10.1016/j.ins.2022.01.010 doi: 10.1016/j.ins.2022.01.010
[21]	R. Yin, Z. Liu, N. Zheng, A simulation-based model for continuous network design problem using Bayesian optimization, IEEE Trans. Intell. Transp. Syst., 2022 (2022), 1–16. https://doi.org/10.1109/TITS.2022.3176918
[22]	L. Yang, Z. Di, M. M. Dessouky, Z. Gao, J. Shi, Collaborative optimization of last-train timetables with accessibility: A space-time network design based approach, Transp. Res. Part C Emerging Technol., 114 (2020), 572–597. https://doi.org/10.1016/j.trc.2020.02.022 doi: 10.1016/j.trc.2020.02.022
[23]	Z. Gao, J. Wu, H. Sun, Solution algorithm for the bi-level discrete network design problem, Transp. Res. Part B Methodol., 39 (2005), 479–495. https://doi.org/10.1016/j.trb.2004.06.004 doi: 10.1016/j.trb.2004.06.004
[24]	H. Poorzahedy, M. A. Turnquist, Approximate algorithms for the discrete network design problem, Transp. Res. Part B Methodol., 16 (1982), 45–55. https://doi.org/10.1016/0191-2615(82)90040-6 doi: 10.1016/0191-2615(82)90040-6
[25]	H. Farvaresh, M. M. Sepehri, A branch and bound algorithm for bi-level discrete network design problem, Netw. Spat. Econ., 13 (2013), 67–106. https://doi.org/10.1007/s11067-012-9173-3 doi: 10.1007/s11067-012-9173-3
[26]	P. Luathep, A. Sumalee, W. H. Lam, Z. C. Li, H. K. Lo, Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach, Transp. Res. Part B Methodol., 45 (2011), 808–827. https://doi.org/10.1016/j.trb.2011.02.002 doi: 10.1016/j.trb.2011.02.002
[27]	H. Farvaresh, M. M. Sepehri, A single-level mixed integer linear formulation for a bi-level discrete network design problem, Transp. Res. Part E Logist. Transp. Rev., 47 (2011), 623–40. https://doi.org/10.1016/j.tre.2011.02.001 doi: 10.1016/j.tre.2011.02.001
[28]	L. Zhang, H. Yang, D. Wu, D. Wang, Solving a discrete multimodal transportation network design problem, Transp. Res. Part C Emerging Technol., 49 (2014), 73–86. https://doi.org/10.1016/j.trc.2014.10.008 doi: 10.1016/j.trc.2014.10.008
[29]	P. Fontaine, S. Minner, Benders decomposition for discrete-continuous linear bilevel problems with application to traffic network design, Transp. Res. Part B Methodol., 70 (2014), 163–172. https://doi.org/10.1016/j.trb.2014.09.007 doi: 10.1016/j.trb.2014.09.007
[30]	P. Fontaine, S. Minner, A dynamic discrete network design problem for maintenance planning in traffic networks, Ann. Oper. Res., 253 (2017), 757–772. https://doi.org/10.1007/s10479-016-2171-y doi: 10.1007/s10479-016-2171-y
[31]	S. Ding, Z. Wang, J. Zhang, F. Han, X. Gu, Time delay system identification using controlled recurrent neural network and discrete Bayesian optimization, Appl. Intell., 52 (2022), 8351–8371. https://doi.org/10.1007/s10489-021-02823-3 doi: 10.1007/s10489-021-02823-3
[32]	E. C. Garrido-Merchán, D. Hernández-Lobato, Dealing with categorical and integer-valued variables in Bayesian optimization with gaussian processes, Neurocomputing, 380 (2020), 20–35. https://doi.org/10.1016/j.neucom.2019.11.004
[33]	P. Luong, S. Gupta, D. Nguyen, S. Rana, S. Venkatesh, Bayesian optimization with discrete variables, in Australasian Joint Conference on Artificial Intelligence, Springer, Cham, (2019), 473–484. https://doi.org/10.1007/978-3-030-35288-2_38
[34]	F. Hutter, H. H. Hoos, K. Leyton-Brown, Sequential model-based optimization for general algorithm configuration, in International conference on learning and intelligent optimization, Springer, Berlin, Heidelberg, (2011), 507–523. https://doi.org/10.1007/978-3-642-25566-3_40
[35]	B. Lakshminarayanan, D. M. Roy, Y. W. Teh, Mondrian forests for large-scale regression when uncertainty matters, preprint, arXiv: 1506.03805.
[36]	J. Bergstra, D. Yamins, D. D. Cox, Hyperopt: A python library for optimizing the hyperparameters of machine learning algorithms, in Proceedings of the 12th Python in science conference, (2013), 1-8. https://doi.org/10.25080/MAJORA-8B375195-003
[37]	D. E. Boyce, Urban transportation network-equilibrium and design models: recent achievements and future prospects, Environ. Plann. A: Econ. Space, 16 (1984), 1445–1474. https://doi.org/10.1068/a161445 doi: 10.1068/a161445
[38]	T. L. Magnanti, R. T. Wong, Network design and transportation planning: models and algorithms, Transp. Sci., 18 (1984), 1–55. https://doi.org/10.1287/trsc.18.1.1 doi: 10.1287/trsc.18.1.1
[39]	J. Huo, X. Wu, C. Lyu, W. Zhang, Z. Liu, Quantify the road link performance and capacity using deep learning models, IEEE Trans. Intell. Transp. Syst., 2022 (2022), 1–11. https://doi.org/10.1109/TITS.2022.3153397 doi: 10.1109/TITS.2022.3153397
[40]	Z. Chen, X. Li, X. Qu, A continuous model for designing corridor systems with modular autonomous vehicles enabling station-wise docking, Transp. Sci., 56 (2021), 1–30. https://doi.org/10.1287/trsc.2021.1085 doi: 10.1287/trsc.2021.1085
[41]	Z. Liu, C. Lyu, J. Huo, S. Wang, J. Chen, Gaussian process regression for transportation system estimation and prediction problems: the Deformation and a Hat Kernel, IEEE Trans. Intell. Transp. Syst., 2022 (2022), 1–12. https://doi.org/10.1109/TITS.2022.3155527 doi: 10.1109/TITS.2022.3155527
[42]	Y. Liu, F. Wu, C. Lyu, S. Li, J. Ye, X. Qu, Deep dispatching: A deep reinforcement learning approach for vehicle dispatching on online ride-hailing platform, Transp. Res. Part E Logist. Transp. Rev., 161 (2022), 102694. https://doi.org/10.1016/j.tre.2022.102694 doi: 10.1016/j.tre.2022.102694
[43]	Y. Liu, R. Jia, J. Ye, X. Qu, How machine learning informs ride-hailing services: A survey, Commun. Transp. Res., 2 (2022), 100075. https://doi.org/10.1016/j.commtr.2022.100075 doi: 10.1016/j.commtr.2022.100075
[44]	C. Rasmussen, C. Williams, Gaussian Processes for Machine Learning, MIT Press, Cambridge, MA, USA, 2006. https://doi.org/10.7551/mitpress/3206.001.0001
[45]	T. Pourmohamad, H. K. Lee, Bayesian optimization via barrier functions, J. Comput. Graphical Stat., 31 (2022), 74–83. https://doi.org/10.1080/10618600.2021.1935270 doi: 10.1080/10618600.2021.1935270
[46]	E. Brochu, V. M. Cora, N. De Freitas, A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning, preprint, arXiv: 1012.2599.
[47]	B. Hao, Y. Abbasi-Yadkori, Z. Wen, G. Cheng, Bootstrapping upper confidence bound, preprint, arXiv: 1906.05247.
[48]	S. Liu, A. B. Owen, Quasi-monte carlo quasi-newton in variational bayes, J. Mach. Learn. Res., 22 (2021), 11043–11065
[49]	P. E. Gill, E. Wong, Sequential quadratic programming methods, in Mixed Integer Nonlinear Programming, Academic press, (2012), 147–224. https://doi.org/10.1007/978-1-4614-1927-3_6
[50]	S. A. C. S. Jayasooriya, Y. M. M. S. Bandara, Measuring the Economic costs of traffic congestion, in 2017 Moratuwa Engineering Research Conference (MERCon), IEEE, Moratuwa, Sri Lanka, (2017), 141–146. https://doi.org/10.1109/MERCon.2017.7980471

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)