Decentralized probabilistic algorithm using a multi-agent system for vehicle routing problems

In the multi-vehicle transportation problem, a well-known combinatorial optimization problem, flexibility and adaptability to new situations is required when faced with things such as traffic jams, new customers, or economical vehicle allocation. In this paper, we propose a decentralized probabilistic algorithm, designed using a multi-agent system, in which agents autonomously and independently search for the partial solution to the problem, their customers, and traveling routes to minimize transportation costs under some constraints. The iterative improvement method is as follows. Customers are initially allocated to agents by random generation. An initial solution then is composed by the nearest neighbor algorithm. One customer belonging to an agent is selected randomly, and the customer belonging to the other agent is allocated to the agent with transition probabilities inversely proportional to the 2-dimensional Euclidean distances between the selected customer and the others. The new candidate partial solution is again composed by the nearest neighbor algorithm, estimated, and accepted with the probability dependent on the difference between the costs before and after computation. The validity of this method is studied by a computer experiment for the three agents, thirty customers, and one or two depot problems. We confirmed that multi-agents adaptively cooperate and self-organize to search for the solution.