Publication | Closed Access
A Centroid-Based Heuristic Algorithm for the Capacitated Vehicle Routing Problem
37
Citations
0
References
2011
Year
Cluster ComputingTransport Network AnalysisEngineeringCluster Construction PhaseDiscrete OptimizationOperations ResearchVehicle RoutingSweep AlgorithmSystems EngineeringLogisticsCombinatorial OptimizationTransportation EngineeringComputer EngineeringComputer ScienceCentroid-based Heuristic AlgorithmInteger ProgrammingCapacitated VrpRoute ChoiceNetwork Routing AlgorithmRoute PlanningBusinessVehicle Routing ProblemHeuristic Search
The vehicle routing problem (VRP) is famous as a nondeterministic polynomial-time hard problem. This study proposes a centroid-based heuristic algorithm to solve the capacitated VRP in polynomial time. The proposed algorithm consists of three phases: cluster construction, cluster adjustment, and route establishment. At the cluster construction phase, the farthest node (customer) among un-clustered nodes is selected as a seed to form a cluster. The notion of the geometrical centre of a cluster is introduced in this study to be utilized at the cluster construction and the cluster adjustment phases. The proposed algorithm has a polynomial time complexity of O(n2.2). Experimental results on Augerat benchmark dataset show that the proposed 3-phase approach can result in smaller distances than the Sweep algorithm in more cases.