Page 59 - IJOCTA-15-2

¨
D. Balpınarlı, M. Onal / IJOCTA, Vol.15, No.2, pp.245-263 (2025)

4.2.2. Local search evaluation procedure and As we will state in Section 4.2.3, we perform
moves the move and create the corresponding neighbor
only if the move is allowed (i.e. if it is not in the
Once the solution representation is defined, the tabu list). Out of the neighboring solutions ob-
neighborhood of a solution should be defined. tained with allowable moves, our algorithm picks
The neighborhood of a solution is the set of the solution with the highest objective function
all solutions that can be reached by some small value and moves to this solution (i.e., makes this
changes in the representation of the current solu- solution the current solution) even if the neigh-
tion. These small changes to the current solution boring solution has a lower objective function
are also called moves or movements. Consider a value than the current solution. Suppose none of
current solution represented by vector y. Every the neighboring solutions obtained with allowable
single move results in a change in y and creates a moves is feasible. In that case, the algorithm exe-
′
vector y , which is a representation of one of the cutes the following procedure, which is referred to
neighboring solutions. For instance, changing a as Infeasibility Procedure in Algorithm (2).
0 entry (in the setup vector y) to 1 can be con- It modifies the multiple item ELSIDD problem as
sidered as a move. It creates a representation y ′ follows:
of a neighboring solution. The objective function
value corresponding to such a representation is • introduces excess variables, e t ≥ 0, for
computed by solving the formulation of the multi- t = 1, . . . , T,
ple item ELSIDD problem by a commercial solver • modifies the capacity constraints (5) to
measure the excess in each period as in
where the y it variables are fixed to the values in
′
vector y obtained by such moves that correspond (29) below:
N
to that particular neighboring solution. Below, X
we list and describe the moves we implement to x it ≤ C t + e t , t = 1, . . . , T, (29)
explore the neighborhood of the current solution: i=1
P T
e
• changes the objective to min t=1 t .
• Removing/Inserting a production period: We are going to call this modified problem
For i = 1, . . . , N, t = 1, . . . , T, we check as ELSIDD-FEAS. Note that ELSIDD-FEAS has
elements y it of representing vector y of the an optimal objective function value of zero if
current solution. For some given i and t, and only if multiple item ELSIDD is feasible.
if y it = 1 (y it = 0), we evaluate the neigh- If all neighbors that can be reached by allow-
′
boring solution y , which is exactly equal able moves are infeasible, the algorithm evaluates
′
to y in all indexes except that y it = 0 these neighbors by solving ELSIDD-FEAS given
′
(y = 1).
it their y vectors. If there are multiple neighbors
• Delaying production to the following pe- that have 0 total excess, it means that feasible so-
riod: If the element y it of vector y of the lutions have been reached. The algorithm reevalu-
current solution is equal to 1, we create a ates these neighbors by solving the original formu-
′
neighboring solution with vector y , which lation for the multiple item ELSIDD problem, and
is exactly equal to y in all indexes except picks the one with the highest profit. Otherwise
′
that y = 0 and y ′ i,t+1 = 1. (i.e. if still no feasible solutions are in reach), it
it
• Taking production to the preceding period: picks the neighboring solution with the lowest to-
If the element y it of vector y of the current tal excess and makes it the current solution. The
solution is equal to 1, we create a neigh- algorithm then proceeds by evaluating the neigh-
′
boring solution with vector y , which is bors of this infeasible solution with the hope of
exactly equal to y in all indexes except finally detecting a feasible solution. In case the
′
that y = 0 and y ′ i,t−1 = 1. Infeasibility Procedure needs to be carried
it
out in the first iteration of the TSA, i.e. if the
hybrid solution obtained from the LR turns out
Algorithm 2. Neighborhood Search Algorithm. to be infeasible, the above neighborhood evalua-
1: procedure Search Neighborhood (y current, Tabu List) tions are performed for up to five iterations (i.e.,
2: Make moves that are not in Tabu List, create neighbors
3: if All neighbors are infeasible then for five distinct current solutions). If feasibility
4: implement Infeasibility Procedure is still not achieved, the ELSIDD-FEAS is then
5: end if solved by CPLEX where the setup vector (y) is
6: Determine the best neighbor
7: Update Tabu List not given, but is defined as a decision variable.
8: Return the best neighbor This step either yields a feasible solution to multi-
9: end procedure ple item ELSIDD, or confirms that the problem is
254