Methods for bi‐objective routing and districting problems

Abstract Districting and routing are crucial components in optimising transportation systems and complex logistics operations. Combining these components helps companies efficiently deliver goods worldwide, reducing costs and improving service levels. The present study contributes to the field by proposing an exact solution method for addressing a bi‐objective problem, involving both districting and routing decisions. The problem tackled involves partitioning a set of customers into districts and determining routes to meet their demands. It is known as the capacitated vehicle routing and districting problem (CVRDP), which combines the capacitated vehicle routing problem (CVRP) with districting. There is one route per district, and every route starts and ends at a single depot, visiting the customers of the district exactly once. Vehicles must meet customer demands while respecting capacity constraints. The bi‐objective problem aims to minimise the total travel time and district's dispersion. Four mixed‐integer linear programming models are proposed, differing in their approach to prevent subtours. These models include the Improved Miller‐Tucker‐Zemlin (MTZ) and Single Commodity Flow (SCF) models, with both the disaggregated and the aggregated versions. The study applies the augmented ‐constraint method to find the, frequently named as, Pareto front. In the computational experiments, adapted instances from the literature are used in a four‐phase analysis, where the number of districts is predetermined. Overall, the disaggregated SCF model outperforms the other models. This model also stands out as the best option for optimising in a single objective problem, specifically in terms of achieving compact districts and minimising the total travel time.