View article

This paper deals with the Delivery Territory Design Problem (DTDP), a districting problem that often occurs in delivery operations. The goal of the problem is to construct clusters of nodes (territories) such that the maximum diameter of a territory is minimized, while the territories designed are balanced w.r.t. some performance measures. We propose to solve the DTDP using a Probabilistic Variable Neighborhood Search (ProbVNS) algorithm based on two local search procedures: a tailored randomized shake procedure that targets both a reduction of infeasibility and diversification, and a deterministic local search based on a linear combination of objective and constraint violation. In addition to searching in different neighborhoods, the ProbVNS also changes the search direction by exploring different penalties for violating constraints. Numerical experiments show that ProbVNS outperforms a recent GRASP with the …