Definizione e realizzazione di metodologie di clastering con capacità limitata nell'assegnazione di stazioni di servizio a multi-depositi

Abstract

Questo lavoro affronta i Problemi di Clustering con Capacità (CCP), dove l'obiettivo è raggruppare efficientemente le stazioni e assegnarle a depositi appropriati, tenendo conto delle restrizioni di assegnazione e capacità. Ho proposto due metodi e, dopo esperimenti, li ho confrontati alla fine con il metodo di Programmazione Lineare Intera Mista (MILP) per decidere quale sia più adatto in base ai requisiti che potremmo avere.

Le soluzioni proposte per questa problematica sono due:

(1) La prima è fornita dall'algoritmo di clustering avido con vincoli di capacità. Utilizza un approccio avido, scegliendo azioni localmente ottimali in ciascuna fase per ottimizzare i costi di viaggio, assicurandosi che la capacità del deposito non venga superata. Per aiutarlo a prendere decisioni migliori, i richiedenti vengono riordinati in base alle loro distanze dai depositi, dando priorità alle stazioni più lontane dai depositi. L'algoritmo è stato creato per considerare sia la vicinanza spaziale che i vincoli di capacità del deposito.

(2) L'algoritmo K-means migliorato per il CCP, che si compone di due parti. Nella Parte 1, l'assegnazione è fatta dando maggiore priorità alle stazioni ad alta domanda, e vengono assegnate ai centroidi più vicini formando cluster di dimensioni uguali. Poi, nella Parte 2, anche i cluster di dimensioni uguali vengono assegnati al deposito più vicino in base alla distanza più breve, tenendo sempre conto dei vincoli di capacità dei depositi.

I metodi proposti si basano su algoritmi esistenti e introducono nuove modifiche adattate alle specifiche esigenze del clustering con capacità. Attraverso una valutazione approfondita, le proposte dimostrano la loro efficienza nel fornire una soluzione robusta per il CVRP, avanzando lo stato dell'arte nel clustering con capacità. Con il potenziale per un'allocazione efficiente delle risorse a basso costo e una pianificazione logistica migliorata, i metodi offrono soluzioni pratiche ed economiche per sfide reali ne

This work tackles the Capacitated Clustering Problems (CCP), where the objective is to efficiently group stations and assign them to suitable depots while taking assignment and capacity restrictions into consideration. I proposed two methods and after experiments I compared them in the end with the Mixed Integer Linear Programming (MILP) method to decide which is more suitable based on the requirements we might have.

The proposed solutions to this issue are two:

(1) The first one is provided by the greedy clustering algorithm with capacity constraints. It uses a greedy approach, choosing locally optimal actions at each stage to optimize travel costs while making sure that depot capacity is not exceeded. To help it make better decisions, requesters are reordered based on their distances to the depots, giving higher priority to stations that are further from the depots. The algorithm was created to consider both spatial proximity and depot capacity constraints.

(2) The improved K-means algorithm for CCP, which consists of two parts. In Part 1, the assignment is done by giving higher priority to high-demand stations, and they are assigned to their closest centroids by forming equal-sized clusters. Then, in Part 2, the equal-sized clusters are also assigned to their closest depot based on the shortest distance, always taking into account the capacity constraints of the depots.

The proposed methods build on existing algorithms and introduce fresh modifications tailored to the specific demands of capacitated clustering. Through extensive evaluation, the proposed approaches demonstrate their efficiency in providing a robust solution for CVRP, advancing the state of the art in capacitated clustering. With the potential for cost-efficient resource allocation and improved logistics planning, the methods offer practical and affordable solutions for real-world supply chain and logistics challenges.