Dynamic programming applied to a new formulation of the stochastic truckload routing problem.

摘要

This thesis focuses on vehicle routing and scheduling, more specifically the truckload routing problem (TRP). We include the consideration of time windows (TRPTW). In the TRPTW, each vehicle carries a single load which fulfills either the cubic volume or weight capacity of the equipment. The demand for these loads is stochastic.; The continuous flow TRPTW looks beyond traditional out and back routing by building extended routes which combine origin/destination pairs. Rather than returning directly to its domicile, a vehicle will instead proceed on to pick-up and deliver a subsequent load, which may take it even farther from the domicile. Each vehicle stays out on the road for as long as allowable by the various scenarios presented in the Department of Transportation (DOT) hours of service (HOS) restrictions.; This research presents an approach to the formulation of the TRPTW which allows the use of optimization through penalty methods and dynamic programming. The traditional lane definition (origin/destination pair) has been extended, we create triplets composed of two lanes in succession which represent (1) a loaded movement and (2) the necessary follow up movement to position for the next load. The triplet provides a natural way of addressing the stochastic demand. The termination point of a triplet in a route always corresponds to the initial point of the subsequent triplet.; The value of this research exists in the presentation of a new model formulation of the TRP which integrates count data analysis into the approach while taking into account real-world constraints. The movement of freight in the TRP is modeled more intuitively using triplets, resulting in greater applicability. This value of this approach is also seen in extensions of to other areas of supply chain management and network modeling.