# iRoute--An Adaptive Route Planning Solution for Commercial Vehicle Fleets
## 4 Proposed Historical Routing Algorithm  
Our former article [33] presented the prototype of the historical route optimization algorithm of the iRoute solution. At present, however, we have come to identify certain key variables that factor towards better results and thus propose that route optimization be done according to the following specific data: orders, customer locations, vehicles, work schedule, constraints, and route planning parameters. In this way, the segments that are repeated during a route will be identified and saved to improve the optimization algorithm. The iRoute solution proposes to optimize vehicle routes taking into account real constraints encountered by drivers day by day. Suppose route X has been driven many times (at least 10) by drivers with differences in terms of time, distance, or path used compared with the theoretically optimized route. In that case, it is very reasonable to expect that in practice the drivers will not use the proposed route due to their knowledge of local road conditions, style of driving (e.g., preferring extra-urban roads), or any other factors that will impact the total execution of the route. Or suppose they will be compelled to use the theoretical route. In that case, they will not be comfortable and they will try to point out at the end that the reason their execution was different from the plan is that the plan was not realistic. It lacked local conditions about the road network, traffic, community, and other factors. This is the reason that we wanted to use the historical tracks and give credit to the drivers for choosing the best route to deliver or collect the goods. Our new adapted route is supposed to minimize the differences between the plan and the execution, still  
Figure 9: High-level view of the optimization engine. offering a good enough plan to cover all the locations from the route. The final solution will also offer the dispatchers a way of validating the execution path or just segments of it so that the driver does not deliberately take a longer path just for his/her needs. The invalid historical segments will not be used in the adapted route algorithm. The similarity ratio between the route segments was calculated by using the Curve Matching library, which is based on the normalization of each curve with Procrustes analysis, and then calculating the Frechet distance between each of the curves. The proposed route optimization adjustment process is described below:  
* Obtain the input--orders, locations, vehicles, constraints--and call standard VRP 1. algorithms (VROOM) to obtain an initial optimized route for the data received. * Subsequently, for each segment (customer X to customer X + 1 locations) of the 2. standard route from Step 1: 1. Check if there is historical track information about the road path between customer location X and customer location X + 1; 2. Check whether we have a minimum of N such executed history track segments or not; Initially, N could be 10, but it will be a parameter, which can be adjusted time, after obtaining enough data; 3. For those N historical data trips, compare the segments and count the paths that are similar to an acceptable percentage (e.g., more than 90%), as the common road traveled from X to X + 1; 4. If we discover a majority of historical segments that are similar to the common path, the algorithm will check the common path with the current optimal segment (provided by the VROOM in Step 1): 1. If the common and optimized road segments are similar, then we keep the current optimized segment and we score positively the historical tracks for later reference; 2. If the common and optimized segments are not similar, the algorithm will overwrite the optimized segment between X and X + 1 with the common path from the historical routes. The algorithm will note in the metadata of the route that the segment (X, X + 1) was adjusted; 5.