Open access peer-reviewed chapter

Petri Nets Models for Analysis and Control of Public Bicycle-Sharing Systems

By Karim Labadi, Taha Benarbia, Samir Hamaci and A-Moumen Darcherif

Submitted: December 1st 2011Reviewed: May 3rd 2012Published: August 29th 2012

DOI: 10.5772/47774

Downloaded: 2077

1. Introduction

Public Bicycle-Sharing Systems (PBSS), also known as self-service public bicycle systems, are available in numerous big cities in the world (Vélib' in Paris, Bicing in Barcelona, Call-a-Bicycle in Munich, OyBicycle in London, etc.). Since its inception, Bicycle-sharing programs have grown worldwide. There are now programs in Europe, North America, South America, Asia, and Australia. A still growing list of cities which provides such green public transportation mode can be found at the Bicycle-sharing world map (http://Bike-sharing.blogspot.com) as shown in Figure 1. As a good complementary to other urban transportation modes, bicycle use entails a number of benefits including environmental, mobility and economic benefits. The public bicycle sharing systems are especially useful for short-distance city transport trips and to face many public transport problems, including growing traffic congestion, pollution, greater car dependency, buses caught in city congestion, and ageing transport infrastructure.

A PBS system can be described as a bank of bicycles that can be picked up and dropped off at numerous stations (service points) across an urban area. The bicycle stations are usually located 300 meters apart, consisting of terminals and stands for fastening the bicycles. Every station is equipped with roughly twenty bicycle stands (the number can be estimated depending on the location of the service point and the estimated level of use). A customer uses a bicycle to travel from one station to another. A bicycle can be taken out from any station and returned to the same or any other station, provided that there is an available locking berth. A PBS system requires more than just bicycles and stations; a variety of other equipment is needed to keep the bicycles and stations functioning at adequate level of service. Particularly, this includes a fleet of vehicles for redistribution of bicycles between stations in order to balance the network (see Figures 2 to 4).

Figure 1.

Bike-Sharing world map (source http://Bike-sharing.blogspot.com).

Figure 2.

Full station, (http://www.velib.paris.fr/)

Figure 3.

Empty station, (http://www.velib.paris.fr/)

Figure 4.

Redistribution vehicle (http://www.velib.paris.fr/)

Over the recent years, public bicycle-sharing schemes have developed from being interesting experiments in urban mobility to mainstream public transport options in cities as large and complex as Paris and London (http://www.velib.paris.fr/). PBS schemes have evolved dramatically since their introduction in the 1960s and undergone various changes. These changes can be categorized into three key phases, known as Bicycle sharing generations [9]-[8]. These include the first generation, called white Bicycles (or free Bicycles); the second generation, coin-deposit systems; and the third generation, or information technology based systems. Potential “fourth generation” design innovations are already under development including electric bicycles, movable docking stations, solar-powered docking stations, and mobile phone and iPhone real time availability applications. Of these innovations, the introduction of electric bicycles is likely to be the most significant in terms of attractiveness. The Table 1 gives a survey of some significant public bicycle-sharing programs over the world since the first generation schemes that were introduced in Amsterdam.

A crucial question for the success of a PBS system is its ability to meet the fluctuating demand for bicycles at each station and to provide enough vacant lockers to allow the renters to return the bicycles at their destinations. Indeed, some stations have more demand than others, especially during peak hours. In addition, not surprisingly stations located at the top of hills are chronically empty of bicycles, as the customers ride down the hill but do not wish to make the return trip uphill. Bicycles also tend to collect in stations in the city centres and stay there. In some cases, the imbalance is temporary, e.g., high return rate in a suburban train station in the morning and high renting rate in the afternoon. In other cases, the imbalance is persistent, e.g., relatively low return rate in stations located on top of hills [30]. If no action is taken by the service provider they rapidly fill or empty, thus preventing other users from collecting or delivering bicycles.

Thus, the system requires constant monitoring to balance the network. The monitoring system dispatches motorized redistribution vehicles (trucks) to rebalance bicycles between stations that are emptying out and those that are filling up. This operation can be carried out in two different modes [30]:

  • Static mode — The bicycle redistribution operation can be carried out during the night when the usage rate of the PBS system is very low. The bicycle repositioning is performed based on the status of the system at that time and the demand forecast for the next day.

  • Dynamic mode — The bicycle redistribution operation can be carried out during the day when the usage rate of the PBS system is significant. The bicycle repositioning is performed based on the current state of the station as well as aggregate statistics of the station’s usage patterns [16].

YearCityBicycle-sharing program
1960Amsterdam (Netherlands)The first Bicycle sharing system in the world appeared in Amsterdam, the Netherlands on July 28, 1965. Bicycles were painted white and offered to the public who would like to use them. Due to theft and abuse, unfortunately the program only survived for several days.
1995Copenhagen (Denmark)In 1995 in Copenhagen, Bycyklen or City Bicycles was operated as the first large-scale second generation Bicycle sharing program. The system had improved in many aspects. The bicycles are specifically designed for intensive urban use and stations were set up with each equipped with a coin deposit.
1998Rennes (France)Rennes launched “Vélo à la Carte” in 1998, which was the first computerized system in the world and the first one in France, and was also operated by ClearChannel, a private company. In 2009, the operator changed to EFFIA and shifted to a new system called “VéloStar”.
2005Lyon
(France)
Lyon started its Bicycle sharing system Vélo’V with an unusually large scale in 2005. The city of Lyon and JC Decaux funds the system together through an advertisement contract, which the latter one operates the scheme. Vélo’V is based on stations and has long and short term subscription available with first 30 minutes free.
2007Paris (France)Velib’ was introduced to Paris in 2007. With the similar operation scheme as Lyon, city of Paris and Cycocity fund the system together and the latter one operates it. Velib’ has fixed stations and requires registration beforehand.
2008Hangzhou (China)In May, 2008, the first Bicycle sharing program in China started its operation in Hangzhou, a city 180 km southwest of Shanghai, with 4.2 million inhabitants in the metropolitan area, 8 districts included.
2008Washington (USA)SmartBicycle DC was a implemented in August 2008 with 120 bicycles and 10 automated rental locations in the of The network was the first of its kind in North America.
2009Canada (Quebec)Bixi is a public serving , , . The system was launched on May 12 2009, with 3000 bicycles and 300 stations located around Montreal's central core, and it expanded to 5,000 bicycles and 400 stations later that summer.

Table 1.

Summary of some PBS systems over the world

Vogel et al., (2011) [38] identify three management and design measures alleviating these imbalances divided into different planning horizons: (1) Strategic (long-term) network design comprising decisions about the location, number and size of stations, (2) Tactical (mid-term) incentives for customer based distribution of bicycles. For example, the Vélib in Paris grants some extra minutes for returning bicycles at uphill stations, (3) Operational (short-term) provider based repositioning of bicycles. The most important issues for the success of a PBS system are summarized in Table 2.

StageQuestions
Before deployment
(Strategic / Tactical)
How many bicycles and stations?
Where to locate stations?
What is the size of each station?
How should the bicycles be distributed?
How many vehicles (and what sizes) are needed for bicycle redistribution?
...
After deployment
(Operational)
How often should the bicycles be redistributed?
Is the current number of redistribution vehicles and projections sufficient?
Should more bicycles be purchased?
More stations needed?
Regular or preventative maintenance required?
...

Table 2.

Management and design measures of a PBS system

To help planners and decision makers answer these crucial questions, modelling and performance analysis and optimization methods and tools for PBS systems are needed. A literature review describing some existing works developed in this research area is dressed in the section 2. After, the rest of this chapter deals with an original Petri net approach dedicated for PBS systems modelling for control purposes [2]-[19]-[20]-[21]. The section 3 provides an introduction for Petri nets with the “marking dependent weights” concept [17] as it is used throughout this chapter to model PBS systems for control purposes. In the sections 4 to 6, a modular framework based on Petri nets with marking dependent weights is developed for modelling and performance evaluation of PBS systems. The concluding section 7 gives some remarks and perspectives of this work. Our approach is intended to help planners and decision makers in determining how to implement, and operate successfully these complex dynamical systems.

2. A review of the literature

Public Bicycle-sharing systems have attracted a great deal of attention in recent years. Although the growth of the system has been rapid following the development of better tracking technology, most of the studies related to PBS systems in the literature have focused on their history, development and some practical advises [9]-[31]-[39]. There are, however, relatively few studies addressing strategic and operational issues that arise in such systems.

About strategic issues, Lin and Yang (2011) [22] and Lin et al., (2011) [23] address the strategic problem of finding optimal stations using mathematical programming techniques. The problem is formulated as a hub location inventory model. The key design decisions considered are: the number and locations of bicycle stations in the system, the creation of bicycle lanes between bicycle stations, the selection of paths of users between origins and destinations, and the inventory levels of sharing bicycles to be held at the bicycle stations. The design decisions are made with consideration for both total cost and service levels. Dell’Olio et al. (2011) [7] present a complete methodology for the design and implementing of bicycle sharing systems based on demand estimates considering the stations and the fares. Vogel et al. (2011) [38] develop a methodology for strategic and operational planning using data mining. A case study shows how Data Mining applied to operational data offers insight into typical usage patterns of bike-sharing systems and is used to forecast bike demand with the aim of supporting and improving strategic and operational planning.

Regarding operational issues, besides the work presented in [38], the static balancing problem studying the repositioning of bicycles among bicycle stations where the customer demand is assumed to be negligible is addressed in [5]-[30]. Several mathematical formulations of the problem can be found in [30] and an exact algorithm based on column generation and a suitable pricing algorithm based on dynamic programming are given by Chemla et al.; (2011) [5]. From an OR perspective, the bicycle repositioning problem bears great similarities to some other routing problems which have been largely studied in the literature. As an example from this point of view, Forma et al. (2010) [12] consider the bicycle repositioning problem as a variation of the Pickup and Delivery problem (PDP). Naturally, some similarities between bicycle-sharing and car-sharing systems can be explored in order to adapt some existing results in this field (see, for example [26]-[36]).

Besides OR approaches developed, particularly by using mathematical programming techniques [5]-[12]-[22]-[23]-[30] to support decision making in the design and management of PBS systems, Data Mining techniques receives attention in academia as well as in practice. Data Mining is particularly suitable to analyze and to predict the dynamics of a PBS system. By exploring and analyzing the temporal and geographic human mobility data in an urban area using the amount of available bicycles in the stations of a PBS system [3], statistical and prediction models can be developed [13]-[16] for tactical and operational management of such systems.

As noted in [37], although extensive analysis of bicycle data or customer surveys can be applied to predict future bicycle demand at stations, the demand still has to be considered stochastic and not deterministic. Moreover various points in time have to be incorporated in a suitable mathematical optimization models. Such a stochastic and dynamic model can be computational intractable. In addition, customer behavior cannot be modelled in these mathematical optimization models. According to our knowledge, unlike our work [2]-[19]-[20]-[21], no other studies has been undertaken on the dynamics modelling and performance evaluation of such dynamical systems. In addition to their self-service mode, PBS systems are dynamic, stochastic, and complex systems, this makes their modelling and analysis very complicated. Among the formalisms used to model the dynamic systems, Petri nets are one of the graphical and formal specification techniques for the description of the operational behavior of the systems. They are widely used in a number of different disciplines including engineering, manufacturing, business, chemistry, mathematics, and even within the judicial system [17]-[18]-[40]-[32]-[42]-[41]. They have been accepted as a powerful formal specification tool for a variety of systems including concurrent, distributed, asynchronous, parallel, deterministic and non-deterministic.

However, although Petri nets have been widely used in various domains, they played a relatively minor role in modelling and analysis of urban transportation systems. According to some existing works, the modelling of the systems by using Petri nets formalisms can be considered from either a discrete and/or a continuous point of view. Continuous Petri nets for the macroscopic and microscopic traffic flow control are used in [15]-[34], while hybrid Petri nets are used in [11] to provide a valuable model of urban networks of signalized intersections. Recently, batch Petri nets with controllable batch speed are used [10] to study a portion of the A12 highway in The Netherlands. From a discrete point of view, generalized stochastic Petri nets are used [1]-[4] for modelling and planning of public transportation systems. The two complementary tools, Petri nets and (max, +) algebra, have been used [28]-[29] to deal with the modelling and the performance evaluation of a public transportation system. For the modelling of passenger flows at a transport interchange, as shown in [33] colored Petri nets are able to incorporate some specific parameters and data in the model such as the variation of walking speeds between passengers and the restricted capacity of features of the interchange infrastructure.

These are a few works that demonstrate the high potential of Petri nets as a tool for modelling and performance analysis of urban transportation systems, but also on the other hand, it is shown that the application of Petri nets is still in its early stage and particularly limited to intersection traffic control [11]-[14]-[15]-[25]-[35]-[34] and to some studies dealing with the modelling of urban transportation systems for planning purposes [28]-[29]-[33]. In addition, according to our knowledge, unlike traditional urban transportation systems, no work has been undertaken on PBS systems modelling and performances analysis by using Petri net models. Our contribution in this context is the first one in the literature [18]-[19]-[20]-[21].

3. Petri nets with variable arc weights

In its basic form, a Petri net may be defined as a particular bipartite directed graph consisting of places, transitions, and arcs. Input arcs are ones connecting a place to a transition, whereas output arcs are ones connecting a transition to a place. A positive weight may be assigned to each arc. A place may contain tokens and the current state (the marking) of the modelled system is specified by the number of tokens in each place. Each transition usually models an activity whose occurrence is represented by its firing. A transition can be fired only if it is enabled, which means that all preconditions for the corresponding activity are fulfilled (there are enough tokens available in the input places of the transition). When the transition is fired, tokens will be removed from its input places and added to its output places. The number of tokens removed/added is determined by the weight of the arc connecting the transition with the corresponding place. Graphically, places are represented by circles, transitions by bars or thin rectangles (filled or not filled), tokens by dots. For a comprehensive introduction of Petri nets, see for example [27].

Formally, a Petri net can be defined as PN = (P, T, Pré, Post, Inhib, M0), where: P = {p1, p2, …, pn} is a finite and non-empty set of places; T = {t1, t2, …, tm} is a finite and non-empty set of transitions; Pre: (PT) N is an input function that defines directed weighted arcs from places to transitions, where N is a set of nonnegative integers; Post: (PT) N is an output function which defines directed weighted arcs from transitions to places; Inhib: (PT) N is an inhibitor function which defines inhibitor weighted arcs (circle-headed weighted arcs) from places to transitions; and M0 is called initial marking (initial distribution of the tokens in the places). A place connected with a transition by an arc is referred to as input, output, and inhibitor place, depending on the type of the arc. The set of input places, the set of output places, and the set of inhibitor places of a transition t are denoted by t, t, and t, respectively. The weights of the input arc from a place p to a transition t, of the output arc from t to p, and of the inhibitor arc from p to t are denoted by Pre(p, t), Post(p, t), and Inhib(p, t), respectively.

The behavior of many systems can be described in terms of system states and their changes. In order to simulate the dynamic behavior of a system, a state or marking in a Petri net is changed according to the following transition rules:

  • A transition t is said to be enabled if each of its input places contains at least a number of tokens equal to the weight of the corresponding input arc, and each of its inhibitor places contains tokens less than the weight of its corresponding inhibitor arcs.

Formally:

pt, M(p)Pre(p,t)E1
pt, M(p)<Inhib(p,t)E2
  • An enabled transition t fires by removing from each of its input places a number of tokens corresponding to the weight of the corresponding input arc, and adding a number of tokens in each of its output places corresponding to the weight of the corresponding output arc.

Formally:

pP,M'(p)=M(p)Pre(p,t)+Post(p,t)E3

The firing of transitions in a Petri net model corresponds to the occurrence of events that changes the state of the modelled system. This change of state can be due to (i) the completion of some activity or/and (ii) the verification of some logical condition in the system. Since transitions are often used to model activities (production, delivery, order…), transition enabling durations correspond to activity executions and transition firings correspond to activity completions. Hence, deterministic or stochastic temporal specifications can be naturally associated with transitions [24].

In addition of the concept of time and the introduction of inhibitor arcs, which are not given in the original definition of Petri nets, the modelling of the complex dynamic of a PBS system requires the use of Petri nets models with “variable arc weights depending on its marking” and possibly on some decision parameters of the system. The same modelling concept is introduced for modelling inventory control systems and supply chains in [17]-[6]. Precisely, the Petri net model of an inventory control system whose inventory replenishment decision is based on the inventory position of the stock and the reorder and order-up-to-level parameters. Similarly, in the case of a PBS system, the redistribution operation of the bicycles between stations depends on the number of the available bicycles in each station when controlled.

By allowing the weights of some arcs of a Petri net to depend on its marking, control policies of the stations can be easily described in the PBS model. Therefore, we consider in this chapter that for any arc (i, j), its weight w(i, j) is now defined as a linear function of the marking M with integer coefficients and . The weight w(i, j) is assumed to take a positive value.

w(i,j)=αij+piP(βij)PiM(pi)E4

To understand the mathematical and intuitive meaning of this concept, consider the Petri net shown in Figure 5.

Figure 5.

Illustration of a Petri net with variable arc weights depending on its marking

The model represents an inventory control system with continue review (s, S) policy (here s = 4 and S = 10) [17]. The different operations of the system are modelled by using a set of transitions: generation of replenishment orders (t3); inventory replenishment (t2); and order delivery (t1). In the model, the weights of the arcs (t3, p2), (t3, p3) are variable and depend on the parameters s and S of the system and on the marking of the model (S - M(p2); s).

  • According to the current marking Mi = (2, 2, 0) of the net, the transition t3 is enabled, since the following condition is satisfied:

    M(p2)=2<Inhib(p2,t3)=4

  • After the firing of t3, 10 - M(p2) = 10–2 = 8 tokens are added into the places p2 and p3. In other words, the firing of the transition t3 from the initial marking Mi leads to a new marking Mf = (2, 10, 8) as the following:

    Mf(p2)=Mi(p2)+[10Mi(p2)]=2+[102]=10.

    Mf(p3)=Mi(p3)+[10Mi(p3)]=0+[102]=8.

4. Modelling of a PBS system

As mentioned in the second section of this chapter, modelling, analysis and performance evaluation of PBS systems is crucial not only for their successful implementation and performance improvement but also for ensuring an effective regulation of bicycle traffic flows. This section deals with our original Petri net approach dedicated for PBS system modelling and analysis for control purposes. We consider a PBS system with N stations noted by S = {S1, S2, …, SN}. Each station Si S is equipped with Ci bicycle stands (the capacity of a station Si). In practice, the number Ci depends on the location of the service point and the estimated level of use. The system requires a constant control which consists in transporting bicycles from stations having excess of bicycles to stations that may run out of bicycles soon. In the general way, the main objective of the control system, performed by using redistribution vehicles as shown in Figure 4, is to maintain Ri (reorder point) bicycles per station Si to ensure bicycles are available for pick up and thus (Ci – Ri) vacant berths available for bicycle drop off at every station.

4.1. The Petri net model

Firstly, for the sake of clarity, we consider a PBS system with only three stations and then we design a Petri model of the system as shown in Figure 6. The designation of the elements and parameters of the Petri net model are given in Tables 3, 4 and 5. Thereafter, as will be shown in this section, according to the modular structure of the resulting Petri net model, its generalization to represent PBS systems with N stations will be straightforward and intuitive.

Before a formal description and analysis of the model in the next sub-sections, the Figure 6 and the Tables 3, 4, and 5 allow readers to quickly gain an understanding of the Petri net model of the system. A closer look at the Petri net model shows three subnets (modules) representing three different functions named as follows: (1) the “station control” subnet; (2) the “bicycle flows” subnet; and (3) the “redistribution circuit” subnet. The main function of each subnet is described in the following:

  • The “bicycle flows” subnet represents the bicycle traffic flows between the different stations of the network. A customer uses a bicycle to travel from one station to another. In other words, a bicycle can be taken out from any station and returned to the same or any other station, provided that there is an available locking berth.

  • The “station control” subnet represents the control function of the stations to ensure bicycles are available for pick up and vacant berths available for bicycle drop off at every station Si. The purpose of this function is two-fold: First, the control of the state of the station in terms of the number of bicycles available for new users; and second, according to the state of the controlled station, take one decision among three alternatives: (i) Add bicycles in the station, or (ii) Remove bicycles from the station, or (iii) Take no action.

  • The “redistribution circuit” subnet represents the path (circuit) to be followed by the redistribution vehicle in order to visit the different stations of the network. Its objective is to rebalance bicycles between stations that are emptying out and those that are filling up.

PlaceInterpretation
PSiRepresents a station Si. Its marking M(PSi) correspond to the number of bicycles available in the station Si.
PRiRepresents a redistribution vehicle used to regulate the stations. Its marking M(PRi) correspond to the number of bicycles available in this redistribution vehicle when the station Si is visited in order to be controlled.
POiSpecify whether the number of bicycles in a station Si is greater than the reorder point Ri. It is indicated when M(POi) = 1.
PCiSpecify the end of the control of a station Si by the redistribution vehicle. M(PCi) = 1 means that the control of the station Si is completed and indicates that the redistribution vehicle is liberated to go to the next station.

Table 3.

Interpretation of places of the PN model

TransitionInterpretation
TRiTest and add (if necessary) bicycles into a station Si.
TOiTest if the number of bicycles available in a station Si is greater than the reorder point Ri.
TSiRemove bicycles from a station Si if the number of bicycles available in this station is judged less than the reorder point Ri
TEiTest if the number of bicycles available in a station Si is equal to the reorder point Ri

Table 4.

Interpretation of transitions of the PN model

ParameterInterpretation
RiReorder point fixed for each station Si. It is the minimum level of available bicycles in the station Si when a decision should be made to adding or removing bicycles into (from) the station (redistribution of bicycles between stations)
CiCapacity of each station Si. More precisely, Ci corresponds to the maximal number of bicycle stands in a station Si.

Table 5.

Decision parameters of the PN model

Thanks to the modularity of the developed model, its generalization for a system with N stations is simple to make according to the different functions cited previously. For example, to model N stations Si (i = 1, 2, …, N), we need to N places denoted by PSi and the control subnet is duplicated for each station similarly to the model represented for three stations (see Figure 6). Finally, by considering all the modules, the Petri net model representing a PBS system with N stations should contain:

|T|=N2+5*Ntransitions; |P|=4Nplaces; |Ad|=2*N2+21*Ndirected arcs, and |Ai|=N2+7*Ninhibitors arcs.

4.2. Description of the Petri net model

4.2.1. The “control stations” subnet

The subnet representing the control function of each station Si is indicated in Figure 6. As shown in the model, the considered subnet is duplicated for each station Si. We recall that, the main objective of the control function is to rebalance bicycles between stations that are emptying out and those that are filling. The control function of the system is realized by using three places denoted by PSi, PCi, PRi ; for transitions denoted by TEi TRi, TSi, TOi. As indicated in the tables 3 and 4, the place PSi represents a station Si; the place PRi represents the redistribution vehicle when visiting the station Si; and the place PCi means to indicate the end of the control operation of the station Si. When the redistribution vehicle arrives at a station Si, the state of this station is controlled. According to the number of bicycles available in the station, the decision to be made is either (a) to put bicycles in the station, or (b) to take bicycles from the station, or (c) take no action. The different operations are described and illustrated as follows.

  1. “Addition of bicycles to a station” operation: The decision to add bicycles in a station Si is performed by the transition TRi connected by the corresponding arcs to the places PRi and PSi. Indeed, the transition TRi means to verify the current number of bicycles in the station and to add (if necessary!) a given number (Ri – M(PSi)) of bicycles to the station Si. When the transition TRi is fired, Ri - M(PSi) tokens (bicycles) will be removed from the place PRi (the regulation vehicle) and at the same time, Ri - M(PSi) tokens (bicycles) will be added to the place PSi (the station Si). At the same time, one token will be deposited in the place PCi to indicate the end of the control of the station Si, and then the redistribution vehicle can travel to the next section Si+1.

    Figure 6.

    The Petri net model of a self-service public bicycles system (with three stations)

    Figure 7.

    “Control station” subnet illustration: The number of available bicycles in the station Si is less than Ri (i.e., M(Si) < Ri = 10)

    • Illustrative example 1.— As shown in Figure 7, consider that initially there are 7 available bicycles in the station S3 (i.e. M(PS3) = 7); 15 available bicycles in the redistribution vehicle (i.e. M(PR3) = 15); M(PC3) = 0; and the reorder point R3 is fixed to 10. For this marking, only the transition TR3 is enabled since the following enabling equations are satisfied:

  2. “Remove bicycles from a station” operation: The decision to remove bicycles (superfluous) from a station Si is made by the two transitions TOi and TSi. More precisely, the transition TOi means to test if the current number of bicycles in the station Si is greater than the reorder point Ri and the transition TSi allows us to remove bicycles (if necessary!) from the station Si and put them in the regulation vehicle. When the transition TOi is enabled, its firing will add a token into the place POi to indicate that the current number of bicycles in the station Si is greater than the reorder point Ri fixed for the station Si. This indication (i.e. M(POi) =1) is one of the enabling conditions of the transition TSi. When the transition TSi is enabled, its firing leads to remove M(PSi)-Ri bicycles (superfluous) will be removed from the station Si and, at the same time, they are deposited in the place PRi which represents the redistribution vehicle.

    • Illustrative example 2.— Now, as illustrated in Figure 8, consider that initially there are 15 available bicycles in the station S3 (i.e. M(PS3) = 15); 22 available bicycles in the redistribution vehicle (i.e. M(PR3) = 15); M(PC3) = 0; and the reorder point R3 is fixed to 10. For the current marking of the subnet, the transition TO3 is enabled, since:

      M(PS3)=1511;M(PO3)=0<1;M(PC3)=0<1.

      After the firing of the immediate transition TO3, a token will be placed in PO3 indicating that the current number of bicycles in the station S3 is greater than R3 = 10 (M(PS3)>10). That is:M(PO3)=M(PO3)+1=1. With this indication, the transition TS3 is systematically enabled, according to the following satisfied enabling equations:

      M(PS3)=1515;M(PO3)=11M(PC3)=0<1;M(PR3)=2210.

      Then, after the firing of the transition TR3, the state of the subnet will change as follows:

      M(PS3)=M(PS3)+[10M(PS3)]=10;

      M(PR3)=M(PR3)10+M(PS3)=2210+15=27;

      M(PC3)=M(PC3)+1=1;M(PO3)=M(PO3)1=0.

  3. “No action” operation: Contrarily to the two previous actions corresponding “to remove” or “to add” bicycles from (resp. into) the station Si, the “not action” function will be performed when the current number of bicycles in the controlled station Si is equal to the reorder point Ri. Testing that M(PSi) = Ri is made by the transition TEi with its corresponding arcs connecting the places PSi and PCi with the transition. The firing of TEi will not change the marking of the place PSi which represents the number of bicycles in the controlled station Si. Similarly to the two previous functions, after the firing of TEi one token will be deposited in the place PCi. This is to indicate the end of the control of the station Si and then the redistribution vehicle can travel at the next section by the firing a transition TRij in the Petri net model. This case is illustrated in Figure 9 where we consider M(PS3) = 10.

Figure 8.

“Control station” subnet illustration: The number of available bicycles in the station Si is greater than Ri (i.e., M(Si) > Ri = 10)

4.2.2. The “bicycle flows” subnet

A public bicycle system is a bank of bicycles which are continuously used by users to travel from one station to another. Thus, each bicycle of the system can be taken out from any station and returned to the same or any other station, provided that there is an available locking berth. The subnet representing the displacements of the bicycles between the different stations of the system is represented in Figure 10 and indicated in Figure 2. Each station Si of the system is modelled by using a place denoted by PSi. The bicycle flows is represented by the multiple token displacements from any place to the same or any other place by firing transitions denoted by TSij (possibly TSii) connecting the different places of the subnet. Each station Si is equipped with Ci bicycle stands. It is the capacity of each place PSi in the subnet. The parameter Ci represents the weight of the inhibitor arcs connecting the places PSi with the transition TSij. The inhibitor arcs are used in order to respect the capacity Ci of each station. According to the stochastic behavior of the bicycle flows between the different stations, the transitions of the subnet must be stochastic transitions.

4.2.3. The “redistribution circuit” subnet

As noted previously, the PBS system requires constant control which consists in transporting bicycles from stations having excess of bicycles to stations that may run out of bicycles soon. In our model, we consider that the vehicle(s) used to rebalance bicycles between stations visits successively stations S1, S2,…, SN.

Figure 9.

“Control station” subnet illustration: The number of available bicycles in the station Si is equal to Ri (i.e., M(Si) = Ri = 10)

As can be seen in the Figure 6, the places denoted by PRi (i = 1, 2, …, N), the transitions denoted by TRij (i j and i, j = 1, 2, …, N) and all of the corresponding arcs form a closed path. The resulting subnet represents a circuit which the redistribution vehicle follows in order to visit and to control successively the different stations of the network. When the redistribution vehicle arrives at a given station Si, the marking of the place PRi (i.e., M(PRi)) indicates the current available bicycles in the vehicle. The displacement of the vehicle from a station Si to another station Sj is modelled by the transition TRij. Obviously, the circuit is connected to the control subnet of the system. Indeed, each place PRi is connected to the three transitions TSi, TEi, and TRi in order to execute the control function of the station Si. The connection is made by the corresponding arcs.

Now, suppose that the control of a given station Si is finished. Then, the redistribution vehicle leaves the station Si and goes to the next section Sj. The firing of the enabled transition TRij leads to a new marking the place PCi, M’(PCi) = 0, indicating that the redistribution vehicle is arrived at the next station Sj with M(PRi) bicycles in its trailer. M(PRi) corresponds to the rest of bicycles just after the control of the previous station Si.

In the presented Petri net model (for three stations), we used a single redistribution vehicle for the control of the stations. Obviously, in practice, for a system with N stations implemented in a given city, the regulation can be performed by several redistribution vehicles which can be affected to different districts of the city. Thus, in the Petri net model, several redistribution vehicles and their circuits can be represented similarly to the example presented with one redistribution vehicle.

Figure 10.

The “bicycle flows” subnet.

5. Performance evaluation with simulation

Real systems are large and complex and so are the Petri nets used for their modelling and analysis. As the model complexity increases, the use of analytical techniques for analysis and performance evaluation becomes harder for many real-life applications or case studies. Despite the many free software tools available for Petri nets simulation and analysis, we had to develop our specific simulation tool in order to validate and analyze the performance of the models presented in this chapter. In fact, the “marking dependent weights” concept, which is an important feature to model self-service public bicycle systems, does not exist anywhere in the existing Petri nets simulation tools.

Our simulation tool has been developed by exploiting the BDSPN simulator recently realized by us [17]-[6] for the simulation of BDSPN models developed for the modelling and performance evaluation of inventory control systems and logistic systems where we also used the “marking dependent weights” concept. The developed simulation tool provides functions for calculating some important perfomance indices of the Petri net model. These indices can then be mapped to the system’s performance indices by the modeler. At the end of the simulation, some performance indices for places and transitions can be obtained. Some of them are formulated and interpreted for the performance evaluation of PBS systems as follows:

  1. Average number of tokens in a place P (Mavr(P)):

    Mavr(P)=M(P)τTsE5

    where M(P) is the number of tokens at the beginning of the cycle; Ts is the total simulation time and is the duration of the cycle. This performance indice can be used particulary to get the mean number of bicycles in each station Si and in the regulation vehicle(s) by computing the average marking of the corresponding places PSi and PRi.

  2. Mean sojourn time of tokens in a place (Savr(P)):

    Savr(P)=M(P)τNtE6

    where Nt is the number of different tokens that have passed through the place until the current cycle. The value of Nt can be obtained by incrementing a counter each time an input transition fires and put tokens in the place. M(P) is the number of tokens in the place P and is the duration of the cycle. By calculating the mean sejourn times of the places PSi, we get important informations about the the turnover (rotation) of bicycles between the different stations of the transport network.

  3. Effective firing rate of a transition T (Favr(T)):

    Favr(T)=NF(T)TsE7

    where Ts is the total simulation time; NF(T) is the number of firings of the transition. The firing rates of some transitions of the Petri net model, such as the transitions TRi, TSi, and TRij, measure some operations rates of the regulation function in order to quantify the dynamics of the system or some rates of specific activities.

  4. Rates of empty and full places (REmpty(P); RFull(P)):

    Rempty%(P)=100Ts(τkτk+1)M(P)=0TsE8
    Rfull(%)(P)=100Ts(τkτk+1)M(P)=CpTsE9

    where Ts is the simulation time (Ts ); (k - k+1) represente the the duration of the cycle where the place P is empty (resp. full) (i.e., M(P) = 0 resp. M(P) = Cp where Cp is the capacity of the place P). The performance indices are particularly interesting to measure the rates of two uncomfortable situations that can occur in the system. That is the case of empty and full stations which have necessary to be avoided.

6. Simulation and validation of the model

Now, the relevance of the Petri net model represented in Figure 6 and described in the previous sections is demonstrated through several simulations made for different interesting configurations of the system. They are defined according to the functions to be activated (or not) in the Petri net model of the PBS system.

  1. Configuration (a). The dynamic model with the regulation system: In this case, we consider the general functioning of the system. That is, stations are available for users and the system is under control to rebalance bicycles between stations that are emptying out and those that are filling up. The Petri net model represented in Figure 6 reproduces this case when all of its subnets are not disabled as it is the case in the following configurations (case b and case c).

  2. Configuration (b).The dynamic model without the regulation system: Unlike the first case, here, we consider that the regulation system is unavailable. So, the stations remain operational for users but without any control of the bicycle flows. According to the Petri net model, this configuration is obtained when the initial marking of all the places PRi is equal to zero. This configuration deactivates the redistribution vehicle path and the whole control function of each station.

  3. Configuration (c). The static model: This case represents the behavior of the system when the frequentation of the stations is very low (functioning of the system during night, for example). In terms of the Petri net model, this situation can be simulated by increasing considerably the transition firing delays of the transitions TSij which represent the displacements of bicycles between different stations. Similarly to the case B, the stations remain operational for users but without any control because (for the case c) of the limited bicycle flows.

6.1. Simulation of the PBS model under the configuration (a)

Let us consider the configuration (a) with the parameters given in the Table 6. The first part of the Table 6 gives the initial marking of the Petri net where we consider that initially there are 15 bicycles available in each station Si. In the second part of the table, we read the parameters Ri and Ci of the control function of the system. It is assumed that the reorder point Ri (resp. the capacity Ci) of each station is the same and fixed to 10 (resp. 20) bicycles. Finally, the table gives the parameters of the transitions of the Petri net model. For each transition, are indicated its nature which can be an immediate transition (I); a deterministic transition (D); or an exponential transition (E); its rule policy namely continue process (C) or restart process (R); and also its firing delay given in minutes (constant firing delay for deterministic transitions; zero firing delay for immediate transitions, and mean firing delay for stochastic transitions).

Configuration Of The Initial Marking Of The Model
M0(PS1)M0(PS2)M0(PS3)M0(PR1)M0(PR2)M0(PR3)
1515151000
M0(PS1)M0(PS2)M0(PS3)M0(PR1)M0(PR2)M0(PR3)
000000
Configuration Of The Parameters Ri And Ci Of The Petri Net Model
R1R2R3C1C2C3
101010202020
Configuration Of The Transitions Of The Model
TS11TS12TS13TS21TS22TS23
E, C, 20E, C, 5E, C, 10E, C, 5E, C, 20E, C, 5
TS31TS32TS33TR1TO1TS1
E, C, 10E, C, 5E, C, 20E, C, 3I, 0E, C, 3
TR2TO2TS2TR3TO3TS3
E, C, 3I, 0E, C, 3E, C, 3I, 0E, C, 3
TR12TR23TR31TE1TE2TE3
E, C, 15E, C, 15E, C, 15I, 0I, 0I, 0

Table 6.

Configuration data of the Petri net model

Considering all the parameters of this configuration, evolution graphs and some performances of the system can be established thanks to our simulation tool. We focus our attention on the behavior of the time evolution of the number of available bicycles in the stations which can be observed in Figure 11. According to the control function integrated in the model, it can be observed that the number of bicycles (marking the places PSi) in the three stations "oscillates" around the reorder point Ri (=10) and the capacity Ci (= 20) of each station is respected. Obviously, the dynamic behavior of this part of the system is similar to the one of inventory control systems [17].

As shown in Figure 12, the dynamic behavior of the redistribution vehicle can also be observed through the time evolution of the marking of the places PRi together. For the chosen parameters of the system, we see that there are always enough bicycles in the redistribution vehicle.

6.2. Simulation of the PBS model under the configuration (b)

As defined previously, in this configuration, we consider the dynamic model without the regulation system. Here, the initial markings of all the places M(PRi) are equal to zero. That is the only modification to be made in the Table 6 to obtain this situation. Thanks to this change, the redistribution vehicle path and all of the control function of each station are not available in the Petri net model (see Figure 6). Formally, for M(PRi) = 0 and M(PCi) = 0, the transitions TEi, TSi, TOi, TRi (control function) and TRij (displacement of the redistribution vehicle) are never enabled for this configuration. Consequently, the stations remain operationnal for users but whitout any control.

Figure 11.

Evolution of the number of available bicycles in the stations (configuration a)

Figure 12.

Evolution of the number of bicycles in the redistribution vehicle (configuration a).

Thanks to our simulator, the evolution time of the number of bicycles in the different stations is given in Figure 13. With regard to the first configuration (a), here, we see clearly the absence of the control functions of the system. It is observed that the stations are very frequently full. In contrast, empty stations are not observed in this configuration. This is only due to the parameters chosen for this case. Indeed, recall that we have 15 bicycles in each station (there are a total of 45 bicycles in the system) and the capacity of each station is fixed to 20. Thus, the minimal number of bicycles which can be found in a given station is 5 bicycles (Indeed, 45 - 20*2 (two full stations) = 5) which can be observed in the graphs.

Finally, the Table 7 gives some performances of the system for the two configurations obtained by computing the equations (5-9). The average number of available bicycles in each station is represented by the average marking of the places PSi. For the configuration A, Mavr(PSi) is approximately equal to 10 which is coherent with the reorder point Ri fixed to 10 for this configuration. In contrast, for the configuration B where the system is without the regulation function, the average number of bicycles in the stations is over 15. The rates of empty and full stations are also given in the table. The rate of empty and full stations (together), RF/F(PSi)=RFull(PSi)+REmpty(PSi), is estimated to 6.80% in the case of the configuration (a), and 51% in the case of the configuration (b) for each station.

Perf. evaluation of the configuration (a)
Mavr(PS1)Mavr(PS2)Mavr(PS3)
10,1810,1410,21
REmpty(PS1)REmpty(PS2)REmpty(PS3)
3.33%3.30%3.31%
RFull(PS1)RFull(PS1)RFull(PS1)
3.52%3.50%3.51%
RE/F(PS1)RF/E(PS1)RF/E(PS1)
6.85%6.80%6.82%
Perf. evaluation of the configuration (b)
Mavr(PS1)Mavr(PS2)Mavr(PS3)
15,7215,5715,53
REmpty(PS1)REmpty(PS2)REmpty(PS3)
0%0%0%
RFull(PS1)RFull(PS1)RFull(PS1)
51.0%51.1%50.8%
RF/E(PS1)RF/E(PS1)RF/E(PS1)
51.0%51.1%50.8%

Table 7.

Some performances indices of the model (for the considered parameters)

Figure 13.

Evolution of the number of available bicycles in the station 3 (configuration b)

As noted previously, to obtain the configuration c, the Petri net model shown in Figure 6 must be parameterized as in the configuration b but by increasing considerably the transition firing delays of the transitions TSij. Contrary to the behavior of the system shown in Figure 13, in this situation, we obtain a static model with very low (negligible) evolution of the distribution of the bicycles in the network.

7. Conclusion

In this chapter, we have presented an original Petri net approach for public bicycle sharing systems modelling and performance evaluation for control purposes. A modular dynamic model based on Petri nets with marking dependent weights is proposed and a simulation approach is developed and used to simulate and validate models described in this chapter. Very likely, this approach is the first one in the literature dedicated to this urban transportation mode by using Petri nets. The authors believe that this new area of research has significant promise for the future to help planners and decision makers in determining how to implement, and operate successfully these complex dynamical systems. Now, we are working in the following directions: (1) Development of some natural extensions of the models including more complex modelling features such as the application of other control strategies used for the latest systems which operate with smart technologies and provide users and controllers with real-time bike availability information; (2) Development of optimization methods for optimal control purposes. For example, the objective is how to search optimal values of the decision parameters Ri, Ci of the model in order to minimize the two uncomfortable situations M(PSi) = 0 (empty station) and M(PSi) = Ci (full station) that may occur in the different stations of the system.

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Karim Labadi, Taha Benarbia, Samir Hamaci and A-Moumen Darcherif (August 29th 2012). Petri Nets Models for Analysis and Control of Public Bicycle-Sharing Systems, Petri Nets - Manufacturing and Computer Science, Pawel Pawlewski, IntechOpen, DOI: 10.5772/47774. Available from:

chapter statistics

2077total chapter downloads

5Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Automated Petri-Net Modelling for Batch Production Scheduling

By Dejan Gradišar and Gašper Mušič

Related Book

First chapter

An Application of GSPN for Modeling and Evaluating Local Area Computer Networks

By Masahiro Tsunoyama and Hiroei Imai

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us