# Optimal Agent-Based Pickup and Delivery with Time Windows and Electric Vehicles
## 2 Derivation of Hypotheses and Related Works  
### Agent-Based Models for Vehicle Routing Problems  
Agent-based approaches over VRPs and their variations have become popular solutions for complex optimization problems, particularly in dynamic environments with uncertainty and many distributed actors. Continuous information exchange and the need to reach a consensus over the negotiation of local solutions are essential to solving these problems and obtaining feasible global solutions.  
The authors of [13] presented an agent-based approach for optimization problems using a decomposition model. Their results included estimates of the potential performance gain using a distributed implementation.  
In an ABSM for VRP, multiple autonomous agents represent the vehicles that interact and coordinate to solve the routing problem collaboratively. Each agent is aware of its current location, its assigned customers, and its constraints. Agents can usually exchange this information to solve the route optimization problem.  
Two approaches are distinguished by the authors in [14]: centralized and decentralized. The first refers to the centralized approach in which a central entity (\"controller\", \"coordinator\") makes a decision based on the information obtained from all other agents. Usually, a coordinator agent has a global overview of the system by gathering information and constraints from every agent to determine the best solution. Since this approach is a single decision-making entity, the decisions tend to be consistent with the global objective. The drawbacks of the centralized approach are the higher computational complexity, where the agents need to process the information from all other agents to make a decision, and the system may also be less adaptive to changes in dynamic contexts. The second approach is decentralization, where agents make decisions based on their local information or locally available data, such as from their neighbors or local environments. In this approach, the agents usually interact in a peer-to-peer fashion. The computation is distributed across agents, which may reduce the computational complexity and allow parallel processing. The authors proposed the usage of the contract net protocol (CNP) in a decentralized approach to order handling.  
The idea of using agent-based approaches to solve dynamic optimization problems has been researched for a long time in the literature. For example, an agent-based approach to solving optimization problems using the Dantzig-Wolfe column generation scheme is proposed in [13]. In [15], the authors used CNP as a negotiation mechanism between vehicle agents to minimize the number of used vehicles.  
Agent-based approaches to freight transportation problems were identified in many studies. For example, in [16], the authors proposed a knowledge-based freight broker based on agents and constraint programming, showing relevant results. The authors in [17] considered a multi-agent approach in combination with a heuristic local search to solve vehicle routing problems with time windows (VRPTW). Their evaluations were conducted on Solomon benchmark instances, which showed results comparable to those in the literature.