Solving a rich vehicle routing problem with a heterogeneous fleet and trailers in medium-sized transport companies

Efficient route planning is a critical challenge for transport companies operating heterogeneous vehicle fleets. Manual planning often fails to leverage cost-saving consolidation opportunities, leading to suboptimal capacity utilization and increased operational costs. This paper addresses a real-world vehicle routing problem involving pickup and delivery tasks, heterogeneous vehicles and trailers, time windows, service equipment requirements, and labor constraints. We develop a matheuristic method that combines heuristic tour construction with exact optimization using a set partitioning model leveraging the manageable number of stops per tour.The proposed matheuristic is validated using real operational data from a medium-sized logistics provider based in Germany. Our experiments demonstrate that the matheuristic achieves average cost savings of 16.6% compared to historical plans, with solution times well under three minutes even for large instances. A comparison with a pure optimization model shows that while exact methods can yield marginally better solutions (up to 2–3% improvement), they are computationally impractical for real-time use. The matheuristic strikes a practical balance between solution quality and runtime, enabling automated, scalable, and cost-efficient routing for medium-sized transport companies with a heterogeneous fleet.