# 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
#### 2.3.2 Coordination of Action Zones  
Until now, the space-time model of the environment is used as a mental model of the agents, but it is not explicitly modelled and shared between the agents, and they do not interact with it. This method results in a better space-time coverage of the transportation network, materialised by a minimal mobilisation of vehicles with the appearance of new travellers. Each vehicle agent tries to maximise its action zone independently of the other agents with the mechanism mentioned above. However, it would be more interesting if the agents covered the network in coordination. Specifically, for a vehicle to lose space-time nodes that it alone covers should be more costly than losing nodes that the other agents cover. To this end, we modelled the environment explicitly and associated with each node in the space-time network the list of vehicles that cover it. Each vehicle notifies the space-time nodes that it is part of its action zone, and each node continuously updates its list. Similarly, when a vehicle agent loses a node in its action zone, the node is notified, updating its list of vehicles. When the price of inserting a traveller is calculated, each vehicle agent first determines the space-time nodes it would lose if it were to insert the new traveller. Then, it asks each of these nodes about the \"price to be paid\" if it were no longer covering it. This price is inversely proportional to the number of vehicles covering that node. Specifically, the price to pay is equal to  
\[\frac{1}{|v_{<n,t>}|}\]  
with \(v_{<n,t>}|\) designating the vehicle agents covering the space-time node \(<n,t>\) and \(|v_{<n,t>}|\) the number of these vehicles. Figure 6: Action zone after insertion of a traveller. This method, based on an active space-time environment, associates a higher penalty with the decision to stop covering a node less covered by others. Thus, vehicle agents have an incentive to cover the entire network in a coordinated manner. [PERSON] [18] created a set of different static problems for the VRPTW. It is now admitted that these problems are challenging and diverse enough to compare the different proposed methods with enough confidence. In [PERSON]'s benchmarks, six different sets of problems have been defined: C1, C2, R1, R2, RC1 and RC2. The travellers are geographically uniformly distributed in the problems of type R, clustered in the problems of type C, and a mix of uniformly distributed and clustered travellers is used in the problems of type RC. The problems of type 1 have narrow time windows (very few travellers can coexist in the same vehicle's route) and the problems of type 2 have wide time windows. Finally, a constant service time is associated with each traveller, equal to 10 in the problems of type R and RC, and to 90 in the problems of type C. There are between 8 and 12 files containing 100 travellers in every problem set. We chose to use [PERSON] benchmarks while following the modification proposed by [19] to make the problem dynamic. To this end, let \([0,T]\) the simulation time. All the time-related data (time windows, service times and travel times) are multiplied by \(\frac{T}{l_{0}-e_{0}}\), with \([e_{0},l_{0}]\) the scheduling horizon of the problem. The authors divide the travellers set into two subsets; the first subset defines the travellers known in advance, and the second is the travellers who reveal during execution. We did not make this distinction since we consider no travellers known in advance. An occurrence time is associated with each traveller, defining the moment when the system knows the traveller. Given a traveller \(i\), the occurrence time that is associated is generated randomly between \([0,\overline{e}_{i}]\), with:  
\[\overline{e}_{i}=e_{i}\times\frac{T}{l_{0}-e_{0}} \tag{1}\]  
It is known that the behaviour of insertion heuristics is strongly sensitive to the appearance order of the travellers to the system. For this reason, we do not consider only one appearance order.