Track: Operations Research

Abstract

This study proposes a mathematical model and a hybrid metaheuristic (based on Greedy Randomized Adaptive Search Procedures and Tabú Search) for the distribution districting problem considering stochastic demand. The problem is inspired by a situation faced by a parcel company operating in Monterrey, Nuevo León México. The company desires to develop a strategic plan to district customers in pursuit of accomplishing two objectives: 1) balancing the average workload between districts (by minimizing the maximum workload content in a district), 2) creating compact districts, which is modeled as the minimization of the maximum distance between a pair of points in a district. . In González-Ramírez et al. (2017). As an extension and to incorporate the stochasticity of demand, we proposed to consider several representative days. We propose a single-objective optimization model in which we optimize the normalized weighted sum of the two objectives. As we are considering several demand scenarios, the proposed model minimizes the weighted sum of the maximum average workload content of each district (average over the demand days) and the compactness metric measured as the maximum time between the farthest away pair of points of a district. In order to normalize the parameters, we estimate the optimal allocation of workload among districts and the optimal compactness metric assuming a circular shape of districts. Furthermore, it is very important that the workload of the districts respect a maximum service time. Otherwise, the company has to pay extra time to the drivers. Given that this is a soft constraint, we model it as a third term in the objective function, penalizing the exceeding workload content of each demand day and district.  The proposed model was implemented in C++ and solved via CPLEX. Since it could be difficult to solve large instances to optimality, a multi-start hybrid metaheuristic is also developed, combining elements of GRASP and Tabu Search. At the construction phase, to generate multiple solutions, three heuristics to select a set of seeds are defined. The first heuristic selects the seeds among the most dispersed points. The second is based on a sweep algorithm, and the third one is very similar but considers the workload of each point. For each of the seed methods, a GRASP structured is implemented, randomly selecting the seeds from a restricted candidate list. Once the seeds have been selected, the remaining points are assigned to the districts that are closest and that are connected in the graph by an arc (which refers to the adjacency matrix of the graph).  With an initial solution constructed the second step considers a local search procedure in which the movements consider moving points between adjacent districts under a Tabu Search structure.

Preliminary results confirm the fact that the model presents limitations regarding the size of the scenarios solved, whereas the metaheuristic obtains high-quality solutions for larger instances in a reasonable amount of time.