The market competition of express package deliveries in Korea is severe because a large number of companies have entered into the market. This study thus suggests an approach to the reconfiguration of express service networks with respect to the strategy partnership of closing/keeping service centers among companies involved and the adjustments of their cutoff times. For this we propose an integer programming model and a genetic algorithm based solution procedure for allowing companies involved to maximize their incremental profit. An illustrative numerical example is presented to demonstrate the practicality and efficiency of the proposed model.