Keywords

1 Introduction

Personal Rapid transit (PRT) is an on-demand urban transit transportation system. It is generally organized in a fully connected network’ shape that covers some parts of a large urban area, or a multi-terminal airport. The network is composed by a set of PRT’stations and dedicated guideways.

The system is fully automated. In fact, the PRT uses a set of driverless electric vehicles (i.e. system controlled) that move along a set of dedicated elevated guideways. This feature allows the separation of the PRT traffic from the conventional urban traffic. PRT vehicles could carry an individual passenger or a small group of individuals up to 6 persons. PRT offers a personalized transportation service as the users of such a system determine on their own the departure time, the departure and the destination of their trip freely. The control system determines based on the current demand the vehicle that should satisfies the demand of users as well as its route and movements within the PRT’ network.

The PRT control system needs also to determine the set of empty moves of vehicles within the system. In fact, as the demand from a PRT station does not equal to the demand to this specific PRT station, the PRT control system would need to balance the flow of empty available vehicles in order to meet perfectly the demand of its users while minimizing their waiting time as well as the total energy consumption of the system. This problem is known in the literature by the empty vehicle redistribution problem. The reader should refer to [12] for more details about this problem.

In the literature, many algorithms have been developed for the empty vehicle management of PRT’ vehicles which focused mainly on the optimal reallocation of the empty vehicles within the system. In fact, this strategy could significantly reduce the waiting time of passengers within the PRT system by increasing the set of empty vehicles displacement. Generally, reallocation algorithms to manage empty moves of PRT vehicles are based on the available historical data related to the incoming of passengers as well as the estimation and prediction of future demands. These approaches use a form of a centralized data base containing past demand and historical data. Due to the central repository, these algorithms are implemented in a centralized manner which they mainly refer to the empty vehicle reallocation. Consequently, these algorithms are hard to be developed in a distributed decentralized way.

Based on this context, implementing simulation tools could be useful in order to analyze and implement effective empty vehicles strategies for PRT system. In fact, simulation could be seen as an abstraction of a complex system in order to study its behavior. In the literature, there exists several simulation approaches such as discrete event simulation, dynamic system and agent-based simulation approach (ABS).

Recently, an increasing interest on using multi-agent systems for innovation transportation applications have been proposed in the literature. In fact, Multi agent systems is a very convenient way to model complex urban transportation system composed of a large number of homogenous and heterogeneous individuals interacting within each other and with their environment. Generally, in this kind of system vehicles are modeled as an autonomous agents which aim to find a sequence of moves in order to optimize their operational cost. However, there are only few works in the literature that proposed efficient algorithms for computing approximate solutions in order to optimize transportation system.

The ABS presents the advantage of being able to study various complex system from the perspective of individual point of view. In the literature, ABS have been implemented and applied to model many logistics and transportation systems [13, 15]. Consequently, it would be interesting to implement an ABS based on the context of PRT in order to reduce its empty vehicles movement and waiting time of passengers.

In the literature, several simulation model and dynamic strategies have been implemented for the PRT context. One could note [12] where authors studied to minimize waiting time of passengers. However, these latter works does not consider battery issues related to the electric PRT vehicles.

One could note also [14]where authors proposed a discrete event simulation approach to model the PRT system. ABS have been proposed within the PRT context in [2, 5, 6]. However, in [2, 5] authors focused on the activities related to vehicles rather than the stations and in [6] authors does not consider battery issues related to PRT vehicles.

Based on these gaps in the literature, we propose in this paper a distributed management algorithm and ABS for PRT systems. The novelty of our approach resides on the fact that we model stations in PRT as an independent actors (i.e. Agents) that are capable of making decisions and ask for empty PRT vehicles. In fact, we give a special focus on implementing a decentralized management algorithm where the set of decisions is distributed on the stations rather than the vehicles. This feature offers several advantages:

  • Eliminating the need for a central control system as the decisions are made autonomously by the stations.

  • A high flexibility for the PRT system as it would be able to cope with uncertain and unusual demand and traffic condition.

