Please join us for the following seminar on November 19, 3:00pm, in POST 302.
Two-Phase Bicriterion Search for Finding Fast and Efficient Electric Vehicle Routes
Department of Computer Science
University of California, Irvine
Abstract: The problem of finding an electric vehicle route that optimizes both driving time and energy consumption can be modeled as a bicriterion path problem. Unfortunately, the problem of finding optimal bicriterion paths is NP-complete. This paper studies such problems restricted to two-phase paths, which correspond to a common way people drive electric vehicles, where a driver uses one driving style (say, minimizing driving time) at the beginning of a route and another driving style (say, minimizing energy consumption) at the end. We provide efficient polynomial-time algorithms for finding optimal two-phase paths in bicriterion networks, and we empirically verify the effectiveness of these algorithms for finding good electric vehicle driving routes in the road networks of various U.S. states. In addition, we show how to incorporate charging stations into these algorithms, in spite of the computational challenges introduced by the negative energy consumption of such network vertices.
Biography: Prof. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987.
He is a Chancellor’s Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. In addition, he currently serves as Technical Director for the ICS Center for Algorithms and Theory of Computation. He was a professor in the Department of Computer Science at Johns Hopkins Universityfrom 1987-2001.
Dr. Goodrich’s research is directed at the design of high performance algorithms and data structures with applications to information assurance and security, the Internet, machine learning, and geometric computing. He has pioneered and led research on efficient solutions to a number of fundamental problems, including sorting, convex hull construction, nearest-neighbor searching, linear programming, privacy-preserving data access, network traceback, and data authentication.
With over 300 publications, including several widely-adopted books, his recent work includes contributions to efficient and secure distributed data structures, information privacy, social networks, and cloud security. He has served as a consultant to AT&T, Walt Disney Animation Studios, and the National Science Foundation, and he has experience as an expert witness in patent litigation involving algorithms, cryptography, operating systems, digital rights management (DRM), networking, and storage technologies. He is an ACM Distinguished Scientist, a Fellow of the American Association for the Advancement of Science (AAAS), a Fulbright Scholar, a Fellow of the IEEE, and a Fellow of the ACM. He is a recipient of the IEEE Computer Society Technical Achievement Award, the NSF Research Initiation Award, the DARPA Spirit of Technology Transfer Award, the Brown Univ. Award for Technological Innovation, the ACM Recognition of Service Award, and the Pond Award for Excellence in Undergraduate Teaching.