Solving Vehicle Assignment Problem Using Evolutionary Computation

摘要

This paper examines the use of evolutionary computation (EC) to find optimal solution in vehicle assignment problem (VAP). The VAP refers to the allocation of the expected number of people in a potentially flooded area to various types of available vehicles in evacuation process. A novel discrete particle swarm optimization (DPSO) algorithm and genetic algorithm (GA) are presented to solve this problem. Both of these algorithms employed a discrete solution representation and incorporated a min-max approach for a random initialization of discrete particle position. A min-max approach is based on minimum capacity and maximum capacity of vehicles. We analyzed the performance of the algorithms using evacuation datasets. The quality of solutions were measured based on the objective function which is to find a maximum number of assigned people to vehicles in the potentially flooded areas and central processing unit (CPU) processing time of the algorithms. Overall, DPSO provides an optimal solutions and successfully achieved the objective function whereas GA gives sub optimal solution for the VAP.