<![CDATA[Micro, Small, and Medium Enterprises (MSMEs) are vital to Indonesia's economy, yet many struggle with ineffective marketing strategies, as seen in Bintang Sepatu Purwokerto, an MSME shoemaker facing stagnant sales. To overcome this, this study proposed a metaheuristic-based clustering (MBC) algorithm combined with principal coordinate analysis (PCoA) for optimal customer segmentation. The developed algorithm successfully overcomes the limitations of Kmeans in mixed datasets, containing categorical and numeric data. Furthermore, the procedure for updating centroids in Kmeans that risks falling into a local optimum is also solved. In this study, six MBC algorithms were developed based on six state-of-the-art metaheuristic optimizations utilized. Then, the developed MBC algorithms are compared with benchmark algorithms, namely Kmeans and KmeansQLDE, based on the near-optimal clustering obtained, t-test, and required running time. The comparison results show that the MBC clustering using gray wolf optimization (GWOClustering) outperforms the benchmark algorithms, achieving an average Silhouette score of 0.7491. In addition, this algorithm significantly outperforms Kmeans based on t-test conducted and results in relatively low runtime. The GWOClustering simulation yielded four near-optimal clusters in the customer segmentation of Bintang Shoes Purwokerto MSME. The analysis of each cluster's characteristics indicates the need for distinct marketing strategies for this MSME. Marketing based on offline purchasing services, store conditions, and product layout is appropriate for consumers in Cluster 1. Meanwhile, digital marketing with attractive, informative graphic content is suitable for consumers in Clusters 2 and 4. Furthermore, strategies with competitive pricing, discounts, or bundling strategies are appropriate for Cluster 3.]]>
