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

Document Type : Research Paper


Mississippi State University-Meridian, 1000 Highway 19 North, Meridian, MS 39307-5799


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.


Main Subjects

[1] Bartholdi J., Gue K. (2000), Reducing Labor Costs in an LTL Crossdocking Terminal; Operations Research 48(6); 823-832.
[2] Basset M., Pekny J., Reklaitis G. (1995), Decomposition Techniques for the Solution of Large-Scale Scheduling Problems; American Institute of Chemical Engineering Journal 42(12); 3373.
[3] Felix Ammah-Tagoe (2006), Freight in America: A New National Picture; Research and Innovative Technology Administration, Bureau of Transportation Statistics; Washington, DC.
[4] Gilbert D. (1934), Parcel Conveyors; Post Office Electrical Engineers’ Journal 27(3); 179-186.
[5] Goodison H. (1981), Parcel Sorting Systems and Ancillary Postal Equipment; Post Office Electrical Engineers’ Journal 74(3); 271-277.
[6] Goldberg D. (1989), Genetic algorithms in search, optimization, and machine learning; Addison-Wesley: Reading; MA.
[7] Gould L. (1991), Increase Productivity by Choosing the Right Sortation Conveyor; Modern Materials Handling 46(7); 54-56.
[8] Graham R.L. (1969), Bounds on Multiprocessing Timing Anomalies; SIAM Journal of Applied Mathematics 17(2); 416–429.
[9] Gue K. (1996), Freight Terminal Layout and Operations; Doctoral dissertation, Georgia Institute of Technology, 1995; (Dissertation Abstract International, B56/11, 6322-6432).
[10] Haupt R., Haupt S. (1998), Practical Genetic Algorithms; New York: John Wiley & Sons.
[11] Khmelnitsky E., Kogan K., Maimon O. (2000), A Time-Decomposition Method for Sequence-Dependent Setup Scheduling under Pressing Demand Conditions; IEEE Transactions on Analytical Control 45(4); 638-652.
[12] Lai J. (2007), Surrogate search: A Simulation Optimization Methodology for Large-Scale Systems; Doctoral dissertation, University of Pittsburgh, 2006; (Dissertation Abstracts International, B67/08, 205-364).
[13] Masel D., Goldsmith D. (1997), Using a Simulation Model to Evaluate the Configuration of a Sortation Facility; Proceedings of the 29th Winter Simulation Conference; Atlanta, GA: IEEE Computer Society, 1210-1213.
[14] Masel D. (1998), Adapting the Longest Processing Time Heuristic (LPT) for Output Station Assignment in a Sortation Facility; Proceedings of the 7th Industrial Engineering Research Conference, Phoenix, Arizona: IIE.
[15] McWilliams D. (2009), Genetic-Based Scheduling to Solve the Parcel Hub Scheduling Problem; Computers and Industrial Engineering 56(4); 1607-1616.
[16] McWilliams D., Stanfield M., Geiger C. (2008), Minimizing the Completion Time of the Transfer Operations in a Central Parcel Consolidation Terminal with Unequal-Batch-Size Inbound Trailers; Computers and Industrial Engineering 54(4); 709-720.
[17] McWilliams D., Stanfield M., Geiger C. (2005), The Parcel Hub Scheduling Problem: A Simulation-Based Solution Approach; Computers and Industrial Engineering 49(3); 393-412.
[18] Rohrer M. (1995), Simulation and Cross Docking; Proceedings of the 1995 Winter Simulation Conference; IEEE Computer Society, 846-849.