DIFFERENTIAL EVOLUTION ALGORITHM FOR SOLVING MULTI-STAGES ASSIGNMENT PROBLEM: A CASE STUDY OF CHICKEN TRANSPORTATION

Abstract

The assignment problem is a problem of assigning an agent to one job. Any matching of assignment come with a cost. The minimize total cost is the goal of assignment problem. The multi-stage assignment problem is more complicated than the classical one. Stage one is assign chicken’s farm to egg’s farm then quantity demanded is created. Stage two, type of truck that matches quantity demanded is assigned. All of the assignments must be assigned in one decision. Thus the costs of assignment depend on that decisions. The exact method is the best way for solving assignment problem for instances simplex method, the Hungarian method, and etc. It is started by developing a mathematical model and LINGO program. Not only exact method that can be solved assignment problem. The heuristic method is an alternative way to solve the problem. In this study, Differential Evolution (DE) is selected. After the initial solution is set, DE will do mutation, recombination, and selection, repeatedly. The end condition in this study is a number of iterations. We develop a mathematical model that include fitness function and all restrictions. After that, we develop LINGO program and test it by generating 3 groups of sample by using the size of sample and each group has 5 samples. Afterward, we use this case study data instead of groups of sample. At the same time, we develop DE algorithm and test with those groups of sample and case study data. For small and medium size, we find the optimal solution. DE find the best solution for small size within 0.2 seconds while LINGO time is around 5 seconds. DE index is 118.4 on average that might not look good because of the generated distance in that sample. For medium size, DE time is only 0.6 seconds while LINGO time is 103.6 seconds on average. The index of DE is 106.9 on average. It means the results move closer to the best answer. We cannot find the optimal solution for large size and case study data within appropriated time however we can find a feasible solution within 72 hours. Therefore, we run LINGO for 72 hours and use it for both large size and case study. An average index of large size is 107.1 and DE time is only 4.2 seconds on average. The case study DE time is 7.8 on average while an index is 109.0. To improve DE result, the future research should modify DE hence result should be closer to the best answer. The new heuristics which might be Particle Swarm Optimization (PSO), or any others heuristics should be used instead of DE.