Route optimisation algorithm: A multi-restriction problem

The company

This company operates in a B2B (business tobusiness) model, renting industrial equipment as their core business. In addition, the company provides technical assistance and field monitoring. The rental service includes delivery to the site and pickup at the end of the rental contract.

The industrial equipment rental market is very competitive; the current market supply dictates the price and so the company that wins is the one that offers the shortest delivery time to customers. The company manages around 1,000 pieces of equipment and over 200 models across five heterogenous families.

The challenge

Since transportation costs account for 8%of the revenue of the company, there must be a clear focus on an improvement plan that minimises this. In fact, 53% of the transportation expenditure is related to vehicle subcontracting. The process of planning deliveries and pick-ups directly is a major cause for the costs, therefore, the company must seek a better process that will positively impact savings.

The as-is transportation planning process faces many difficulties mainly due to the market demanding short response periods and machine complexity. Here are the main challenges:

• Due to the heterogeneity from both the rented machines and the fleet of trucks available, which all have very distinct areas and weights, the task of assessing which truck fits a certain route better is a complex task.
• The delivery sites characteristics also pose a big restriction, since they can either be in the city centre with a lot of traffic and where stopping is not permitted, or on the middle of a construction site with no proper roads.
• Typically, the planning team is preparing the operation at the end of the day to be executed in the first hour of the next day.
• The entire process is conducted manually and without the most important data that really impacts cost, such as the distance travelled, total working time and truck occupation, leading to highly demanding tasks - far from optimal solutions.
• There is a clear difficulty combining deliveries with pickups leading to empty return trips.
• The development of an algorithm that minimises transportation costs and takes into consideration all business restrictions is crucial to not only present a better solution but also to free up planning team time for complex assessments.

The approach

Finding the best routes for a fleet of vehicles based on a set of locations to visit, while fulfilling all the business restrictions, was the goal of the algorithm. Since the complexity of the problem increases exponentially with the number of locations to be visited, a classical optimisation approach is not feasible.

To search for all the possible combinations that guarantee us the best one, the necessary computer power and running time would be impracticable. Therefore, optimisation techniques like heuristics must be used to intelligently and efficiently search the solution space to find an ear-optimal solution.

The goal is clear: minimising cost which is composed by a fixed cost per car, the cost per km travelled, and finally a penalty cost for all the cases where a customer order was selected for planning, but could not be satisfied.

The algorithm takes into consideration relevant business restrictions for the operation:

Backhauls: route optimisation problems typically focus on reducing the cost of deliveries, but in this case, the return flow is as important. An inefficient return flow could not just represent more costs by doing empty trips, instead of using them to pick-up the finished rental contrast, but also the opportunity cost hidden, if the machine is waiting to be picked up, is not being rented to another client.[ch1] [CT2] 

Heterogeneous fleet: the 1,000 equipment pieces are heterogenous and because of this, the fleet is also heterogenous, meaning that only specific trucks can transport specific equipment - this adds another layer of complexity.

Site dependency: depending on the characteristics and restrictions of the delivery point only specific trucks can be used (docks, entry, city traffic).

After running the algorithm, not only to present the solution, but also to monitor the operation, a dashboard was developed where the main Key Performance Indicators (KPIs) were included as well as a visual map of the flow of the routes.

Achievements

The tools developed enabled the increase inoccupation rate of the cars from 45% to 65% and enabled a 21% decrease of the number of km travelled/year. These two accomplishments represent a transportation cost reduction of around €200,000.

Besides the calculated financial impact, there was an increase in the number of customers visited per day and, therefore, the service level increased. With a data driven process alongside our algorithm, there was a clear reduction in the effort of the logistics team in planning and the assessment of restrictions and proposals to fulfill daily.