Load plan selection for package express fleets.

Abstract

A loader serves two roles during the loading process for package delivery. First, given a load plan, which is an assignment of regions to delivery vehicles, the loader takes each package to be delivered, one-by-one, reads the address, and assigns it to the proper vehicle, according to the load plan. Second, the loader can decide whether or not to change the load plan during the loading process. Changing a load plan involves the re-assignment of regions to vehicles and, when appropriate, removing packages from one vehicle and placing them on another vehicle. Moving already assigned packages takes time, delays fleet departure, and hence generates additional cost. However, load plan adjustment can better balance delivery workload, which reduces cost. The objective of the research presented is to aid the loader during the loading process in deciding whether or not the current load plan should be continued, and if not, identify a better load plan, assuming that the current package load of each delivery vehicle is known. The load plan selection process is modeled as a Markov decision process (MDP) and analyzed in Chapter 2. We present structured results for the expected cost-to-go function which lead to an improved algorithm for computing an optimal load plan policy. We describe the improved algorithm and compare it to traditional dynamic programming methods in Chapter 3. We present a heuristic, based on conditions for action elimination, that is computationally superior to the exact methods. In Chapter 4, we present a prototype decision support system (DSS) for load plan selection in package express. We develop a statistical model to reflect a more complex information state and describe the implementation of the statistical model in an actual operation. We model the load plan selection process for air packages and suggest a solution technique. Conclusions are presented in Chapter 5.