This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
Automatic Generation of Evaluation Courses for Car Navigation Systems Via Combinatorial Optimization
Technical Paper
2023-01-0589
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
To accelerate development and improve the quality of car navigation systems, we have built a system for automatic generation of evaluation courses. In general, the operation of car navigation systems is verified by driving tests using vehicles. The evaluation courses need to be designed so that inspection sites, such as underground parking lots, tunnels, etc., will be visited during the evaluation period. They should be circuits that include as many inspection sites as possible within a defined distance. However, as the number of the inspection sites increases, the number of courses that can be designed becomes enormous. This makes it difficult to create courses that meet all of the requirements. Hence engineers have spent a lot of time on evaluation course design. For this reason, automatic course generation has become essential for reducing man-hours. We believe that one of the effective approaches is to treat automatic evaluation course generation as a combinatorial optimization problem. In our formulation, inspection sites are grouped into clusters according to the required number of courses, and the shortest circuit is constructed in each cluster.
Then, we treat the clustering and shortest circuit generation problems separately as a bi-level combinatorial optimization problem. In other words, the original problem is divided into smaller parts of the combinatorial optimization problems. We then propose a Markov chain Monte Carlo method for solving the bi-level optimization problem, and construct a system for automatic generation of evaluation courses. The proposed method significantly reduces course-design time compared to manual course construction.
Authors
Citation
Tomita, K., Kojima, K., Saito, S., Iwami, T. et al., "Automatic Generation of Evaluation Courses for Car Navigation Systems Via Combinatorial Optimization," SAE Technical Paper 2023-01-0589, 2023, https://doi.org/10.4271/2023-01-0589.Also In
References
- Laporte , G. The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms European Journal of Operational Research 59 3 1992 345 358
- Schuetz , Martin J.A. et al. 2022
- Kadowaki , T. , and Nishimori , H. 1998
- Morita , S. and Nishimori , H. Mathematical Foundation of Quantum Annealing J. Math. Phys. 49 2008 125210 10.1063/1.2995837
- Ohzeki , M. and Nishimori , H. Quantum Annealing: An Introduction and New Developments J. Comput. Theor. Nanosci 8 6 2011 963 971
- Neukart , F. et al. Traffic Flow Optimization Using a Quantum Annealer Front. ICT 4 2017 29
- Ohzeki , M. Breaking Limitation of Quantum Annealer in Solving Optimization Problems under Constraints Scientific Reports 10 3126 2020
- Ohzeki , M. , Miki , A. , Miyama , M.J. , and Terabe , M. Control of Automated Guided Vehicles without Collision by Quantum Annealer and Digital Devices Front. Comput. Sci. 1 2019 9 10.3389/fcomp.2019.00009
- Haba , R. , Ohzeki , M. , and Tanaka , K. Travel Time Optimization on Multi-AGV Routing by Reverse Annealing Scientific Reports 12 17753 2022
- https://nlftp.mlit.go.jp/ksj/gml/datalist/KsjTmplt-N03-v2_3.html
- Metropolis , N. , Rosenbluth , A.W. , Rosenbluth , M.N. et al. Equation of State Calculations by Fast Computing Machines The Journal of Chemical Physics 21 6 1953 1087 1092
- Kirkpatrick , S. , Gelatt , C.D. , and Vecchi , M.P. Optimization by Simulated Annealing Sci. 220 4598 1983 671 680 10.1126/science.220.4598.671
- Lawler , E.L. , Lenstra , J.K. , Rinnooy Kan , A.H.G. , and Shmoys , D.B. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization John Wiley & Sons 1985
- Garey , M.R. and Johnson , D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness San Fransisco Freeman 1979
- https://coin-or.github.io/pulp/