We present local-improvement heuristics for a Service Network Design Problem encountered in the motor carrier industry. The scheduled set of vehicle departures determines the right hand side of the capacity constraints of the shipment routing subproblem which is modeled as a multicommodity network flow problem. The heuristics, one for dropping a scheduled service and another for introducing a new service, are based upon subgradients derived from the optimal dual variables of the shipment routing subproblem. The basis of the multicommodity network flow problem is partitioned to facilitate the calculation of the dual variables, reduced costs and subgradients. These are determined in large part by additive and network operations, and only in small part by matrix multiplication. The results of our computational experimentation are presented.