Systemwide Planning with a Branch-and-Price Algorithm for Pavement-Marking Assessment Data Collection via the Mobile Retroreflectivity Unit Routing Model
Publication: Journal of Computing in Civil Engineering
Volume 38, Issue 3
Abstract
The visibility of pavement markings is one of the most critical factors for traffic safety, and a periodical assessment plan is crucial for maintaining this function. Traditional assessment methods, such as visual windshield surveys or manual testing using handheld devices, are unsafe, time-consuming, and labor-intensive. In recent years, transportation agencies have begun to adopt the use of mobile retroreflectivity units (MRUs) for condition assessment of pavement markings. MRUs, different from other manual methods, can be utilized to collect large-scale retroreflectivity data in an efficient manner. However, no relevant research has yet proposed a mathematical optimization model for arranging the evaluation schedule and paths of MRUs. This study aims to propose a MRU routing model, and an efficient solution methodology. A branch-and-price algorithm, including column generation and branch-and-bound, was implemented. Computational experiments have been conducted based on actual tasks from the Florida MRU program for validation. Results show that the proposed solution methodology with a set partitioning model in this study not only finds the optimal solution for problems with tasks less than 60, but also effectively narrows the solution gap to be within 1.0% for problems with tasks less than 131.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some data used during the study were provided by a third party. Direct requests for these materials may be made to the provider. The Florida Department of Transportation provided data regarding the assessment requirements used in this work (FDOT 2020). Additionally, the network distance was collected from Project OSRM Project OSRM (2020).
Acknowledgments
The authors thank the Ministry of Science and Technology (MOST) of Taiwan for Grant 109-2221-E-002-015 that has made this work possible. The second author is also thankful for the support he received from the Transportation Analytics and Decision Sciences Group of the Buildings and Transportation Science Division, Oak Ridge National Laboratory. The authors thank the Florida Department of Transportation for the data provided (FDOT 2020). Additionally, the network distance was collected from Project OSRM Project OSRM (2020). This manuscript has been authored in part by UT-Battelle, LLC, under Contract DE-AC05-00OR22725 with the US Department of Energy (DOE).
References
Abdelaty, A., O. G. Attia, H. D. Jeong, and B. K. Gelder. 2018. “Dynamic pavement delineation and visualization approach using data mining.” J. Comput. Civ. Eng. 32 (4): 04018019. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000758.
Ai, C. 2020. A pavement marking inventory and retroreflectivity condition assessment method using mobile lidar. Boston: Massachusetts Department of Transportation.
Aktan, F., and T. Schnell. 2004. “Performance evaluation of pavement markings under dry, wet, and rainy conditions in the field.” Transp. Res. Rec. 1877 (1): 38–49. https://doi.org/10.3141/1877-05.
Barnhart, C., E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance. 1998. “Branch-and-price: Column generation for solving huge integer programs.” Oper. Res. 46 (3): 316–329. https://doi.org/10.1287/opre.46.3.316.
Belenguer, J. M., and E. Benavent. 2003. “A cutting plane algorithm for the capacitated arc routing problem.” Comput. Oper. Res. 30 (5): 705–728. https://doi.org/10.1016/S0305-0548(02)00046-1.
Braekers, K., K. Ramaekers, and I. V. Nieuwenhuyse. 2016. “The vehicle routing problem: State of the art classification and review.” Comput. Ind. Eng. 99 (Aug): 300–313. https://doi.org/10.1016/j.cie.2015.12.007.
Breedam, A. V. 1995. “Improvement heuristics for the vehicle routing problem based on simulated annealing.” Eur. J. Oper. Res. 86 (3): 480–490. https://doi.org/10.1016/0377-2217(94)00064-J.
Byun, J.-E., and J. Song. 2020. “Bounds on reliability of larger systems by linear programming with delayed column generation.” J. Eng. Mech. 146 (4): 04020008. https://doi.org/10.1061/(ASCE)EM.1943-7889.0001717.
Chang, T.-H., A. Y. Chen, C.-W. Chang, and C.-H. Chueh. 2014. “Traffic speed estimation through data fusion from heterogeneous sources for first response deployment.” J. Comput. Civ. Eng. 28 (6): 04014018. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000379.
Chang, T.-H., C.-S. Hsu, C. Wang, and L.-K. Yang. 2008. “Onboard measurement and warning module for irregular vehicle behavior.” IEEE Trans. Intell. Transp. Syst. 9 (3): 501–513. https://doi.org/10.1109/TITS.2008.928243.
Chen, A. Y., and J. C. Chu. 2016. “TDVRP and BIM integrated approach for in-building emergency rescue routing.” J. Comput. Civ. Eng. 30 (5): C4015003. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000522.
Chen, A. Y., and F. Peña-Mora. 2011. “Decentralized approach considering spatial attributes for equipment utilization in civil engineering disaster response.” J. Comput. Civ. Eng. 25 (6): 457–470. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000100.
Chen, A. Y., F. Peña-Mora, and Y. Ouyang. 2011. “A collaborative GIS framework to support equipment distribution for civil engineering disaster response operations.” Autom. Constr. 20 (5): 637–648. https://doi.org/10.1016/j.autcon.2010.12.007.
Chou, C.-C., W.-C. Chiang, and A. Y. Chen. 2022. “Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays.” Transp. Res. Part E Logist. Transp. Rev. 158 (Jun): 102591. https://doi.org/10.1016/j.tre.2021.102591.
Choubane, B., J. Sevearance, C. Holzschuher, J. Fletcher, and C. R. Wang. 2018. “Development and implementation of a pavement marking management system in Florida.” Transp. Res. Rec. 2672 (12): 209–219. https://doi.org/10.1177/0361198118787081.
Choubane, B., J. Sevearance, H. S. Lee, P. Upshaw, and J. Fletcher. 2013. “Repeatability and reproducibility of mobile retroreflectivity units for measurement of pavement markings.” Transp. Res. Rec. 2337 (1): 74–82. https://doi.org/10.3141/2337-10.
Christofides, N., A. Mingozzi, and P. Toth. 1981. “State-space relaxation procedures for the computation of bounds to routing problems.” Networks 11 (2): 145–164. https://doi.org/10.1002/net.3230110207.
Costa, L., C. Contardo, and G. Desaulniers. 2019. “Exact branch-price-and-cut algorithms for vehicle routing.” Transp. Sci. 53 (4): 946–985. https://doi.org/10.1287/trsc.2018.0878.
Dumas, Y., J. Desrosiers, E. Gelinas, and M. M. Solomon. 1995. “An optimal algorithm for the traveling salesman problem with time windows.” Oper. Res. 43 (2): 367–371. https://doi.org/10.1287/opre.43.2.367.
Eilon, S., C. D. T. Watson-Gandy, N. Christofides, and R. de Neufville. 1974. “Distribution management-mathematical modelling and practical analysis.” IEEE Trans. Syst. Man Cybern. 4 (6): 589. https://doi.org/10.2307/2346285.
FDOT (Florida Department of Transportation). 2019. Maintenance rating program handbook. Tallahassee, FL: FDOT.
FDOT (Florida Department of Transportation). 2020. “Florida state department of transportation pavement marking management data.” Accessed September 30, 2020. https://fdotwp1.dot.state.fl.us/pavementmarkingmanagement.
FDOT (Florida Department of Transportation). 2023. Florida test method for measuring retroreflectivity of pavement marking materials using a mobile retroreflectivity unit. Tallahassee, FL: FDOT.
Federal Highway Administration. 1999. Asset management primer. Washington, DC: DOT.
Federal Highway Administration. 2022. “National standards for traffic control devices: The manual on uniform traffic control devices for streets and highways; Maintaining pavement marking retroreflectivity.” Fed. Regist. 87 (Jun): 47921–47931.
Feillet, D., M. Gendreau, A. L. Medaglia, and J. L. Walteros. 2010. “A note on branch-and-cut-and-price.” Oper. Res. Lett. 38 (5): 346–353. https://doi.org/10.1016/j.orl.2010.06.002.
Fisher, M. L., and R. Jaikumar. 1981. “A generalized assignment heuristic for vehicle routing.” Networks 11 (2): 109–124. https://doi.org/10.1002/net.3230110205.
Golden, B. L., and R. T. Wong. 1981. “Capacitated arc routing problems.” Networks 11 (3): 305–315. https://doi.org/10.1002/net.3230110308.
Hadjidemetriou, G. M., P. A. Vela, and S. E. Christodoulou. 2018. “Automated pavement patch detection and quantification using support vector machines.” J. Comput. Civ. Eng. 32 (1): 04017073. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000724.
Hoang, N.-D., Q.-L. Nguyen, and D. T. Bui. 2018. “Image processing–based classification of asphalt pavement cracks using support vector machine optimized by artificial bee colony.” J. Comput. Civ. Eng. 32 (5): 04018037. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000781.
Holzschuher, C., and J. Sevearance. 2017. FDOT quality assurance for mobile retroreflectivity units. Tallahassee, FL: Florida Department of Transportation.
Hsieh, Y.-A., and Y. J. Tsai. 2020. “Machine learning for crack detection: Review and model performance comparison.” J. Comput. Civ. Eng. 34 (5): 04020038. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000918.
Joubert, J. W. 2007. The vehicle routing problem: Origins and variants. Hatfield, Pretoria: Univ. of Pretoria.
Kockelman, K. M., et al. 2016. Implications of connected and automated vehicles on the safety and operations of roadway networks: A final report. Washington, DC: Federal Highway Administration.
Kulkarni, R., and P. Bhave. 1985. “Integer programming formulations of vehicle routing problems.” Eur. J. Oper. Res. 20 (1): 58–67. https://doi.org/10.1016/0377-2217(85)90284-X.
Kulkarni, S., M. Krishnamoorthy, A. Ranade, A. T. Ernst, and R. Patil. 2018. “A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem.” Transp. Res. Part B Methodol. 118 (Jun): 457–487. https://doi.org/10.1016/j.trb.2018.11.007.
Kumar, S. N., and R. Panneerselvam. 2012. “A survey on the vehicle routing problem and its variants.” Intell. Inf. Manage. 4 (3): 66–74. https://doi.org/10.4236/iim.2012.43010.
Laporte, G. 2009. “Fifty years of vehicle routing.” Transp. Sci. 43 (4): 408–416. https://doi.org/10.1287/trsc.1090.0301.
Lawler, E. L., and D. E. Wood. 1966. “Branch-and-bound methods: A survey.” Oper. Res. 14 (4): 699–719. https://doi.org/10.1287/opre.14.4.699.
Lee, Y.-C., Y.-S. Chen, and A. Y. Chen. 2022. “Lagrangian dual decomposition for the ambulance relocation and routing considering stochastic demand with the truncated poisson.” Transp. Res. Part B Methodol. 157 (Aug): 1–23. https://doi.org/10.1016/j.trb.2021.12.016.
Lin, K.-L., T.-C. Wu, and Y.-R. Wang. 2016. “An innovative road marking quality assessment mechanism using computer vision.” Adv. Mech. Eng. 8 (6): 168781401665404. https://doi.org/10.1177/1687814016654043.
Lin, Y.-C., S.-T. Liao, C. R. Wang, and A. Y. Chen. 2019. “VRP-based model for lane marking assessment with MRU vehicle.” In Proc., 4th Int. Conf. on Civil and Building Engineering Informatics (ICCBEI 2019). Osaka, Japan: Asian Group for Civil Engineering Informatics.
Liu, H.-H., A. Y. Chen, C.-Y. Dai, and W.-Z. Sun. 2015. “Physical infrastructure assessment for emergency medical response.” J. Comput. Civ. Eng. 29 (3): 04014044. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000395.
Longo, H., M. P. de Aragão, and E. Uchoa. 2006. “Solving capacitated arc routing problems using a transformation to the CVRP.” Comput. Oper. Res. 33 (6): 1823–1837. https://doi.org/10.1016/j.cor.2004.11.020.
Mantha, B. R. K., C. C. Menassa, and V. R. Kamat. 2017. “Task allocation and route planning for robotic service networks in indoor building environments.” J. Comput. Civ. Eng. 31 (5): 04017038. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000687.
Project OSRM. 2020. “Modern c++ routing engine for shortest paths in road networks.” Accessed September 30, 2020. https://project-osrm.org/.
Righini, G., and M. Salani. 2006. “Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints.” Discrete Optim. 3 (3): 255–273. https://doi.org/10.1016/j.disopt.2006.05.007.
Simsir, F., and D. Ekmekci. 2019. “A metaheuristic solution approach to capacitied vehicle routing and network optimization.” Eng. Sci. Technol. Int. J. 22 (3): 727–735. https://doi.org/10.1016/j.jestch.2019.01.002.
Sitzabee, W. E., W. Rasdorf, J. E. Hummer, and H. A. Devine. 2009. “Data integration of pavement markings: A case in transportation asset management.” J. Comput. Civ. Eng. 23 (5): 288–298. https://doi.org/10.1061/(ASCE)0887-3801(2009)23:5(288).
Upshaw, P., J. Sevearance, and H. Lee. 2013. Operations manual for mobile retroreflectivity units. Tallahassee, FL: Florida Department of Transportation.
Usberti, F. L., P. M. França, and A. L. M. França. 2011. “The open capacitated arc routing problem.” Comput. Oper. Res. 38 (11): 1543–1555. https://doi.org/10.1016/j.cor.2011.01.012.
Wang, C. 2017. “A spatiotemporal methodology for pavement rut characterization and deterioration analysis using long-term 3d pavement data.” Ph.D. dissertation, School of Civil and Environmental Engineering, Georgia Institute of Technology.
Wang, C., Z. Wang, and Y.-C. Tsai. 2016. “Piecewise multiple linear models for pavement marking retroreflectivity prediction under effect of winter weather events.” Transp. Res. Rec. 2551 (1): 52–61. https://doi.org/10.3141/2551-07.
Wang, C. R., and Y.-C. J. Tsai. 2019. “Categorizing 3d pavement rut shapes using 3d laser imaging technology.” In Pavement and asset management, 3–10. London: CRC Press.
Wang, I.-L., Y.-C. J. Tsai, and F. Li. 2011. “A network flow model for clustering segments and minimizing total maintenance and rehabilitation cost.” Comput. Ind. Eng. 60 (4): 593–601. https://doi.org/10.1016/j.cie.2011.01.001.
Yuan, Y., D. Cattaruzza, M. Ogier, and F. Semet. 2020. “A note on the lifted miller–tucker–zemlin subtour elimination constraints for routing problems with time windows.” Oper. Res. Lett. 48 (2): 167–169. https://doi.org/10.1016/j.orl.2020.01.008.
Zhang, A., K. C. P. Wang, Y. Fei, Y. Liu, S. Tao, C. Chen, J. Q. Li, and B. Li. 2018a. “Deep learning–based fully automated pavement crack detection on 3D asphalt surfaces with an improved CrackNet.” J. Comput. Civ. Eng. 32 (5): 04018041. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000775.
Zhang, K., H. D. Cheng, and B. Zhang. 2018b. “Unified approach to pavement crack and sealed crack detection using preclassification based on transfer learning.” J. Comput. Civ. Eng. 32 (2): 04018001. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000736.
Zhang, Y., and H. Ge. 2012. “Assessment of presence conditions of pavement markings with image processing.” Transp. Res. Rec. 2272 (1): 94–102. https://doi.org/10.3141/2272-11.
Information & Authors
Information
Published In
Journal of Computing in Civil Engineering
Volume 38 • Issue 3 • May 2024
Copyright
© 2024 American Society of Civil Engineers.
History
Received: Apr 28, 2023
Accepted: Oct 31, 2023
Published online: Feb 6, 2024
Published in print: May 1, 2024
Discussion open until: Jul 6, 2024
ASCE Technical Topics:
- Algorithms
- Data collection
- Engineering fundamentals
- Infrastructure
- Mathematical models
- Mathematics
- Methodology (by type)
- Models (by type)
- Optimization models
- Pavement markings
- Pavements
- Research methods (by type)
- Routing (transportation)
- Traffic engineering
- Traffic management
- Traffic models
- Traffic safety
- Transportation engineering
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.