# Hybrid Approach to the Cost Estimation of External-Fleet Full Truckload Contracts
## 2 FTL Cost-Estimation Models
### Algorithms Used in Estimation
#### 2.2.2 DBSCAN Clustering  
There are so many clustering algorithms that discussing each of them is an impossible task. They differ mainly in the way of data processing, application, as well as the very definition of the concept of a group [24; 25]. In general, clustering algorithms can be divided as follows:  
* iterative optimizing algorithms, like k-means or k-medoids [26];
* hierarchical, organized in _bottom-up_ or _top-down_ ways;
* density-based clustering, like DBSCAN, OPTICS or DENCLUE;
* grid algorithms, such as, for instance, STING or WaveCluster;
* algorithms based on a data model, like COBWEB. The DBSCAN, as mentioned earlier, is an algorithm included in the class of density algorithms [27]. Among the biggest advantages of this algorithm are finding groups of different, even complex, shapes, not only spherical, and finding groups surrounded by other clusters. They also cope well with noisy data and do not need to provided with the number of groups to be found--the algorithm finds them by itself. DBSCAN takes two parameters as input. The first is the minimum number of points required to form a group, denoted as \(n\), while the second is the maximum radius of the neighborhood \(\epsilon\). The neighborhood itself, shown in Equation (5), is the set of points \(D\) lying at a distance less than or equal to \(\epsilon\) from a given point \(p\) and is defined as  
\[N_{\epsilon}(p)=\{q\in D:d(p,q)\leq\epsilon\}, \tag{5}\]  
where \(d(p,q)\) denotes the distance between \(p\) and \(q\). The core point presented in Equation (6) is a \(p\) such that in its \(\epsilon\) neighborhood, there are at least \(n\) points  
\[|N_{\epsilon}(p)|\geq n. \tag{6}\]  
The border point is such a point that is not a core but is reachable from another core. Point \(p\) is called directly density-reachable if \(p\in N_{\epsilon}(p)\) and \(|N_{\epsilon}(p)|\geq n\). Point \(p\) is called density-reachable from point \(q\) if there exists such a set of points \(p_{1}\ldots p_{n},p_{1}=q,p_{n}=p\) and each \(p_{i+1}\) is reachable from point \(p_{i}\). A point \(r\) is density-connected with point \(q\), if there exits such a point \(p\) that both points \(r\) and \(q\) are reachable from point \(p\). A cluster is such a subset of all points under consideration that meets the following conditions: * If point \(p\) belongs to a group and point \(q\) is reachable from it, then point \(q\) also belongs to that group. * If two points belong to the same group, they are densely connected. A noise is a subset of all points from the database that do not belong to any group found. The DBSCAN consecutively reviews all the yet-unvisited (unclassified) points. For each of them, the method checks the number of all points in its neighborhood. If the number of such points is less than the \(n\) parameter, the point in question is temporarily marked as noise and the algorithm takes another of the points not yet reviewed. Otherwise, a new group consisting initially of points from the surroundings of the current core (the set of seeds) is created. For each point belonging to the seed set, the number of neighbors is checked. If this number is greater than or equal to \(n\), all points not previously visited from the neighborhood of the point under consideration are added to the seed set and, so, the cluster is expanded. If, in such a neighborhood, there are points previously marked as noise, they will be added to the cluster. Its expansion ends when all points from the seed set have been examined. In addition to its advantages, DBSCAN also has disadvantages. The algorithm is not entirely deterministic--its results depend on the order in which the data are viewed. A boundary point that is already assigned to one group can later be found in another, if it lies close enough to it. This situation, fortunately, is not frequent and, most importantly, does not have a big impact on the results of grouping. The detailed algorithm description can be found in [27]. In the considered case, DBSCAN is used in a spatial context, which is actually quite popular.