A Heuristic for Solving the Maximum Dispersion Problem

Mahdi Moeini () and Oliver Wendt ()
Additional contact information
Mahdi Moeini: Technical University of Kaiserslautern
Oliver Wendt: Technical University of Kaiserslautern

A chapter in Operations Research Proceedings 2016, 2018, pp 405-410 from Springer

Abstract: Abstract In this paper, we investigate solving the Maximum Dispersion Problem (MaxDP). For a given set of weighted objects, the MaxDP consists in partitioning this set into a predefined number of groups, such that the overall dispersion of elements, assigned to the same group, is maximized. Furthermore, each group has a target weight and the total weight of each group must be within a specific interval around the target weight. It has been proven that the MaxDP is NP-hard and, consequently, difficult to solve by classical exact methods. In this work, we use variants of Variable Neighborhood Search (VNS) for solving the MaxDP. In order to evaluate the efficiency of VNS, we carried out some numerical experiments on randomly generated instances. The results of the VNS is compared with the solutions provided by the solver Gurobi. According to our results, the VNS gives high quality solutions for small instances and, in solving large instances, it provides some decent solutions for all instances; however, Gurobi fails to provide any solution for some of them.

Keywords: Maximum Dispersion Problem (MaxDP); Variable Neighborhood Search (VNS); Solver Gurobi; Target Weight; High Quality Solutions (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-319-55702-1_54

Ordering information: This item can be ordered from
http://www.springer.com/9783319557021

DOI: 10.1007/978-3-319-55702-1_54

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().