Asset replacement considering the impact on a single objective is a well-studied problem, but the extension to multiple objectives poses new challenges. We examine the service life of a passenger vehicle from energy, emissions and economic perspectives. The Life Cycle Optimization performed considers burdens accrued by each objective in the materials production, component manufacturing and assembly, use, maintenance and repair, and end-of-life phases of each vehicle's life. We discover that as technology improves, frequent vehicle replacements, which bring newer technologies onto the road sooner, favor the local emissions objective. In contrast, the economic and global-impact emissions objectives are minimized by longer vehicle lives since their manufacturing burdens are larger in proportion to moderate savings in fuel economy gained by anticipated technolgical improvements. We analyze the performance of three heuristic algorithms for the identification of Pareto-optimal solutions to the multiobjective vehicle replacement problem. These are replacement policies in which the value of one objective may not be improved without degrading the value of another objective. We implement two multiobjective genetic algorithms and one tabu search-based algorithm, and we validate the results using the Constraint method. In doing this, we discover some commonalities across the algorithms, such as the ability to identify the clustering of solutions into groups corresponding to the number of replacements achieved over the fixed time horizon. Having determined a representative set of Pareto-optimal solutions for single-vehicle replacement, we employ their trade-off information in constructing a multivehicle model that examines the vehicle replacement decisions of consumer groups. As the model aggregates these individual decisions, we investigate the potential impact of national policy changes such as an increase in fuel tax or widespread introduction of new technology as seen in an advanced, lower-emitting vehicle.