# Hybrid Approach to the Cost Estimation of External-Fleet Full Truckload Contracts
## 3 Clustered kNN Shipping-Cost Estimation
### DBSCAN Clustering  
The rationale for the location clustering is simple. There are two main reasons: one is process oriented, while the second derives from the applied kNN estimation method. The transportation cost mainly depends on the route. The database shows that there are many pickup/unloading locations close to each other. From that perspective, there is a minor (or even no) difference between the route between Dortmund and Sopot and that from Gdansk to Bochum. The exact locations differ; however, the direct transportation cost difference is marginal. Therefore, it seems inefficient to keep an exact start/end location, and it is worth it to merge similar routes.  
The second reason comes from the selected kNN estimation. Its efficiency depends on a number of neighbors. Therefore, one expects to have many similar orders to select the most relevant ones. A review of the available data reveals that there are many close-by locations. Therefore, there are dozens of different routes starting and ending close to each other. Clustering such location merges different routes (orders) and then the estimation obtains more appropriate data examples for finding the most similar neighbors for a new route. It allows one to estimate the cost for totally new locations, as long as they lie close to the already exiting ones. Modified DBSCAN addresses that issue.  
Data clustering was performed in two steps. At first, the main clusters were evaluated using the classical DBSCAN procedure with the following parameters: \(\epsilon=7\) [km] and \(n=100\). Figure 3 shows the obtained initial clusters and Figure 4 the centers. The locations considered as noise, i.e., not assigned to any cluster, are not shown, as they were taken into account by further manual clustering (as there were no relevant historical data).  
Figure 3: Clusters assigned using DBSCAN together with enlarged cluster in Warsaw (PL) area.  
It is worth noting that these clusters reflect real road positions and clustered locations frequently follow the road patters lying along them. As one may notice, the clustering does not fill the entire map with assigned clusters and leaves empty map regions without an assigned group. This issue was addressed using custom manual clustering. Empty regions were filled with the manually set centers of attraction (see Figure 4), which represent additional MANUAL clusters for regions without order histories. In such a way, the clustering was completed. Each estimated location can be assigned to the nearest cluster, i.e., the DBSCAN one or to the MANUAL one.  
Therefore, each ordered route was defined by two labels indicating start/end clusters and was characterized by the route length. The **RoutLength** is evaluated as the distance between the centers of both clusters. Once the estimation was run, each new pickup/unload location could be assigned to the nearest cluster. As there always might appear some erroneous data, it was checked against the distance threshold \(d_{max}\) (maximum distance from the nearest cluster). If some new location exceeded this maximum distance, it was considered as erroneous and the associated route cost was not estimated.