A Multi-Model Estimation of Distribution Algorithm for Agent Routing Problem in Multi-Point Dynamic Task
Sai Lu, Bin Xin, Lihua Dou, Ling Wang · 2018
The agent routing problem in multi-point dynamic task (ARP-MPDT) is a multi-task routing problem of a mobile agent. In this problem, there are multiple tasks to be carried out in different locations. As time goes on, the state of each task will change nonlinearly. The agent must go to the task points in tum to perform the tasks, and the execution time of each task is related to the state of the task point when the agent arrives at the point. ARP-MPDT is a typical NP-hard optimization problem. In this paper, we establish the nonlinear ARP-MPDT model. A multi-model estimation of distribution algorithm (EDA) employing node histogram models (NHM) and edge histogram models (EHM) in probability modeling is used to solve the ARP-MPDT. The selection ratio of NHM and EHM probability models is adjusted adaptively. Finally, performance of the algorithm for solving the ARP-MPDT problem is verified by the computational experiments.