This study investigates an Urban Logistics Network (ULN) redesign problem arising in Clothing and footwear chain retailers’ O2O implementations. We built an optimization model aimed at minimizing the total city logistics cost considering online orders fragmentation, local distribution costs and other practical issues. To solve this model, we put forward an improved Lagrangian relaxation algorithm. The performance of this algorithm is verified by comparing with CPLEX. Our methodology is illustrated with the Urban Logistics Network under O2O from a leading clothing and footwear chain retailer (Daphne) in Chongqing. Numerical analysis indicates that the increase of online sales and the decrease of offline and the increased ratio of short distance distribution will lead to increasing total costs under the current structure of the stores. This study also examines the effects of changing parameter values on the optimal solutions and to points out some management implications, such retail format adjustment and store closing.