Schedule Optimizer & HoS Clocks

At CloudTrucks we’re building a platform for truck drivers to run better businesses. A common difficulty we hear from our users is finding efficient routes that minimize deadhead and maximize profit while keeping them in line with regulations. One of the many tools we provide towards this end is the Schedule Optimizer — a tool that takes, as input, a driver’s desired time and distance to drive and/or revenue to earn, and as output formulates a sequence of loads for them to carry, such that they spend minimal time driving without a load (AKA deadhead). Sounds like an old-fashioned constraint satisfaction problem, right? However, the driver’s preference constraints are only one part of the picture.

Truck drivers in the US have to follow a number of stringent regulations around safety. These are defined and enforced by the Federal Motor Carrier Safety Administration (FMCSA). One subset of these regulations relates to Hours of Service (HoS), i.e. the duration of time a driver spends driving their vehicle as part of their job. There are a handful of rules for drivers to follow, most of which are simple enough on their own, but in combination they make the process of planning out a feasible and compliant schedule quite complex, to the point where some drivers will simply forgo trying to plan multi-load schedules and play it by ear, working only one load at a time. This is not optimal for the driver, because it means their work schedule is less efficient than it could be, which in turn means they are earning less than they could be in a given time period.

But with the power of Python and object-oriented programming we’ve developed a system that can balance both driver preferences and regulatory HoS constraints when formulating a schedule — in this blog post, we’ll focus on how we built the latter. We start by modeling the various regulations via two abstractions, Limits and Rules. Limits are a simple data class defined as such:

class Limit:
  state: DrivingState
  limit: Time

DrivingState is used to represent different states defined by the FMCSA, such as “On Duty” - when a driver is on the clock - and “Driving” - when they’re actively driving a load. An interesting wrinkle worth noting is that a driver can be driving their truck while off-duty, to get home or to other accommodations, a practice known as “Personal Conveyance” (but there are also limits to how long they can do so, to avoid gaming the regulations).

There are 3 types of Rules the FMCSA defines: Limit, Shift, and Cycle. Rules are then composed of a pair of limits (how long they can drive, and how long they must rest), and a name for the rule.

class ShiftRule:
  name: str
  active: Limit
  rest: Limit

So what do we do with these Rules and Limits? We make clocks to track them! As our schedule optimizer uses a constraint satisfaction algorithm to work towards an (approximately) optimal schedule given our driver’s preferences, it explores potential schedules of loads; a schedule is comprised of a sequence of events with temporal durations, as well as flags indicating if the event is a drive, rest period or another event, among other metadata. For each potential schedule, to validate that it is feasible according to FMCSA regulations, we instantiate a Clock object for each Rule. As we step through the events in a potential schedule, the duration and type of each event are given as input to an advance method that modifies the state of the clock to track the durations relevant to the rule. The implementations vary for each type of Clock, but we’ve included an abridged version of the abstract base class in the appendix below.

One neat property of these abstractions is that we can use them looking both forward and backward in time — while we’ve been describing them in the context of building out schedules in the future, we’re also able to use the same code to evaluate historical schedules from our drivers ELD (short for electronic logging device, a black box device all US commercial trucks must carry for tracking their regulatory compliance) data, to give them insights into their HoS rules compliance. Wall clocks can’t do that!

What does this all mean for drivers? For one, our drivers can leverage our schedule optimizer to make schedules for them, with a high degree of confidence that the schedule will be making them about as much revenue as possible given their preferences. Additionally, they can have peace of mind that these schedules will be feasible, both in terms of being physically achievable and in terms of being compliant with regulations. Finally, since CloudTrucks never forces dispatch, drivers are free to generate schedules and not follow them, just to see what a revenue-maximizing, fully feasible schedule looks like, and then incorporate that knowledge into their hand-made schedules if they so desire. If this problem interests you and you want to build more reusable abstractions that help truck drivers run better businesses, check out our hiring page!

Thanks to everyone who contributed to both the code and this blog post!

Appendix:

class Clock(abc.ABCMeta):
    """Clocks track, on a rule-by-rule basis, the adherence to each 
       hour of service regulation
       This class represents the Clock protocol, 
       which all rules must obey. 
       It provides a few convenience methods as well.
       Parameters
       ----------
       rule: Rule
         The rule which this clock tracks.
    """
    rule: Rule
    @abc.abstractproperty
    def counter(self) -> Time:
        """
        Counter represents how much time has elapsed which counts 
        against this clock
        """
        pass
    @abc.abstractmethod
    def _active(self, duration: hos_time.Time) -> List[Violation]:
        """Increment the clock for the active state for this rule"""
        pass
    @abc.abstractmethod
    def _rest(self, duration: hos_time.Time) -> List[Violation]:
        """Increment the rest clock for this rule"""
        pass
    @abc.abstractmethod
    def _inactive(self, duration: hos_time.Time) -> List[Violation]:
        """No clock is incrementing, but no rest is accruing"""
        pass
    @abc.abstractmethod
    def time_until_rest(self) -> hos_time.Time:
        """Hours remaining on this clock until a rest is required"""
        pass
    @abc.abstractmethod
    def time_until_reset(self) -> hos_time.Time:
        """Hours remaining on this clock until a rest is
           fulfilled
        """
        pass
    @abc.abstractmethod
    def advance(self, state: DrivingState, duration: Time) ->
      List[Violation]:
        """
        Advance this clock forward, in a given driving state,
        and return a list of violations which occur during this
        advancement.
        Parameters
        ----------
        state: DrivingState
          What state is the driver in during this time?
        duration: Time
          How long does the driver advance?
        Returns
        -------
        violations: List of Violation
           List of violations which occurred while advancing in
           this state, possibly empty.
        """
        pass