On-line algorithms for truck fleet assignment and scheduling under real-time information

With greater availability of real-time information systems, algorithms are needed to support commercial fleet operators in their decisions to assign vehicles and drivers to loads in a dynamic environment. A rolling horizon framework for the dynamic assignment and sequencing of trucks to jobs consisting of picking up and delivering full truckloads when requests for service arise on a continuous basis is presented. A mathematical formulation of the problem faced at each stage is presented; its solution allows for the dynamic reassignment of trucks to loads, including diversion to a new load of a truck already en route to pick up another load, as well as for the dynamic resequencing of the order in which loads are to be served as new loads arrive and conditions unfold. Loads have associated time windows for pickup and delivery, and the objective function includes an explicit penalty cost for not serving a particular load. A solution algorithm is presented and implemented, and computational results are presented, yielding insight into various operational trade-offs in dynamic fleet operations. Because applicability of the solution algorithm is limited to relatively small problems, and given the stochastic dynamic nature of these systems, numerical experiments are performed to compare the quality of the solution obtained using this approach with the performance of simpler and less computationally demanding local rules.