A Genetic Based Scheduling Algorithm for the PHSP with Unequal Batch Size Inbound Trailers

Abstract

This paper considers the parcel hub scheduling problem (PHSP) with unequal batch size inbound trailers, which is a combinatorial optimization problem commonly found in a parcel consolidation terminal in the parcel delivery industry (PDI). The problem consists of processing a large number of inbound trailers at a much smaller number of unload docks. The parcels in the inbound trailers must be unloaded, sorted and transferred to the load docks, and loaded onto the outbound trailers. Because the transfer operation is labor intensive and the PDI operates in a time-sensitive environment, the unloading, sorting, transferring, and loading of the parcels must be done in such a way as to minimize the timespan of the transfer operation. A genetic algorithm is used to solve the PHSP. An experimental analysis shows that the algorithm is able to produce solution results that are within 17% of the lower bound, 16% better than a competing heuristic, and 24% better than random scheduling.