Design space exploration of hybrid electric vehicles is an important multi-objective global optimization problem. One of the main objectives is to minimize fuel consumption while maintaining satisfactory driveability performance and vehicle cost. The design problem often includes multiple design options, including different driveline architectures and component sizes, where different candidates have various trade-offs between different, in many cases contradictory, performance requirements. Thus, there is no global optimum but a set of Pareto-optimal solutions to be explored. The objective functions can be expensive to evaluate, due to time-consuming simulations, which requires careful selection of which candidates to evaluate. A design space exploration algorithm is proposed for finding the set of Pareto-optimal solutions when the design search space includes multiple design options. As a case study, powertrain optimization is performed for a medium-sized series hybrid electric delivery truck.