Title:
Optimal Planning for Electrification of Public Transit Systems and Infinite-Dimensional Linear Programming
Advisor:
Dr. Andy Sun, School of Management, Massachusetts Institute of Technology
Other Committee Members:
Dr. Santanu S. Dey, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Daniel Molzahn, School of Electrical and Computer Engineering, Georgia Institute of Technology
Dr. Van Hentenryck Pascal, School of Electrical and Computer Engineering, Georgia Institute of Technology
Dr. Alexander Shapiro, School of Industrial and Systems Engineering, Georgia Institute of Technology
Date and Time: April 13th, 1pm - 3pm (eastern time)
Location (Meeting Link): https://gatech.zoom.us/j/92690483609?pwd=L3V4U1NFOTNmMU5nQnZHNjlCVUpndz09
Meeting ID: 926 9048 3609
Passcode: 552508
Abstract:
Worldwide, the transportation sector is the second largest contributor to greenhouse gas emissions (GHG) after the electricity industry, while in the US, it is the largest contributor. One attractive solution to curb the GHG emission in the public transit segment is the Battery Electric Bus (BEB). A BEB produces zero tailpipe GHG emissions, its fuel cost is around 40% cheaper than a similar-sized fossil-fuel bus, its noise level is significantly lower, and it has less maintenance need. However, BEB technology poses new challenges to bus operation planning and charging placement due to the limited travel range and long charging hours. The optimal charging infrastructure plan may also vary with the spatial distribution of the routes.
In Chapter 2, we propose an Optimal Planning of Charging Facilities and Electric Bus Fleet (OPCF-EBF) model to optimally plan the transition to an entirely electric bus fleet. The OPCF-EBF model brings together long-term planning investment decisions and short-term operation assessment, where the latter considers modular arithmetic to model the repeating of daily 24-hour bus demand in each planning year. The proposed OPCF-EBF model is shown to be NP-hard through reduction from the uncapacitated facility location problem. We propose an effective and computationally scalable primal heuristic called ``Policy-Restriction'' that significantly outperforms and improves Gurobi. We conduct extensive computational studies using real-world data from public transit systems in major cities in the U.S. and around the world, which reveal insights into optimal investment and operational strategies.
In Chapter 3, we explore another dimension of the OPCF-EBF model with only one bus route and only depot BEBs, but an arbitrary number of battery states. We call this a fleet-sizing problem. We show that, under a simple non-preemptive charging strategy with no early charging and idling, the fleet-sizing problem is polynomially solvable. The proof of this fact relies on the ``almost'' total unimodular nature of the constraint matrix for the operation problem given the number of depot BEBs. We also rely on a proximity result that quantifies the distance of the optimal solution of a Separable Convex Integer Program and the solution of its corresponding linear relaxation. We then prove the polynomial-time complexity based on the number of intermediate auxiliary linear programs necessary to obtain an integral optimal solution. Inspired by the fleet-sizing problem, we introduce a special class of polynomially solvable Separable Integer Programs followed by the notion of a Dyad Contiguous Row (DCR) matrix.
In Chapter 4, we investigate deeply the notion of a stationary optimization problem. We introduce a type of primal and dual for infinite-dimensional stationary linear programs based on a restriction to L-infinity and L1 spaces of appropriate dimensions. We motivate this approach from the fixed-point formulation of discounted stationary programs and prove weak duality. We illustrate with a hydro-thermal stationary planning problem that strong duality may hold for a large class of infinite-dimensional stationary linear programs. In particular, the value function of the latter is piecewise linear convex with countably many affine functions. Weak duality may fail if the L-infinity and L1 set constraints are removed.
In Chapter 5, we investigate an algebraic method to characterize extreme points of a class of infinite dimensional optimization problems called row-finite linear programs. We introduce the notion of an Asymptotically Compatible (AC) solution to extend the definition of a basic solution for infinite dimensional linear programs. In fact, a solution to a row-finite inequality system is extreme if the only AC solution to the system induced by the active linear constraints is the trivial one. We describe how the Gauss-Jordan elimination algorithm parameterize all the solutions of row-finite equality system. Our approach is illustrated in the characterization of extreme circulations over infinite digraphs of finite degree.