The Dynamic Freight Routing Problem for Less-Than-Truckload Carriers

Less-than-truckload (LTL) carriers transport freight shipments from origins to destinations by consolidating freight using a network of terminals. As daily freight quantities are uncertain, carriers dynamically decide freight routes on the day of operations. We introduce the dynamic freight routing problem (DFRP) and model this problem as a Markov decision process (MDP). To overcome the curses of dimensionality of the MDP model, we introduce an approximate dynamic programming (ADP) solution approach that uses a lookup table to store value function approximations and present and compares a number of aggregation approaches that use features of the postdecision states (PDSs) to aggregate the PDS space and reduce the number of entries in the lookup table. Furthermore, because the decision subproblems are integer programs (IPs), we present a framework for integrating lookup tables into the decision subproblem IPs. This framework consists of (1) a modeling approach for the integration of lookup table value function approximations into subproblem IPs to form extended subproblem IPs; (2) a solution approach, PDS-IP-bounding, which decomposes the extended subproblem IPs into many smaller IPs and uses dynamic bounds to reduce the number of small IPs that have to be solved; and (3) an adaptation of the ϵ-greedy exploration-exploitation algorithm for the IP setting. Our computational experiments show that despite the DFRP having high-dimensional PDS vectors, a two-dimensional aggregation of the space can produce policies that outperform standard myopic policies. Moreover, they demonstrate that the PDS-IP-bounding algorithm provides computational advantages over solving the extended subproblem IPs using a commercial solver.