A mixed-integer linear programming model for the electric bus assignment problem with parking constraints
Abstract
We address an operational planning problem faced by public transit companies that operate a fleet of electric buses (EBs) out of an indoor parking (depot). Given a set of pre-computed sequences of trips (STs) that start and end at the depot, a set of identical EBs, a parking composed of identical lanes operated using a first-in, first-out (FIFO) policy, and a set of chargers, the Electric Bus Assignment Problem with Parking Constraints (eBAP-PC) consists in assigning an EB to each ST, assigning a lane to each EB returning to the depot after a ST, and scheduling its recharge such that the battery of each EB is never fully depleted. Feasible solutions must also ensure that the charging capacity is never exceeded and the EBs simultaneously parked in the same lane respect the lane capacity and the FIFO policy. Cast as a feasibility problem, we first model the eBAP-PC as a mixed-integer linear program that exploits a decomposition of the problem into three interrelated subproblems. We then introduce three techniques to accelerate its solution process. Finally, we report the results of three computational experiments conducted on instances derived from two real-world datasets. First, we assess the effectiveness of the acceleration strategies. Second, we perform a sensitivity analysis on some instance parameter values. Last, we benchmark our solution method against two constraint programming methods from the literature.