Route Optimization in Telematics
Route optimization is highly valuable for fleet owners: it provides an opportunity for companies to plan, create, and analyze the most profitable and optimal route strategy for their fleets. Route Optimization option assists companies to efficiently target a wide range of issues they have to deal with during distribution and route planning.
The route optimization software is useful in the fleet management systems, located at the user’s end. It often includes GPS tracking capability and advanced reporting features, providing fleet owners with fuel-efficient route planning, reducing or preventing unplanned stops, and helps to set up a reliable and cost-efficient delivery network.
TSP: Idea and background
TSP stands for Travelling Salesman Problem that becomes exponentially difficult with the gradually increased amount of dots, or cities, the salesman had to visit.
TSP can be visualized using a graph, which is an abstract object containing a set of dots or circles for the vertices, joined by lines or curves for the edges, where the edges represent direct travel between the locations, represented by the dots. Each edge of a graph has a numerical value, associated with it, called a weight. So the task is to find the path with the shortest sum of weights. Weight of an edge also often called the “cost” of the edge. Therefore, in TSP traveling salesmen actually aimed at finding the route with minimum cost.
An example of the complete directed graph and relevant cost matrix that includes distances between each point (docks, cities, etc.) is shown on a left figure above. Zeros in the cost matrix mean that 2→3 and 3→2 distances are the same. If we go through all the possible case calculations here, then we will find out that the optimal path, in this case, is 1→3→2→4→1, and the minimum cost would be 7.
In a real-life TSP could be re-formulated and described as follows: suppose your clients have a set of customers and fleet vehicles for deliveries. In this case, we need to find a set of routes serving all customers at minimum cost. Here we’re facing the so-called Vehicle Routing Problem (VRP), which was for the first time introduced by G. B. Dantzig et al [6].
In a real-life scenario, VRP would naturally include some constraints, such as time window constraints (a time period during which service should start), the time between each pair of customers, duration of each customer visit. In addition, the solution ideally should account for driver breaks, fatigue rules, variable loading/unloading time. One may attempt to actually use those constraints to state a relation between variables (service start time intervals, customer visit duration, etc). This is a nice point and the idea behind so-called Constraints Programming (CP).
In a constraint programming paradigm, the relations between variables are stated in the form of constraints. Constraints specify the properties of the solution to be found, rather than a step or step sequence to execute.
Get Shamil Mirkhanov’s stories in your inbox
Join Medium for free to get updates from this writer.
The solution of VRP is essentially a route optimization. Route optimization in this scenario defines a process of finding a most cost-efficient route, that takes into account various relevant factors like, for example, departure/arrival time slots, effective loading, and number as well as the location of all the stops on the route.
In a real-life case, route optimization could be potentially performed using the following methods:
- using some of the available “solvers” (not all of them are practical and accurate enough)
- using various fleet management software (constraints satisfaction problems, not all of it includes efficient route optimization)
- hire an expert to do it for you (time/money consuming, not always possible, accuracy issues)
- It is also possible to combine these methods with each other and suggest more of them (requires skills, experience, time/money).
Smart Route Optimization: a real-life example
Navixy Telematics Platform utilizes smart algorithms combined with advanced features of constraint programming and multi-purpose meta-heuristic techniques to account for everyday fleet management needs and addressing VRP in a highly efficient and customer-beneficial way.
By simply clicking on the route optimization button, a dispatcher will instantly get the optimal sequence of locations to visit on the map. One-click and all the points line up in the most effective route.
The driver will receive the already optimized route on the smartphone: a list of places to visit in the established sequence, as well as the shortest route from point to point. All the driver has to do is follow the route displayed on the mobile device.
Such Smart Route Optimization allows to significantly increase productivity and efficiency of the fleet while reducing costs, however, it is a quite difficult option to realize in a precise, efficient, and useful way.
Nowadays, there is a broad range of algorithms collections, vehicle routing libraries, and specially developed solvers available to target VRP and related challenges.
Original publication: https://www.navixy.com/blog/smart-route-optimization-in-fleet-telematics
