Title: Package balancing k-means algorithm for physical distribution

Authors: Yinglong Dai; Wang Yang; Guojun Wang

Addresses: School of Information Science and Engineering, Central South University, Changsha, 410083, China ' School of Information Science and Engineering, Central South University, Changsha, 410083, China ' School of Computer Science and Educational Software, Guangzhou University, Guangzhou, 510006, China; School of Information Science and Engineering, Central South University, Changsha, 410083, China

Abstract: As the express delivery service is flourishing, it is a challenge to assign a set of tasks to a set of carriers, as it has to aggregate the neighbour tasks to a carrier and keep the loads of carriers balanced simultaneously. K-means clustering algorithm is an effective way to split the delivery tasks. However, it cannot solve the load balancing problem. This paper proposes an extended clustering algorithm - package balancing k-means. It adding the weight metric to the standard k-means algorithm to achieve load balancing. Analyses and experiments show that package balancing k-means can solve the load balancing clustering problem efficiently. Moreover, experiments show that the extended algorithm can achieve faster convergence.

Keywords: clustering; k-means; logistics; physical distribution; load balancing.

DOI: 10.1504/IJCSE.2017.084687

International Journal of Computational Science and Engineering, 2017 Vol.14 No.4, pp.349 - 358

Received: 12 Oct 2015
Accepted: 12 Jan 2016

Published online: 21 Jun 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article