Plug-in Hybrid Electric Vehicles (PHEVs) offer a great opportunity to significantly reduce petroleum consumption. The fuel economy of PHEV is highly dependent on All-Electric-Range (AER) and control strategy. Previous studies have shown that in addition to parameters influencing Hybrid Electric Vehicles (HEVs), control strategies of PHEVs are also influenced by the trip distance. This additional parameter makes it even more difficult to manually tune the parameters that minimize fuel consumption. This study uses a pre-transmission parallel PHEV model developed with the Powertrain System Analysis Toolkit (PSAT). A non-derivative based algorithm called DIRECT (for DIvided RECTangles) is used to optimize the main control strategy parameters. The fuel economy and main performance criteria of the PHEVs are compared for the initial design and final optimal design. An optimal control solution resulting from an extensive search of the entire design space can provide physical insight into the PHEV operation.