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 adjust planned 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 introduce and compare a number of aggregation approaches which use features of the post-decision state to aggregate the post-decision state space, thereby reducing the number of entries in the lookup table. Furthermore, since 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 epsilon-greedy exploration-exploitation algorithm for the IP setting. Our computational experiments show that despite the post-decision state of the DFRP being high-dimensional, a two-dimensional aggregation of the post-decision space is able to produce policies that outperform standard myopic policies. Moreover, our experiments demonstrate that the PDS-IP-Bounding algorithm provides computational advantages over solving the extended subproblem IPs using a commercial solver.
Article
View The Dynamic Freight Routing Problem for Less-than-Truckload Carriers