Fuzzy Clustering C-Means for solving Multi Depot Vehicle Routing Problems.
In this project, I developed a solution using Fuzzy C-means clustering to address a complex problem involving vehicle objectives represented as nodes. The main goal was to enable each node to belong to multiple clusters, a feature that is not possible with standard clustering techniques like K-Means. This flexibility is essential in solving the problem of assigning delivery vehicles or nodes to various clusters based on specific constraints.
Unlike traditional clustering methods, where each data point is assigned to exactly one cluster, Fuzzy C-means allows nodes to have partial membership in multiple clusters. This was necessary for the problem I was tackling, where a node (representing a vehicle or delivery location) requires the ability to move between clusters with shared parameters, such as load capacity and service limits. Each cluster represents a delivery zone or route, and the nodes (vehicles or couriers) need to be allocated to these zones while adhering to various constraints such as maximum load or capacity limits.
The problem I aimed to solve is related to the Vehicle Routing Problem (VRP), which is a classic NP-Hard problem in logistics. The VRP seeks to find the most efficient way to deliver goods, respecting vehicle capacities, delivery time windows, and other operational limits. In this case, the “courier” (vehicle) has a capacity limit, and needs to distribute packages across multiple delivery zones (clusters), each with its own set of constraints.
Using Fuzzy C-means allowed me to model this complexity more effectively, as each courier (node) could be associated with multiple delivery zones (clusters), reflecting the possibility of partial allocation and shared responsibilities across routes. This approach provided more flexibility and improved the overall efficiency of the delivery system.
To implement this solution, I used Microsoft Excel as the development platform. The project was designed with the following constraints:
- A maximum of 100 iterations to simulate the clustering process
- A maximum of 20 clusters
- A maximum of 200 nodes (representing couriers or vehicles)
These limitations were set to ensure that the computation remains manageable and can be executed within a reasonable time frame. Although the formulas behind the clustering process are not visible in the provided screenshots, they play a crucial role in driving the calculations and optimization steps. The formulas in Excel determine the membership values of each node in the clusters, the center of each cluster, and help track the changes in membership through each iteration, gradually refining the solution.
This project showcases the application of heuristic methods in optimization problems, specifically for solving logistical challenges like the Vehicle Routing Problem. The use of Fuzzy C-means allowed for an innovative approach to clustering that accommodates real-world complexities, providing a more flexible and accurate model for assigning vehicles to delivery routes with various constraints. This solution could be expanded to larger datasets and more complex problems in the future, making it a solid foundation for further optimization work in logistics and delivery management.
You can see the project
to see the Microsoft Excel.