Track: Operations Research

Abstract

We try to solve a flow-captured location-allocation problem for signboard layout using a genetic algorithm. A facility located at a node of a road network captures the traffic flow passing the node. In this problem, the traffic is assumed to represent demand. The flow-capturing location-allocation model responds to this type of demand and seeks to maximize the one-time exposure of this traffic to facilities. The signboard layout problem is classified as an instance of this problem. Kakimoto et al. solved this type of problem using an integer programming approach in the case of charging facilities for electric vehicles in Bangkok, Thailand. They reported that the location problem cannot be solved if there is a large number of facilities. On the other hand, Hodgson et al. compared the performance of exact, vertex substitution and greedy solution procedures. They found that a greedy approach can solve the problem for a large number of facilities. However, the difference between the optimal solution and the greedy solution becomes larger as the number of facilities increases.

                   In this research, we study the possibility of solving the signboard layout problem using a genetic algorithm. This algorithm is a metaheuristic algorithm that can solve large combinatorial optimization problems. We formulate a mathematical model for the problem based on multi-objective optimization, where one objective function minimizes the number of signboards and the other maximizes the traffic flow captured by the signboards. We present the design of the genes, that is, the bit strings that express a solution to the problem. Finally, we evaluate the performance using numerical simulation.