Recent trends in customer habits have greatly affected last-mile logistics, increasing the pressure to effectively serve an increasing demand. For traditional postal mail companies, this change is an opportunity to alleviate the decreasing role of conventional mail within society and to focus on new products and services. Unfortunately, these changes also affect the efficiency of their supply chains, which were focused on delivering letters. In this work we consider the last-mile reorganization problem as faced by Correos de Chile, the Chilean public postal service. While this work is mostly focused on the particular needs of the company, the approach applies to other scenarios where the work allocation can be modeled as a districting problem with multiple simultaneous objectives and special shape conditions on the districts. To solve the proposed model, a multi-criteria heuristic procedure based on a combination of different neighborhood structures, each geared towards specific characteristics of the problem, is put forward. The applicability of the approach on large-size real-life conditions is tested on instances derived from real life operations showing the applicability of the proposed method.