Algorithms and Strategies for Dynamic Carrier Fleet Operations: Applications to Local Trucking Operations

This assignment problem is investigated in several steps. First, a myopic deterministic version is studied in which travel time, service time and the demands are fixed. A new non-decreasing partitioning scheme to deal with time window constraints for this problem is developed. A feasible option for solving the dynamic assignment problem is to repeatedly apply this deterministic algorithm in a dynamic setting in a rolling horizon framework whenever new information is available. The deterministic algorithm provides a basis for further consideration of stochastic factors including queuing times, handling times and travel times under traffic congestion. Several stochastic models are proposed and discussed. The discussion indicates that direct adoption of stochastic models aimed at other problems involves great difficulty because of the complex nature of this problem. Therefore, approximation models are preferable. Further, by incorporating additional requirements of trailer repositioning, a more general problem of multi-layered resource allocation is defined. Multi resource allocation problems have wide practical implications in air, rail and maritime carrier fleet operations. The discussion of these models highlights a promising opportunity for future research. All the methods and ideas motivated by this specific assignment problem can be easily extended to other routing and scheduling problems. As part of this research, we further investigated some NP-hard problems that generally underlie such applications. A special case of TSP problem, titled "the TSP with separation requirement", is examined and a new formulation is presented. The formulation takes the TSP with precedence constraints and the time dependent TSP as special cases. Additionally, a new general cutting plane method is proposed. It applies, but is not limited to, integer programming problem with binary variables. We believe that this method has some advantages over its counterpart, Gomory's method. However, further effort is needed to test its performance.