The Capacitated and Economic Districting Problem

Luis Henrique Pauleti Mendes (), Fábio Luiz Usberti () and Celso Cavellucci ()
Additional contact information
Luis Henrique Pauleti Mendes: Institute of Computing, University of Campinas, Campinas, São Paulo 13083-852, Brazil
Fábio Luiz Usberti: Institute of Computing, University of Campinas, Campinas, São Paulo 13083-852, Brazil
Celso Cavellucci: Institute of Computing, University of Campinas, Campinas, São Paulo 13083-852, Brazil

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2003-2016

Abstract: This paper presents the capacitated and economic districting problem (CEDP), which searches for the best edge partition defining connected, capacitated, and balanced districts in an undirected connected graph, weighing the economic value of each district. This problem provides a comprehensive description of the decision making on service networks districting, where the order by which the districts are serviced plays a role in the profit. This is observed in the arrangement of districts for meter reading, as the day in which each district is read impacts the revenue. Two integer linear programming formulations are proposed for CEDP, accompanied by a proof of N P -hardness. To tackle large instances, a greedy randomized adaptive search procedure (GRASP) metaheuristic, embedded with reactive parameter tuning, statistical filtering of solutions subjected to intensification, and a set of solution repairing procedures, is proposed. The GRASP is hybridized to each model to evaluate the outcomes of combining their individual merits. Computational experiments were performed on a new benchmark composed of 144 instances of different sizes, edge densities, network topologies, balance tolerances, and district capacities. The results show the effectiveness of the exact methodologies in solving the models and providing optimal solutions for the set of small instances. The GRASP was capable of tackling large networks, achieving feasible solutions to almost all instances. The results also show that the hybridized methodologies outperformed their standalone counterparts with respect to the attained primal and dual bounds.

Keywords: integer linear programming; metaheuristic; service network; meter reading; network design (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1180 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:4:p:2003-2016

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().