Hybrid Particle Swarm Optimization for Two-stage Cross Docking Scheduling

Hairu Zhao, Ling ChenInternational Journal of Hybrid Information Technology 2015 · DOI

Abstract: In order to improve supply chain's operation efficiency, shorten delivery time and decrease distribution costs, two-stage cross docking scheduling problem under direct shipment mode was studied in this paper. Taking into consideration the influence of numbers of vehicles in distribution center on cross docking problem, three models were established based on different assumptions including only one vehicle in distribution center, many vehicles in distribution center and the location of distribution center to be determined, and the objective was to minimize transportation time. Hybrid particle swarm optimization was proposed to solve the model on the basis of PSO and GA. The algorithm introduced clone selection operator to make particles multiply and mutate by calculating the affinity between individuals so that the best individual can be reserved and the poor can be improved. Clone operator, crossover operator, antibody reorganization operator and mutation operator were designed to improve the performance of the algorithm. Computational experiments showed that the hybrid particle swarm optimization algorithm has faster convergence speed and better solution precision compared with other algorithms. The result of the present work implied that the model in this paper was accord with the reality, and it was effective and feasible.

Introduction: The Cross-Docking Challenge

In modern supply chains, cross-docking is a high-efficiency strategy where products from suppliers are moved directly to outbound trucks with little to no storage time in between. While this slashes inventory costs, it creates a massive scheduling headache: how do you coordinate dozens of inbound and outbound vehicles to ensure no one is waiting and transportation time is minimized?

The authors identify a gap in existing literature: most models assume a single vehicle or a single dock door. In reality, distribution centers manage fleets. This paper tackles the Two-Stage Cross-Docking Scheduling Problem under three increasingly complex scenarios:

  1. A single vehicle operating in both stages.
  2. Multiple vehicles operating in both stages.
  3. Multiple vehicles where the optimal location of the distribution center itself must also be determined.
Basic schematic of a two-stage cross-docking system showing the flow from suppliers to customers.

This is an NP-hard problem, meaning as the number of suppliers and customers grows, finding the absolute "best" schedule becomes computationally explosive.

Methodology: Mapping Logistics to Flow Shop Scheduling

The researchers transformed the logistics problem into a two-stage flow shop scheduling model, treating delivery vehicles like machines and pickup/delivery times like processing tasks. This mapping allows the application of established manufacturing optimization theories to the logistics domain.

Comparison of terminology between cross-docking vehicle scheduling and two-stage flow shop scheduling.

To solve this model, they proposed a Hybrid Particle Swarm Optimization (HPSO) algorithm. Standard PSO is efficient at finding solutions quickly but often gets stuck in "local optima." Genetic Algorithms (GA) are better at exploring the whole search space but converge slowly. The HPSO bridges this gap using:

  • Clone Selection Operator: Inspired by the human immune system, this calculates the "affinity" (fitness) of particles. High-performing particles are "cloned" and mutated, allowing the algorithm to aggressively exploit the best areas of the search space.
  • Antibody Reorganization: This operator periodically reshuffles the population into new subgroups to maintain diversity and prevent the "premature convergence" that plagues standard GA.
  • Crossover and Mutation: Traditional GA techniques are integrated to ensure the algorithm continues to explore new, potentially better scheduling sequences.

Experimental Results

The study relies on simulated computational experiments with 21 suppliers and 10 customers. In all tests, the HPSO algorithm outperformed standard PSO and GA in both speed (iterations required) and solution quality (minimum distance found):

  • Model 1 (Single Vehicle): HPSO found the optimal solution (201.94 km) in just 5 iterations. Standard PSO got stuck at 237.88 km, and GA took 21 iterations.
  • Model 2 (Multiple Vehicles): HPSO achieved a solution of 280.48 km in 48 iterations. PSO was significantly worse (342.79 km), and GA required 140 iterations to converge.
  • Model 3 (Location Optimization): When tasked with finding the best spot for the distribution center, HPSO reached a solution of 251.02 km in 43 iterations, again beating both baseline algorithms in precision and efficiency.

Discussion and Conclusion

The "aha moment" of this research is that neither PSO nor GA is sufficient alone for high-dimensional logistics problems. The addition of the clone selection operator acts as a middle ground—it is more targeted than random mutation but more diverse than standard PSO movement. By mapping cross-docking to flow shop scheduling, the authors leverage decades of manufacturing optimization theory for modern "just-in-time" logistics.

While the results are promising, the paper operates under several simplifying assumptions, such as zero dwell time for sorting and a focus on direct shipment only. Future research could integrate real-world constraints like traffic disruptions or explore performance in larger, more complex "many-to-many" delivery networks.

Summary updated

Abstract

In order to improve supply chain's operation efficiency, shorten delivery time and decrease distribution costs, two-stage cross docking scheduling problem under direct shipment mode was studied in this paper. Taking into consideration the influence of numbers of vehicles in distribution center on cross docking problem, three models were established based on different assumptions including only one vehicle in distribution center, many vehicles in distribution center and the location of distribution center to be determined, and the objective was to minimize transportation time. Hybrid particle swarm optimization was proposed to solve the model on the basis of PSO and GA. The algorithm introduced clone selection operator to make particles multiply and mutate by calculating the affinity between individuals so that the best individual can be reserved and the poor can be improved. Clone operator, crossover operator, antibody reorganization operator and mutation operator were designed to improve the performance of the algorithm. Computational experiments showed that the hybrid particle swarm optimization algorithm has faster convergence speed and better solution precision compared with other algorithms. The result of the present work implied that the model in this paper was accord with the reality, and it was effective and feasible.
BibTeX
@article{zhao2015hybrid,
  author = {Hairu Zhao and Ling Chen},
  title = {{Hybrid Particle Swarm Optimization for Two-stage Cross Docking Scheduling}},
  journal = {International Journal of Hybrid Information Technology},
  year = {2015},
  doi = {10.14257/ijhit.2015.8.11.21},
}
Figure