Parcels sent from origin customers to destination customers are always routed through consolidation/sorting facilities referred to as hubs. The movement of shipments from a hub to another is typically carried out either by ground or by air. Practically, all parcel distribution companies have full control of their ground vehicles (trucks and vans), which enables them to schedule their departure times in such a way to reduce the shipments’ journey. In contrast, only giant carriers can afford to have their own airplanes. Most small and middle size companies, which we are concerned with in this research, have to rely on commercial airlines for their air shipping and abide with the schedules decided by these companies. We propose a mixed integer formulation for the problem that optimizes the routing of the shipments (ground versus air) and the scheduling of their movements (departure times from customers and facilities). The model takes into account the variation of the flights (as offered by the airlines company) from day to day and from season to season while ensuring a regular pickup time for each origin customers and a regular delivery time for each destination customer (as the parcel company cannot change its commitment to its customers from day to day). A heuristic method based on valid constraints is proposed and successfully applied to a real-world problem.