Variable neighborhood search for multi-objective resource allocation problems

doi:10.1016/j.rcim.2012.04.015

2013-06-01

PRE

Yun-Chia Liang *

DOI：10.1016/j.rcim.2012.04.015

原文链接

原文求助

摘要

En 中文

The Resource Allocation Problem (RAP) is a classical problem in the field of operations management that has been broadly applied to real problems such as product allocation, project budgeting, resource distribution, and weapon-target assignment. In addition to focusing on a single objective, the RAP may seek to simultaneously optimize several expected but conflicting goals under conditions of resources scarcity. Thus, the single-objective RAP can be intuitively extended to become a Multi-Objective Resource Allocation Problem (MORAP) that also falls in the category of NP-Hard. Due to the complexity of the problem, metaheuristics have been proposed as a practical alternative in the selection of techniques for finding a solution. This study uses Variable Neighborhood Search (VNS) algorithms, one of the extensively used metaheuristic approaches, to solve the MORAP with two important but conflicting objectives minimization of cost and maximization of efficiency. VNS searches the solution space by systematically changing the neighborhoods. Therefore, proper design of neighborhood structures, base solution selection strategy, and perturbation operators are used to help build a well-balanced set of non-dominated solutions. Two test instances from the literature are used to compare the performance of the competing algorithms including a hybrid genetic algorithm and an ant colony optimization algorithm. Moreover, two large instances are generated to further verify the performance of the proposed VNS algorithms. The approximated Pareto front obtained from the competing algorithms is compared with a reference Pareto front by the exhaustive search method. Three measures are considered to evaluate algorithm performance: D1(R), the Accuracy Ratio, and the number of non-dominated solutions. The results demonstrate the practicability and promise of VNS for solving multi-objective resource allocation problems. (C) 2012 Elsevier Ltd. All rights reserved.

Keyword:

Variable neighborhood search

Multi-objective resource allocation problem

Pareto front