# On the Use of the Multi-Agent Environment for Mobility Applications
## 2 Environment as a Spatio-Temporal Reference
### Space-Time Environment for Planning in Mobility Applications  
Vehicle routing problems (VRPs), modelling real-world applications such as dynamic carpooling or online food delivery, are complex optimisation applications that have attracted an enormous research effort for decades. In the online version of these problems, the optimisation of the response time to connected travellers is vital, along with the optimisation of the classical cost criteria (e.g., the size of the fleet of vehicles, the total travelled distance, the total travel times, the total waiting times, etc.). Multi-agent systems, on the one hand, and greedy insertion heuristics, on the other hand, are among the most promising \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Ratio of Connected** & **Broadcast** &
\begin{tabular}{c} **Space-Time** \\ **Network** \\ \end{tabular} & **Improvement** \\ \hline
20\% & 634 & 252 & 60.25\% \\ \hline
50\% & 1625 & 575 & 64.62\% \\ \hline
80\% & 2680 & 944 & 64.78\% \\ \hline
100\% & 3413 & 1105 & 67.62\% \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Overall number of exchanged messages: broadcast versus space–time environment. approaches for this purpose. This section describes a multi-agent system coupled with a novel regret insertion heuristic. The heuristic is based on a space-time representation of the multi-agent environment. It serves as a mental model for the agents and as an explicit and active entity, guiding the planning of the agents. In a VRP, many nodes must be visited once by several capacitated vehicles. These problems are challenging optimisation problems, and solving them has great practical utility. The time-constrained problem is one of the most studied variants of the VRP (Vehicle Routing Problem with Time Windows, VRPTW henceforth). In this variant, the vehicles must visit the nodes within time windows. Vehicle routing problems are divided into two categories: static problems and dynamic problems. In static problems, all the problem data is available before the optimisation process begins. In dynamic problems, the problem data is incomplete before the execution and is discovered progressively during the optimisation. The incomplete data can be any problem element, such as traffic data or available vehicles. However, the dynamic aspect usually refers to the travellers to be transported, which are unknown before execution (as in carpooling and dial a ride systems). Operational problems are never completely static, and it is reasonable to assume that a static system does not meet current operational configurations. Indeed, in real vehicle routing problems, even when all travellers are known in advance (with a reservation system, for example), there is always an element that makes the problem dynamic. These elements can be no-shows, delays, breakdowns, etc. Online vehicle routing problems could be considered an extreme case of dynamic vehicle routing problems. Indeed, not only is the problem data not completely known before the optimisation starts, but travellers connect to the system in real-time and expect almost immediate responses to their requests. Therefore, the response time of the system in this type of problem is vital. It is more beneficial to immediately provide the current solution to the traveller, rather than waiting a long time for the optimisation system to improve its current solution slightly. Indeed, the traveller is unlikely to wait long for a response to her request. To meet the requirement of short response times, we relied on the multi-agent paradigm to solve online vehicle routing problems. Multi-agent modelling of online VRPTW is relevant for the following reasons. On the one hand, since it allows the distribution of computations, it should shorten the response time to travellers' requests. On the other hand, nowadays, vehicles are more and more connected and have onboard computing capabilities. In this context, the transportation system is _de facto_ distributed and requires appropriate modelling to take advantage of these facilities.