A Network Flow Approach to Battery Electric Bus Scheduling


A major challenge to adopting battery electric buses into bus fleets is the scheduling of the battery charging while considering route timing constraints and battery charge. This work develops a scheduling framework to balance the use of slow and fast chargers assuming the bus routes and charger locations are fixed. Slow chargers are utilized when possible to lower the cost of charging and fast chargers are used when needed to meet timing constraints and to ensure a sufficient charge for route execution. A directed graph is used to model the available charge times for buses that periodically return to the station to pick up passengers and to recharge its battery. A constrained network flow Mixed-Integer Linear Program (MILP) problem is formulated to optimize the scheduling of chargers as well as to determine the number of chargers required to meet battery state of charge thresholds. Using a randomly generated route schedule for thirty buses, results are presented that demonstrate the ability of the proposed method to find optimal charging plans while considering peak time charging costs and allowing for fixed and variable numbers of chargers. These optimal charging plans reduce costs up to 94\% compared to a naive thresholding based plan and up to 87\% compared to an optimal strategy that does not consider the peak time costs.

See publication:
This publication pertains to:
Charging Stations
Publication Authors:
  • Justin Whitaker
  • Greg Droge
  • Matthew Hansen
  • Daniel Mortensen
  • Jacob Gunther
It appeared in:
Peer-reviewed technical journal
Battery Electric Bus