Heuristic for a Real-life Truck and Trailer Routing Problem

In this paper we suggest a multi-start greedy heuristic for a real-life truck and trailer routing problem. The considered problem is a site dependent heterogeneous fleet truck and trailer routing problem with soft and hard time windows and split deliveries. This problem arises in delivering goods from a warehouse to stores of a big retail company. There are about 400 stores and 100 vehicles for one warehouse. Our heuristic is based on sequential greedy insertion of a customer to a route with further improvement of the solution. The computational experiments are performed for real-life data. We also provide a mixed integer linear programming formulation for precise and clear description of the problem.