Moana — A multi agent approach for VRP
Thomas Farneti
• Enrico Benini
Introduction
The purpose of this project is to create an autonomous system that is able to plan orders coming from a company's ERP. The ERP will send the orders one at a time and in an autonomous way the system should reach a new state in which the order has been assigned to a vehicle, respecting the capacity constraints. Usually such planning is in fact carried out by a human planner who organizes orders in appropriate logic.The goal is to incorporate (or at least lay the foundations) such logic within intelligent agents able to sense events (addition of a new order to schedule) and perform appropriate actions (plan order) by moving the system towards a new state.Essentially the system can be seen as a solver of the VRP with agents.VRP
A Vehicle Routing Problem (VRP) consists of a set of customers that are to be serviced by a set of vehicles. The vehicles are usually assumed to have limited capacity to carry goods and are used to either deliver or pick up goods from the customers. The classic vehicle routing problem assumes that all vehicles have the same capacity and goods are picked up from the customers. Though the vehicle routing problem is simple to state, yet, it is extremely complex to solve.In order to understand the complexity of the problem, let us consider solving one leg of the vehicle routing problem in which one route is used to visit a set of customers. If we assume that the vehicle has unlimited capacity and is used to service a set of customers, then the problem reduces to a Traveling Salesman Problem (TSP). In the TSP a salesman starts from a central depot, visits a set of customers and returns back to depot. To solve such problems, the complexity increases exponentially with respect to the number of customers.The VRP is more complex than the traveling salesman problem as each route in a vehicle routing problem is a TSP. That is, if there are K vehicles in a vehicle routing problem, then in order to get a best set of routes for the K vehicles, K number of travelling salesman problems have to be solved. Algorithmic procedures used to obtain the exact or optimal solution to the VRP problem do exist, but they are computationally expensive. In order to obtain "good" solutions for VRP's that are close to the exact solution in a reasonable amount of time, heuristic search strategies are used.A Multi Agent VRP Solver
In order to use agents for vehicle routing problems, the architecture has to consist of a negotiation principle and a coordination framework to support it. The negotiation broadcasts the availability of the customers, accepts the bids on the customers and commits the customer to the vehicle bid with the lowest cost.The coordination framework should be designed for decentralized systems of self-interested and rational entities. Each software agent, responsible for either making the orders available or allocating a order to a route will cooperate and coordinate to solve the vehicle routing problem. Key advantages of this approach are its assumption of decentralized control, the possibility of concurrent or asynchronous execution, the flexibility of control mechanisms and the ability to reconfigure and extend the problem to multiple computers over a network.The methodology used for solving the problem uses an auctioning process to assign customers to vehicles. The auctioning process consists of:- Task Announcement - An auctioning agent that will announce to each Vehicle agent that represents a vehicle on the availability of a order.
- Bid Collection - After the bid announcement of the order, the Vehicle agent collects bids for a order.
- Bid Evaluation - After a bid is collected the Vehicle agent computes the cost of adding the order to its current route.
- Task Offer Submission - After bid evaluation, the Vehicle agent submits the cost of adding the order to its current route.
- Bid Assignment - the auctioning agent collects all the bids received from the vehicle and assigns the order to the Vehicle agent with the lowest cost.
- Task Commitment - After order is awarded to the Vehicle agent, it inserts the customer into its route.
CNP for Distributed Search
The agent system that is being implemented for solving the VRP uses a modified version of the CNP that is is capable to conduct a distributed search. With this method the system is able to conduct a search using one or more heterogeneous computer systems (in this case software agents) in a distributed network with each node on the network capable of autonomously selecting a search strategy that maximizes its performance locally. This method allows one to integrate both global search strategies such as Genetic Algorithms, Tabu Search and Simulated Annealing and local neighborhood search strategies. This allows the system to use search methods that have proven to give good results while using them in a distributed manner without the overhead of a centralized mechanism to oversee the process. The agent system consists of two main agents, namely:Planner agent 
Behavior
- Percives the orders adding events from the environment
- Sends orders information one at a time to all Vehicle agents
- Receives bids for each order
- Compares the bids and assigns the order to the bidder agent with the highest bid or lowest cost
Vehicle agent 
Behavior
- Receives order information from the Planner agent one at a time.
- Calculates the cost of inserting the new order into the existing route.
- The cost of inserting the new node is sent back to the Planner agent.
- Accepts a order from the Planner agent if assigned.
Environment
The environment is the bridge between the MAS and underlying architectureCurrent implementation of VRP Mas Solver
The VRP problem was solved using two types of agents namely the Panner agent and the Vehicle agent. These agents have been implemented using the framework JASON. Each agent then its .asl file that will be interpreted and put into execution by the interpreter JASONThe Planner agent announces the available orders one at a time to the Vehicle agents using the CNP distributed search, collects the bids, evaluates the bids to find the Vehicle agent with the lowest cost, and assigns the order to the Vehicle agent with the lowest cost.The Vehicle agents are created on a needed basis. That is, Vehicle agents are generated until all the customers submitted by the Planner agent have been accepted. Each Vehicle agent is associated with a maximum capacity. The Vehicle agent will accept customer as long as the capacity constraint is feasible.Each order that is submitted by the Auctioneer agent is inserted at the end of the current route of the Vehicle agent. The Vehicle agent computes the cost of its current route after inserting the order that was submitted by the PLanner agent. The difference in cost is the bid that is sent back to the Planner agent. This allows the Vehicle agent to bid on orders that are in its neighborhood to minimize the total distance traveled by the vehicle. The messaging between the Planner agent and the Vehicle agent takes place until all customers have been assigned to the Vehicle agents.Java Infrastructure 
To allow the MAS to perform actions and receive event was created an infrastructure built in Java. This infrastructure uses the principles and patterns of DDD. There is in fact a domain model realized through POJO. An outside actor may change the status of the domain model by sending appropriate commands to be executed by appropriate services. Each command implies a change of state of the system that is notified through appropriate events. Commands and events travel through an event bus. To access the internal state of the model is then possible to run queries that will be interpreted by appropriate read modelsThis segregation between Commands and Queries is a pattern called CQRS.CQRS 
Command and Query Responsibility Segregation (CQRS) is a pattern that segregates the operations that read data (Queries) from the operations that update data (Commands) by using separate interfaces. This implies that the data models used for querying and updates are different. The models can then be isolated although this is not an absolute requirement.Compared to the single model of the data (from which developers build their own conceptual models) that is inherent in CRUD-based systems, the use of separate query and update models for the data in CQRS-based systems considerably simplifies design and implementation. However, one disadvantage is that, unlike CRUD designs, CQRS code cannot automatically be generated by using scaffold mechanisms.The query model for reading data and the update model for writing data may access the same physical store, perhaps by using SQL views or by generating projections on the fly. However, it is common to separate the data into different physical stores to maximize performance, scalability, and security.The read store can be a read-only replica of the write store, or the read and write stores may have a different structure altogether. Using multiple read-only replicas of the read store can considerably increase query performance and application UI responsiveness, especially in distributed scenarios where read-only replicas are located close to the application instances. Some database systems, such as SQL Server, provide additional features such as failover replicas to maximize availability. Separation of the read and write stores also allows each to be scaled appropriately to match the load. For example, read stores typically encounter a much higher load that write stores.Finally we provide a simple GUI that allow to see the current result of the computation pressing a simple button. This gui use the same architecture explained, reading the model and printing out the solution of the mas solver. We show for every route: the related orders, theirs demands and the total demand for the route. This allow us to check easily the capacity constraints of every routes. Project structure
it.unibo.moana.core
it.unibo.moana.persistence
On Autonomy
In this section we will discuss some of the autonomy aspects in the project.Independence
One of the property of autonomy is independence and this is present in the project because, the usage of an agent system, keeps all decupled from the outside, the system don't need input to run. Eventually the system will reach a stable point where there's no comunication is needed and the main goals are achived. Moreover all the system can be decentralized to enhance the location independece. Unfortunatly the planner agent is the core of all the system and it's required for it's right behaviour, a future improvement to independence can be the implementation of a cluster strategy: where there're more planner agents, one of them is the master and is active and the others are in idle state. Through a monitoring agent, that collect the alive status of the others, and wake up, loading the right beliefs and goals, an idle planner if the main one goes down.Self-Government/Self-Rule
In our case the self government is very simple because there're only two kind of agents, but we can found some sort of self-government anyway because the agents choose what to do based on the communication, the input from the environment and what happened in the past. In particular, the agents store some internal beliefs to notify if somthing remarkable happened to support some future self-government (ie. disable, enable or delay plans) and play with goals, exposing an executive and motivational autonomy to achive them. This can be also releated to the unit of invocation, one of the main feature of an agent programming paradigm.Level of Autonomy
In a normal scenario a VRP problem will be problably assigned to a human being, that, with a standard software, will try to find the best solution. So in that case the level of autonomy is 'human operated'. With this project one of our goals is to lift the level of autonomy of this duty up to an 'human supervisioned' or even a 'fully autonomy': our vision is a automatized system that can rapidly provide a solution to the VRP problem in response of external orders, from a custumer ERP for instance. Finally, thanks to the higher level of abstraction given by the agents system, we can instruct the agents to manage strange and unexpected situations, so the right decision can be made and that's one of the main key of an autonomous system.Scalability
If the number of orders are growing then the system, with some minor effort, can scale to manage it because every planner agent can be assigned only to some set of orders and plan it independently from other istances of planner agents in a master-worker architecture. We consider this idea very interesting due to the delegation of duties.Conclusions
With this simple project we wanted to demostrate how the Agent-model could be used to solve problems like VRP. The benefits that we found are:- The solver is designed as an autonomous entity. Then it is able to make decisions and self organize to reach a new state that meets the constraints.
- It's possible to add to the system different kinds of Agents that could plan orders with different decision.
- It could be used to simulate the performance of different Algortithm. For example we could create two agents with two different type of Heuristic and see who performs better.
- Jason is an interpreted language so you can change on the fly the planner and the actors logic.