Consequently, the contributions of this paper is threefold:

  • We propose an ABS where stations acts as an independent and autonomous actors in the PRT system.

  • We propose a decentralized management strategy for minimizing waiting time of passengers and the set of empty moves in the system.

  • We test our approach based on a realistic case study of Corby in the United Kingdom.

The structure of this paper is as follows. In Sect. 2, the problem definition is presented. Section 3 explains the proposed ABS as well as the implemented decentralized strategy. The computational results and analysis of our simulation model are presented in Sect. 4. Finally, Sect. 5 concludes and gives directions for future research.

2 Problem Definition

In this section, we present the formal problem definition related to PRT. The proposed problem considers to have a PRT network N with a set of finite PRT stations denoted M. Groups or individual PRT’users come at the different PRT stations to ask a specific transportation service from their current location to a specific PRT’station. We suppose that passengers arrives based on a specific poisson process of rate \(\lambda \). The transportation requests should be served immediately. Rejection of transportation demand is not allowed in the system. The PRT system has a set of electric driverless vehicles that the system would use to satisfy the transportation demand. The PRT’vehicles are constrained by its limited battery capacity B. This limited battery capacity would allow the vehicle to travel for a limited distance before returning to the charging location to recharge their batteries.

We consider also to have a predefined matrix distance that determine the cost of moving between each pair of stations. The vehicles are initially located at the charging location. The vehicles in the PRT system are driverless that move without any human intervention. Our problem consider to find a set of dispatching decisions in order to satisfy the transportation demand. We should note that dispatching decisions refer to the assignment of a vehicle to a specific transportation request. As soon as the system receives transportation demand, dispatching decisions need to be made as soon as possible in order to reduce the waiting time of passengers and to increase the efficiency of the system. The dispatching decisions within a PRT system should be made while knowing the current state of the network. That is why effective strategies should be made while evaluating several possibilities in order to optimize the current state of the system.

Our problem is a dynamic one. In fact, the information related to the coming of the transportation requests is known gradually as the PRT system serves its passengers. This characteristic represents an important feature to our problem as the driverless vehicles could not serve all the transportation requests at the same time due to the limited battery capacity and fleet size.

The objective of our problem is to find the set of dispatching decisions related to PRT system that would minimize the total energy consumption and the waiting time of passengers. These two objectives are of a high interest as they would increase the efficiency and the appealing of such a transportation system.

3 The Simulation Model

In this section, we present the proposed ABS model to tackle the proposed problem related to PRT. For this purpose, we present the multi-agent system modeling of PRT. Then, we present the proposed decentralized strategy.

3.1 The Multi-agent System Modeling of PRT

Generally, coordination in on-demand transportation systems (i.e. PRT) could be in two distinctive forms: (i) Centralized in which the central control system tends to improve the performance of the global system by exploring all the different alternatives related to the current situation related to the transportation network by the use of coordination and information sharing. (ii) Decentralized in which coordination could be found at an inter-urban zone only, which could causes conflicting practices that need to be managed.

As a result of the high level of transportation service that the PRT aims to offer to its users, PRT could be modeled as a decentralized system in which independent agents could take their own decisions. This feature would ensures a highly reactive system to the upcoming demand of passengers. Consequently, the PRT could be modeled by using multi-agent system modeling approach. Multi-agent system modeling approach consists of a set of different agents interacting with each other’s in order to solve a specific problem, compete for a finite set of shared resources (i.e. the PRT vehicles) or coordinating with each other in order to avoid conflicts.

In the literature [1], the term agent defines a software or a hardware based computer system that has specific characteristics such as reactivity and pro-activity, autonomy, and social ability. Muti-agents systems offer the advantage of being simple to implement and understand [15]. Also when the problem and the modeled systems is itself distributed, multi-agent system models offer more flexibility in term of dealing with the different constraints of the simulated system.

