In 2019, a USA hauling company asked us for help with optimizing routes of their trucks.
The first case is that they have some scheduled shipments. Trucks move from the company depot to pick up cargo and then haul it to a specified destination. Then they return to the city where the company is situated. To not simply burn fuel in vain, it is desired to accomplish another hauling that would go on the way from the original destination to the company depot.
Several questions arise when looking for an opportunity to optimize fuel consumption. Is it worth taking a detour to pick up cargo from a city that is not on an optimal back route? Maybe travel distance increases so much that it will still be more efficient to just return an empty truck? If several vehicles were involved in the original trip, can we split them and assign each vehicle to pick up a different shipment? Should we wait a day in the destination city so that a new shipment will become available? Also, other constraints must be taken into consideration – trucks have weight and speed limits, both direct and back shipments have limitations on pick up and delivery dates, it’s not allowed to make more than two stops on the back trip, etc.
The second case is a logical development of the first one – when the company has available trucks and wants to find the most profitable shipment, perhaps with the possibility of making a backhaul.
The problem of routing optimization itself is very common and can be classified as a TSP (traveling salesman problem) with specific limitations. There are developed algorithms to solve such problems with good results for practical usage. For real-life scenarios with a small number of analyzed data, main efforts go into accounting custom limitations. Another potential improvement is to consider all vehicles fleet together and optimally allocate shipments between them. This would be a transformation into VRP – vehicle routing problem.
So, we have implemented a variant of well-known algorithms, adjusted for the client’s needs. For interaction with a user, developed a site on .NET Core MVC with Bootstrap 4. It shows the best of analyzed routes to a customer and allows selecting the most preferred one. Integration with Google Maps API was done for retrieving the shortest distances between cities and visual representation of the found routes.