As the adoption of electric vehicles (EVs) grows, optimizing the EV charging process becomes crucial for efficient energy utilization and grid management. Some key aspects related to EV charging optimization include charging cost minimization, battery health and efficiency optimization, EV user behavior analysis, EV charging stations placement or location optimization etc. Through this dissertation, our aim is to contribute to the field of EVs in a way that helps in optimizing the huge infrastructure that will be required in coming years to accommodate the large number of EVs on roads.
In the first chapter, the problem under consideration is optimizing the charging schedule of an electric vehicle to minimize the total charging cost. In order to preserve battery life, the charging rate is restricted based on the current state-of-charge (SoC) of the battery. Noting that the charging rate limit is typically represented as a decreasing concave function of SoC, we first formulate the problem as a constrained optimal control problem. Discretization of the problem poses a nonlinear programming (NLP) problem that has a linear objective function and a convex feasible region. The proofs of the convexity of the feasible region and the strong duality of the problem are presented. Exploiting the strong duality, we present an exact solution approach that employs a cutting plane method to solve the Lagrangian dual problem in conjunction with the recovery of the primal solution. Subsequently, we propose two heuristics that employ greedy strategies, where charging is conducted to its rate limits over the periods with the lowest costs. We also present examples that illustrate these greedy strategies may not yield exact solutions. A thorough numerical experiment on simulated data is provided for the comparative efficacy of the proposed methods to the existing method.
In the second chapter, we consider a disjointly constrained bilinear program in which the variables are partitioned into two disjoint sets, each with its own respective set of constraints while bilinear terms in the objective function relate the two sets of variables. Leveraging the fact that the problem reduces to a linear program when one set of variables is held constant, we initially provide a geometric characterization of the relationship between the optimality condition of a basic feasible solution within one set of variables and the corresponding polyhedron in the other set of variables that achieves optimality, which we call the optimality polyhedron. By exploiting this relationship, we propose an algorithm that implicitly enumerates basic feasible solutions to expand the set of optimality polyhedra that eventually covers the feasible region in the other set of variables. A numerical study on randomly generated instances reveals that the proposed algorithm examines only 3.56% of the total number of basic feasible solutions on average while generating higher quality solutions compared to an off-the-shelf solver.
In the third chapter, we formulate the hard clustering problem of assigning a data point to exactly one cluster as a bilinear optimization problem. Using the Manhattan distance between points and their respective cluster centers as the objective function, the optimization problem is formulated as a minimization problem. This bilinear optimization problem is solved using the polyhedra expansion algorithm with initial clustering from k-means algorithm. The application of this methodology is demonstrated on the National Household Travel Survey data by utilizing the basic demographic and psychographic variables. The objective of this study is to develop a clustering scheme that can be utilized as a baseline to create potential customer segments by analyzing the driving behavior of a group of EVs.