Transportation businesses reduce costs by optimizing the routes of their trucks. However, determining optimal truck schedules is computationally intensive, running for hours on sequential computers. This article describes experience with parallelizing SAP's Vehicle Scheduling and Routing Optimizer on shared-memory multicore computers. Re-engineering this complex application for a 24-core machine reduced typical computation time on real data from 1.5 hours to 5 minutes. The article discusses successful and unsuccessful parallelization approaches and concludes with lessons learnt.