The classic Quadratic Assignment Problem stipulates that we are assigning some number of departments to an equal number of potential locations. We are given the volume of traffic $($aka the flow$)$ between each pair of departments and the distances between each pair of locations. The problem consists in assigning departments to locations to minimize the total volume$-$distance travelled $($i$.$e$.$ inter$-$departmental flows $\backslash$times inter$-$location distances$).$ This could often correspond to minimizing material handling costs or time. For example, let$$s say the daily flow between departments $1$ and $2$ was $30$ trips. Furthermore, assume department $1$ is assigned to location $6$ and department $2$ to location $4.$ If the distance between locations $6$ and $4$ was $15$ meters, then the volume$-$distance between these two departments would be $30\backslash$times $15=450$ trip$-$meters. Obviously, the goal is to locate departments with large inter$-$departmental flows close together while department pairs with little traffic can be located further away from each other.

You$$ve been provided with an Excel spreadsheet whose complexity shows how tricky the problem is even for a very small instance of the problem: assigning $5$ departments to $5$ locations. This problem is small enough to be solved by enumeration as there are only $5!=120$ possible assignments. However, our goal here is to use the problem to illustrate the idea of local search.

$1.$ We will express solutions by giving the assigned locations of our $5$ respective departments. Thus our initial assignment of $5-4-3-2-1$ means that the first department is assigned to location $5,$ the second to location $4$ and so forth. This initial solution is given both in red in cells C$5$ G$5$ and in black in cells C$4$ G$4$ in the project spreadsheet; it has an objective function value of $6821,$ which we see in cell H$2.$ One way to improve on this solution is to swap the locations of any pair of departments. We define solutions found in this manner to be neighbors of our current solution. For example, the first neighbor of our starting solution would swap locations of departments $1$ and $2,$ giving the solution $4-5-3-2-1.($Now department $1$ is given location $4,$ while department $2$ gets location $5.)$ To find the objective function value of this neighboring solution, the sequence $4-5-3-2-1$ would be entered in cells C$4$ G$4$ on the spreadsheet, at which point cell H$2$ would display the neighbor$$s objective function value. Investigate each of the $10(5$C$2)$ neighbors of the current solution $($the one in red$)$ that can be created by swapping any pair of departments. To do this, perform one swap at a time, writing down its objective function in the following table, and then return to the original $($or current$)$ solution after each swap. The first $3$ neighbors are filled in $($though not their objective function values$).$ For convenience, the current solution $5-4-3-2-1$ is shown in red in cells C$5$ G$5$ so that it$$s easy to get back to it after investigating each neighbor.

Row Departments whose locations are swapped Neighbor Objective Function

$11$ and $24-5-3-2-1$

$21$ and $33-4-5-2-1$

$31$ and $42-4-3-5-1$

$4$

$5$

$6$

$7$

$8$

$9$

$10$

$2.$ Local search investigates all neighbors of the current solution $($which you just did$)$ and then moves to the one which gives us the best objective function value. This best neighbor becomes our new current solution. Specify the new current solution $($solution $2)$ by listing the locations of the $5$ departments, in order as seen in the table above. Update the Current Solution $($the red cells in C$5$ G$5)$ on the spreadsheet to reflect this new assignment. For example, if the first neighbor had the smallest objective function value $($which it does not, although it does give a better objective function value than the initial current solution$),$ then your new current solution would be $4-5-3-2-1.$

New current solution:

$3.$ Perform one more iteration of local search by investigating all of the neighbors of solution $2$:

Row Departments whose locations are swapped Neighbor Objective Function

$11$ and $2$

$21$ and $3$

$31$ and $4$

$4$

$5$

$6$

$7$

$8$

$9$

$10$

As you did before, identify the best neighbor of solution $2$ and make this best neighbor the new current solution $($solution $3).$ Update the red cells in C$5$ G$5$ with the new solution.

Current solution $3$:

At this point, we$$ve seen how local search works. As long as we can construct a neighborhood of an initial solution $($which isn$$t always trivial$)$; it can be applied fairly easily, and it often will rather quickly make dramatic improvements on initial solutions. In our final project, we$$ll investigate its limitations and see how these are often addressed.