In the paper the optimization problem of parcel delivery is considered. This belongs to the family of Multi-Commodity Network Flow Problems (MCNF). The problem is characterized by a significant number of incorporated business requirements (different vehicles types and transport routes, due dates, multiple transit stations, etc.) together with a wide data scope covering thousands of post offices across a country and millions of daily parcels which both lead to a large problem size. The problem is formulated in terms of a Mixed Integer Linear Program with over 3 billion variables and over 800 thousand constraints. A heuristic-based approach in conjunction with the use of a state-of-the-art MIP solver is proposed to solve real-life problem. Computational results demonstrates that the designed heuristic search is able to provide good solutions for large-scale instances of the MCNF in a reasonable time.