The efficient and accurate logistics scheduling problem has become the bottleneck that impedes the e-commerce development of China. Cloudbased logistics can achieve resource sharing and centralized logistics scheduling, which is expected to fundamentally solve the problems encountered in logistics scheduling. However, the current research about cloud logistics scheduling is only the beginning. Most methods based on exact algorithms and heuristic scheduling algorithms are timeconsuming and inefficientwhile efficient scheduling algorithmis relatively scarce. This article takes cloud logistics scheduling problemas a NP-hard problem with multi-constraint and multi-objective decision making and establishes a multi-objective optimization cloud logistics scheduling model. K-means algorithmis used to cluster large and complex distribution network, but due to the load balancing problem in practical application, we useWK-means cluster which take the weight as an external constraints to balance the workload between each cluster. Large-scale VRP problem will eventually be divided into point-to-point TSP problemwhich we can use the branch-bound to solve and optimize. Simulation results show that the proposed scheme is more accurate and efficient than the existing typical heuristic scheduling method.