We introduce the charging station location problem with plug-in hybrid electric vehicles.

Our objective is to maximize the vehicle-miles-traveled using electricity.

We present a Benders decomposition algorithm accelerated through Pareto-optimal cuts.

The structure of the formulation allows us to construct the cuts as closed form expressions.

Our algorithm both accelerates the solution process and effectively handles instances of realistic size.