Creating balanced and connected clusters to improve service delivery routes in logistics planning

Abstract

A challenging problem in real world logistics applications consists in planning service territories for customer deliveries, in contexts where customers must be clustered into groups that satisfy various conditions such as balance and connectivity. In this paper we propose new algorithms for producing such clusters based upon special procedures for exploiting Thiessen polygons. Our methods are able to handle multiple criteria for balancing the clusters, such as the number of customers in each cluster, the service revenue in each cluster, or the delivery/pickup quantity in each cluster. Computational results demonstrate the efficacy of our new procedures, which are able to assist users to plan service personal service territories and vehicle routes more efficiently.

Keywords

Clustering / K-means / logistics / routing / Thiessen polygon

References

[1] Barreto S., Ferreira C., Paixao J., Santos B.S.. Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 2007, 179: 968-977.

[2] Blakeley F., Bozkaya B., Cao B., Hall W.. Optimizing periodic maintenance operations for Schindler Elevator Corporation. Interfaces, 2003, 33: 67-79.

[3] Braysy O., Gendreau M.. Vehicle routing problems with time windows, part I: route construction and local search algorithms. Transportation Science, 2005, 39: 104-118.

[4] Braysy O., Gendreau M.. Vehicle routing problems with time windows, part II: metaheuristics. Transportation Science, 2005, 39: 119-139.

[5] Dondo R., Cerda J.. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 2007, 176: 1478-1507.

[6] Estivill-Castro, V. & Lee, I. (2001). Fast spatial clustering with different metrics and in the presence of obstacles. In: GIS’01, 142–147, November 9–10, 2001

[7] Fan B.. A hybrid spatial data clustering method for site selection: the data driven approach of GIS mining. Experts Systems with Applications, 2009, 36: 3923-3936.

[8] Hruschka H., Natter M.. Comparing performance of feedforward neural nets and K-means for cluster-based market segmentation. European Journal of Operational Research, 1999, 114: 346-355.

[9] Huff D.L.. A probabilistic analysis of shopping center trade areas. Land Economics, 1963, 39: 81-90.

[10] Humair S., Willems S.P.. Optimizing strategic safety stock placement in supply chains with clusters of commonality. Operations Research, 2006, 54: 725-742.

[11] Karypis G., Kumar V.. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal of Scientific Computing, 1998, 20: 359-392.

[12] Kwon, Y.J, Kim, J.G., Seo, J., Lee, D.H. & Kim, D.S. (2007). A Tabu search algorithm using Voronoi diagram for the capacitated vehicle routing problem. In: Proceedings of 5^th International Conference on Computational Science and Applications, IEEE Computer Society, 480–485

[13] MacQueen J.B.. Some methods for classification and analysis of multivariate observations. Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, 1967, Berkeley: University of California Press 281-297.

[14] Strehl, A. & Ghosh, J. (2002). Relationship-based clustering and visualization for high-dimensional data mining. INFORMS Journal on Computing, 1–23

[15] Zhang B., Yin W.J., Xie M., Dong J.. Geo-spatial clustering with non-spatial attributes and geographic non-overlapping constraint: a penalized spatial distance measure. Proceeding of PAKKD’07, 2007, Berlin Heidelberg: Springer-Verlag 1072-1079.