Truck and trailer scheduling in a real world, dynamic and heterogeneous context

•Introduction of a new variant of Vehicle Routing Problem from a real-world application.•The problem is constrained, dynamic and uses a heterogeneous fleet of vehicles.•Description of a lightweight constructive solver capable of real-time dynamic optimization.•Assessment of the operational impact of the optimized schedules for a large haulage company.•Presentation of a methodology for company policy-making through simulation.

We present a new variant of the Vehicle Routing Problem based on a real industrial scenario. This VRP is dynamic and heavily constrained and uses time-windows, a heterogeneous vehicle fleet and multiple types of job. A constructive solver is developed and tested using dynamic simulation of real-world data from a leading Scottish haulier. Our experiments establish the efficiency and reliability of the method for this problem. Additionally, a methodology for evaluating policy changes through simulation is presented, showing that our technique supports operations and management. We establish that fleet size can be reduced or more jobs handled by the company.