As complex systems such the PRT are generally a decentralized and distributed ones with many interactions between its different components, it is rather difficult to model and analyze each possible interaction at the earlier design process of a multi-agent model. In fact, multi-agent systems modeling approach handles this complexity by decomposing the system into smaller and rather simple autonomous agents. Consequently and based on this feature, there is no need to define all the possible control reaction and interaction in the simulated system. Therefore, an autonomous agent in a multi-agent system would act and update its state according to its own environment and interaction with the other different agents. Based on this feature, the complexity of the whole simulated system is reduced [11].

In the literature, PRT is considered as a complex and distributed system [4]. PRT is composed by different interacting actors and a network of complex subsystems that together provide a high level of transportation service. Thus, PRT can be modeled as a network of agents. Agents in PRT would try to maximize their own gain rather than the whole system gain. Each agents would act autonomously by being able to interact with its dynamic environment and taking pro-active and reactive decisions [13]. In this sense, it exists numerous studies that proposed to tackle on-demand transportation systems modeling by the use of a multi-agent system modeling approach.

In [2, 5], authors proposed to model PRT using multi-agents based approach where vehicles act as an independent agents. In [6], authors proposed to use multi-agent simulation approach for the PRT context where stations act as independent agent but without tackling many hard constraints related to PRT such as the limited distance constraints. Other works on PRT includes discrete event simulation [8, 9], static energy consumption minimization [7, 10], fleet sizing [3], network design [16], and so on. The novelty on our approach is to consider stations as independent agents while taking into account various constraints and limitation related to the PRT vehicles.

3.2 The Proposed Modeling Approach

As we proposed to use Multi-agents simulation approach for our PRT system, one could argue that the driverless vehicles would be used as the only agent types in our model. However, we used in our model three type of agents: (i) Vehicles, (ii) Passengers, (iii) Stations.

This different agents would communicate with each other and their own environment. The passengers agents arrive at specific PRT station and ask to be transported to another PRT station. Consequently, the passengers agents send a transportation request to its current departure station. The transportation request is represented by a triplet: (i) Departure station (ii) Arrival station (iii) Departure time.

This transportation request would be treated by the specific agent that represents the departure station. In fact, the station agent and based on the transportation demand characteristic would select the best available vehicle agent available at the departure station based on the total traveled distance and the available electric battery charge. Consequently, we could consider that the environment in our simulated system represents all the information available at the different nodes of the network.

In the following subsections, the role of each type of agent is explained.

3.3 Vehicle Agent

The vehicle agents in our model has four different functions:

  • They transport passenger’ agents in order to satisfy their transportation requests.

  • They interact with the station agents in order to know what passengers request they could satisfy.

  • They interact with the specific charging station agent in order to perform charging operation.

  • They gather different statistics in order to evaluate the performance of the whole system.

Every vehicle can be in four principal states: waiting empty, moving empty, moving with passengers, charging state.

3.4 Passenger Agent

The passenger agent is composed of a set of passengers or an individual one with the same departure and destination stations, and whose number does not exceed the capacity of the PRT vehicle in term of number of passengers (e.g. six passengers). This agent interacts with the station agent in order to inform it about its related transportation request. Then, after a vehicle agent pick up the passenger agent it sends a message to the station agent in order to inform it about its waiting time which would be needed to gather statistics related to the system.

3.5 Station Agent

