| Truckload carriers are constantly faced with the problem of shipping truckloads of goods at minimal cost between pairs of cities or customers using a fleet of trucks located at one or more depots. While designing routes for the drivers, various real-world conditions must be considered. For instance, every truckload must be picked up between certain time windows only. Due to the presence of these time windows, a driver is forced to wait at a location if he arrives early for a pickup. In some situations the drivers are compensated at a certain hourly rate for waiting. The routes must also be designed in such a way that the Department of Transportation's (DOT) driving regulations are not violated. This problem appears in the literature as Vehicle Routing Problem with Full Loads, or in short, VRPFL.;This dissertation presents an exact algorithm based on the column generation approach to solve the VRPFL. This algorithm takes into consideration the time windows and waiting costs. The layovers, which is one of DOT's requirements is not considered in the exact algorithm. However, a procedure to incorporate them using this algorithm has been developed and tested.;The algorithm was coded and validated for accuracy. Various computational tests were performed and problems up to 100 loads were solved efficiently. A real-world problem was also tested successfully using this model. Finally several ideas for incorporating some real-world constraints are provided. |
