The article characterizes the issues of service point clustering for the vehicle routing problem. Selected clustering methods described in the subject literature are discussed. A service point clustering algorithm is proposed to reduce the computational complexity of the vehicle routing problem.1. INTRODUCTION
The Vehicle Routing Problem (VRP) is an extension of one of the oldest optimization problems on networks – the Traveling Salesman Problem (TSP), which consists of visiting each of the selected locations exactly once and returning to the location from which the journey began
[7]. The travel costs between each pair of locations are known. The salesman must plan a route in such a way that he can visit each location exactly once and the total cost of the journey is as low as possible. In its simplest form, the vehicle routing problem differs from the traveling salesman problem by additional constraints related to the number and capacity of vehicles [1].
The vehicle routing problem, like the traveling salesman problem, is an NP-hard problem, i.e., there are no exact algorithms for this problem that solve it in time depending polynomially on the number of analyzed data. A proof of the NP-hardness of the vehicle routing problem can be found in [9]. The complexity of the vehicle routing problem is of the order O(n-1!), where n denotes the number of points to be visited. The computation time grows exponentially with respect to the number of data (in this case, with respect to the number of visited points, cities). For example, for a case with 15 cities, the number of possible route combinations will be 87,178,291,200, and for 20 cities, this number will increase almost 1.4 million times to a value of 1.21645*10^17. For a computer performing a million operations per second, the computation time for 20 cities would be almost 4,000 years.
Due to the relatively long computation time, researchers focus on finding approximate (heuristic) algorithms that would provide satisfactorily good results in an acceptable time. One way to achieve this goal is to reduce the complexity of the considered vehicle routing problem case. In the literature, this goal is achieved by using so-called two-phase methods: cluster first/route second, route first/cluster second (ang. (…)
The article contains 16,068 characters.
Source: Logistyka Magazine 2/2012
Clustering algorithm applied to the vehicle routing problem – PDF file for download