In our simulation model, the station agents are the most important ones. In fact, the dispatching decisions related to the PRT system are implemented as an integral part of the station agents. Thus, the station agents would receive all the different passengers arriving at their locations. Each station agent would evaluate the available transportation requests. Based on the current situation of the system, the station agent would interact with the vehicles agent available at its location in order to perform the transportation request. The station agent would choose from the available empty vehicle the best one able to perform the transportation request. This decision is based on the traveled distance related to the transportation request as well as the available electric energy in the different vehicles. If no empty vehicles are available, the station agent would communicate with the other station agents in order to ask for a specific number of vehicles. For example, if a station agent has four waiting transportation requests that could not be satisfied by the available vehicle agent in the station, it would ask all the other stations agents to send four different empty PRT vehicles. The different other station agents would evaluate the demand and would accept or reject the demand in empty vehicles. In the case of acceptance a conflict could arise if more than one station would satisfy the need of empty vehicles of a specific station agent. In this case, the station agent asking for empty vehicle would accept only the vehicles coming from the closest distance possible. Finally, we should note that periodically the station agent would evaluate the available empty vehicle agent available at its location. If a vehicle has waited empty for too long, it would be sent to the charging location.

Details about PRT station agents are shown in Algorithm 1. We should note that station agents treat the transportation demand based on the principle of first come first serve in order to minimize the total waiting time.

figure a

Finally, we should note from Algorithm 1 that a proactive behavior is implemented as a part of the general behavior of the station agent. In fact, we propose that each station should have a fixed number of empty vehicle waiting for passengers to come in order to reduce the total waiting time of passengers. Periodically and after serving the different waiting passengers, the station agent would look for the number of empty waiting vehicles in its current location and ask other station agents to send empty vehicles if the station is at a deficit of empty vehicles (e.g. number of empty vehicles is less than the reserve value).

Table 1. Results of the proposed strategy
Full size table

4 Computational Results

The proposed simulation model was written in C++ language with the intention of analyzing the proposed decentralized strategy. The written computer program was written with the intention to predict the service level for the system using several statistics related to the waiting time of passenger, consumed energy, etc.

In this section, we present the computational results related to our multi-agent model for the PRT system. For the testing bed, we choose the one from the literature [9]. The testing bed is based on the Corby real use case which represents a realistic PRT network. The network is composed of 15 stations and 4 depots. As we are treating the case of a single depot topology, we proposed to generate four different networks where each one of them contain only one different depot.

As for the simulated scenarios related to the PRT transportation requests, we used scenarios adapted from the literature [4]. More specifically, the generated scenarios are based on the data available in the ATS/CityMobil softwareFootnote 1. The ATS/CityMobil presents the rates \(\lambda _{ij}\) of a poisson process for traveling from any station i to any other station j in the Corby network. We should note that \(\lambda _{ij} \in [0.789, 17.902]\). We used in this paper 5 different scenarios. Also, we supposed that the total number of fleet is equal to 200 vehicles. The reserve value related to the number of empty vehicles that should be present in each station is equal to 2 vehicles. We should note that we supposed that the battery would make the vehicles run for 40 min before to be needed to recharge it [4]. Results are presented in Table 1. Table 1 presents the percentage of empty movements as well as the full movement (movement of a vehicles with passengers) of the total movement of vehicles in the system. We also present the mean waiting time of passengers for each scenario in minutes (Min). We should note that the waiting time of a passengers is the difference between the arrival time of the passengers to their arrival station and the time of the fulfillment of their demand.

Results shows the good performance of our decentralized strategy as we found a mean waiting time of 3.847 min and a mean empty movement of 47.677 % which means that the vehicles move in 47.677 % empty without taking passengers.

5 Conclusions

In this study, a multi-agent system model is proposed for the PRT system. Unlike the majority of the previous studies, a decentralized management strategy with complex relationships between the different agents is proposed. This study differs from the previous studies for PRT in that it considers stations as an autonomous agent as well as battery issues within a multi agent simulation model. The validity and reliability of the proposed model are evaluated through simulation experiments by using a real world application related to an urban use case from the United Kingdom.

The next step of this study is to integrate the proposed model within a decision support system related to PRT in order to evaluate the best strategy among many others for the system. In future studies, the effect of other external factors on the performance of the different agents could be studied Finally, the development of learning algorithms for the stations and vehicles agents could be a promising field of study.