Inferring origin–destination trip matrices from aggregate volumes on groups of links: a case study using volumes inferred from mobile phone data

Inferring origin–destination trip matrices from aggregate volumes on groups of links: a case study using volumes inferred from mobile phone data Noelia Caceres*, Luis M. Romero and Francisco G. Benitez Transportation Engineering, Faculty of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092, Seville, Spain SUMMARY The origin–destination matrix is an important source of information describing transport demand in a region. Most commonly used methods for matrix estimation use link volumes collected on a subset of links in order to update an existing matrix. Traditional volume data collection methods have significant shortcomings because of the high costs involved and the fact that detectors only provide status information at specified locations in the network. Better matrix estimates can be obtained when information is available about the overall distribution of traffic through time and space. Other existing technologies are not used in matrix estimation methods because they collect volume data aggregated on groups of links, rather than on single links. That is the case of mobile systems. Mobile phones sometimes cannot provide location accuracy for estimating flows on single links but do so on groups of links; in contrast, data can be acquired over a wider coverage without additional costs. This paper presents a methodology adapted to the concept of volume aggregated on groups of links in order to use any available volume data source in traditional matrix estimation methodologies. To calculate volume data, we have used a model that has had promising results in transforming phone call data into traffic movement data. The proposed methodology using vehicle volumes obtained by such a model is applied over a large real network as a case study. The experimental results reveal the efficiency and consistency of the solution proposed, making the alternative attractive for practical applications. Copyright © 2011 John Wiley & Sons, Ltd. KEY WORDS: transport demand; O–D matrix estimation; trafficflow; mobile phone data 1. INTRODUCTION The origin–destination (O–D) trip matrix is an essential source of information about traffic demand used by administrative authorities for proper strategic planning and management of road infrastructure networks. An O–D matrix is difficult and often costly to obtain by direct measurements/interviews or surveys, although one may obtain a ‘reasonable’estimate in a short term by using traffic counts and a prior O–D matrix. The prior O–D matrix is typically assumed to come from a sample survey and may be an old (probably outdated) matrix. Travel surveys are obtained through costly and laborious processes, which, from the initial data gathering to the result exploitation, are lengthy and may take years. Traffic counts are one type of information that can be collected automatically on a subset of links by fixed sensors embedded in the road (e.g. inductive loop, radio frequency identification (RFID), infrared, and camera). In most commonly used methods for matrix estimation, the prior O–D matrix is iteratively ‘adjusted’or ‘changed’to reproduce those observed *Correspondence to: Noelia Caceres, Transportation Engineering, Faculty of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092, Seville (Spain). E-mail: [email protected] Copyright © 2011 John Wiley & Sons, Ltd. JOURNAL OF ADVANCED TRANSPORTATION J. Adv. Transp. 2013; 47:650–666 Published online 14 October 2011 in Wiley Online Library (wileyonlinelibrary.com). DOI: 10.1002/atr.187 link volumes by means of modelling approaches. The reliability of sensor data is therefore critical for O–D matrix estimation. Combining loop data with other systems that also collect volume data might be of crucial importance for improving the efficiency and reliability of the estimated matrix. Other existing systems based on collecting volume data aggregated for groups of links are not used in matrix estimation methods. One example of these systems is those providing measures in standard ‘average daily traffic’format, aggregated in both directions (two links). Other technology that may also collect aggregate volumes is the mobile system. In most cases, the road network is denser than the cell distribution, so multiple roads may be covered by the same cell. The location accuracy provided without terminal and network modifications does not allow detection of movement of a handset along a particular road; it can only be asserted that it moves along one of the group of roads covered by the cell. Although mobile systems do not measure volumes as accurately as fixed sensors, volume data can be acquired on a wider coverage without additional costs arising. Thus, mobile phones can be regarded as a complementary solution to fixed sensors in order to enhance the available information for mobility monitoring purposes. The rationale behind it is the importance of the huge amount of data available at the mobile operators' database to be used as a rich source of information to diminish the uncertainty of mobility O–D matrices. Evidently, this type of data is complementary to other sources such as link trafficflow counts, licence plate recognition, audio video interleave data capturing techniques and RFID systems among others. The paper presents a methodology for matrix estimation using aggregate volume on groups of links. Traditional modelling approaches for matrix estimation are formulated to use volume data measured on single links, so the concept of aggregate volumes may be very useful to include any available volume data in the estimation process. It is evident that an aggregate scheme may also handle individual (disaggregate) links as a special group composed of a single link. Therefore, the approach may combine aggregate and disaggregate data from different sources, but for the sake of clearness, the attention is focused on just the aggregate case using volume inferred from mobile phone data. These systems have become widespread in collecting traffic data because they provide great advantages over traditional methods of traffic measurement. Anyway, this approach may also be applied using aggregated data from any other technology that collects aggregate volumes. This paper is organized as follows. In Section 2 a short review of matrix estimation approaches is provided, including related works about utilizing mobile phone data in transportation. Section 3 describes the model formulation and the solution method to estimate O–D matrices by means of aggregate volumes of groups of links. In Section 4, after introducing the mobility management strategy used in mobile systems, a method of inferring volume data from mobile phone counts is presented. A case study on a real network to demonstrate and verify the proposed method is summarized in Section 5. The last section concludes the paper with major findings and future extensions. 2. STATE OF THE ART 2.1. Origin–destination matrix estimation using classical modelling approaches The O–D matrix is important in describing transport demand within a given region. An origindestination matrix is difficult to obtain by direct measurements; observation of the population of interest in its entirety within a study area is not economically (or perhaps even technically) feasible. Then, traditionally O–D matrices have been estimated using different methodologies, such as carrying out surveys on a representative sample of individuals, applying a trip distribution model, or using traffic counts as measurements of link flows in a network model in order to update an existing matrix. The third alternative is the one that has mostly been used over the past 25 years, and a considerable amount of work has been documented in the literature [1]; a set of traffic counts and a prior O–D matrix are prerequisites. The prior matrix is typically assumed to come from a survey using a finite data set (instead of using the whole population). The survey data need to be corrected, expanded, and validated in order to achieve a representative and reliable prior matrix to be used in matrix estimation methods [2]. Therefore, this prior matrix can be regarded as an observation (a good approximation) of the ‘true’ 651 INFERRING ORIGIN–DESTINATION TRIP MATRICES Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr O–D matrix to be estimated. The way a prior matrix is obtained is profusely documented in specialized survey books and praxis protocols, and it is out of the scope of this paper to focus attention on this matter. However, the fact that a prior matrix is regarded as a ‘good approximation’of the ‘true’ O–D matrix does not imply that it can be used directly as a result. Travel surveys are undertaken every 5–10 years because they are costly and laborious processes; hence, prior O–D matrices are probably outdated. Furthermore, a few errors may arise during the processes of building, calibrating, and forecasting the prior matrix with models, such as sampling errors, measurement errors, transfer errors, or aggregation errors. The prior matrix is therefore updated using trafficflows, which are one type of information that can be collected automatically on a subset of links in a network, not on all links (this would be impossible nowadays because of economic budgetary restrictions). In methods based on this third alternative, the prior O–D matrix is iteratively ‘adjusted’or ‘changed’to reproduce the observed traffic counts when assigned to the transportation network. The aforementioned errors can also be mitigated by adjusting the prior O–D matrix to satisfy the traffic counts. In this manner, one may obtain a ‘reasonable’estimate of the O–D matrix; hence, this alternative is most widely used in practical applications. 2.2. Origin–destination matrix estimation using mobile phone data The incorporation of new technologies plays a key role in improving transportation applications. The idea of using mobile phones to acquire traffic information is more and more widespread. Various review studies relating to this topic have been published in recent years [3,4]. With the specific goal of O–D matrix calculations, a few simulation works have been carried out to evaluate the potential of using mobile data for estimation of travel demand [5,6], with a view to its practical applicability. Regarding matrices obtained from network operators' data, we can refer to works using call data in order to extract mobility information of individuals [7] and to identify home or work locations [8] or even studies using information retrieved from turned-on phones for generating trip distribution tables [9] or time–space trajectories [10,11]. According to the reviewed literature, the major drawback in the use of phone data for matrix estimation is the composition of the sample, which may be constituted by active phones only (in communication—call, SMS, MMS, etc.) or by idle phones as well (turned on and not in communication). Thus, the phone status when samples are collected drastically changes the size or the location accuracy of the data. A sample from only active phones would guarantee higher location accuracy because the mobile system always knows the server cell to which the active phone is connected during a communication. At present, cell identification (cell ID) is the basic geographic unit provided without terminal or network modifications. However, the sample size is much smaller than those from idle phones because the size depends on the number of calls. In contrast, a sample from idle phones offers less accurate location data. Whenever the phone has idle status, the system does not need to know the cell where a phone is located but needs to know a set of candidate cells for becoming the serving cell. This set is called the location area, which consists of a group of adjacent cells. When cells or location areas are used as home or work zones for building an O–Dmatrix,mobility patterns may be different from when using traditional traffic zones. The spatial extent of zones is of crucial importance for the understanding of trips that are generated and attracted within the zone. In conventional transport studies, a zoning system is defined according to transportation planning criteria, such as homogeneous land uses and/or population composition using census and socioeconomic data [2]. In mobile networks, generally base stations (cells) are placed to provide adequate coverage for communication rather than the aforesaid criteria. Moreover, cell size varies according to urban or rural areas and may cover areas with different land uses (e.g. home and work zones fit into the same cell); hence, the fitting problem is worse for location areas. However, even using cells (active phones sample), a typical traffic zone and a cell do not overlap exactly in both the size and the features of the area. Either poor network representations or too coarse zoning systems may invalidate the results of even the most theoretically appealing model [2]. Anyway, it is difficult to exactly detect the starting point and the destination of a trip by means of communication records; some users only have 1–2 records per day, and the points where users make calls may not coincide with a trip origin and destination. 652 N. CACERES ET AL. Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr There are other drawbacks to estimating O–D matrices directly from phone data, such as the uncertainty about the number of phones carried in the vehicles, or the fact that not every phone is under contract with the network operator that delivers the data. Therefore, phone trips do not match vehicle trips, and the matrix must be corrected by methods based on other vehicle-monitoring systems. Despite these drawbacks, an O–D matrix generated using phone data directly must be regarded as valuable prior information about the transport demand, and it can help to obtain more accurate results in future. Until now, the aforementioned modelling approaches based on traffic counts and a prior matrix remain the most reliable ones for matrix estimation. The preceding arguments provide the rationale for not drawing up O–D matrices directly from phone data but using the inferred flows between two adjacent/distant cells (inferred from call data) to update an existing prior matrix by solving an optimization problem. 2.3. Trafficflow estimation using mobile phone data The most used sensor to collect trafficflow data is the loop detector. Data provided by these sensors are available with little effort, but they are limited in terms of cost and coverage. Their measurements depend on the existing infrastructure, which tends to be expensive to extend or modify because of the cost of devices, installation, or maintenance. Although loops generally produce reasonable data all the time, they may occasionally provide missing values or erroneous measurements due to various malfunctions. There exist two main types of errors [12]: first, the detectors tend to undercount vehicles; second, a large percentage of detectors tend to count vehicles in neighbouring lanes in addition. By considering these negative aspects, other alternatives for collecting trafficflow data should be included for use in matrix estimation approaches. According to the literature, a fair number of works relating to trafficflow estimations using phone data have shown good quality results in order to be regarded as a feasible alternative for mobility detection purposes. Most of them use data generated by active phones. As already mentioned, a sample from only active phones guarantees higher location accuracy based on cell ID. Certainly, having a sample from idle phones increases the sample size, but location data are less accurate at the level of the location area, which consists of a group of adjacent cells. Then, the problem of matching users' movements to roads is more difficult to solve than using location data at cell level. This is the main reason why most studies so far have used datasets from active phones to obtain trafficflows, even though the sample size is smaller. Regarding active phones, the most common event for detecting the user's movement between two cells is the handover. A handover record is inserted into the system databases when a phone with a call changes from one base station/cell to another. The analysis of these records provides a measurement of the number of active phones moving from one cell to another in a given period, that is to say a boundary-crossing rate. Two works [13,14] found that the phones' flow from handover calls is closely related to the vehicles' flow measured by loop detectors, having similarities for most hours of an ordinary day. Typical flow peaks associated with times both in the morning and in the afternoon appear in both cases. However, those studies concluded that accurate vehicle flows cannot be obtained directly from phone data because of sample size problems. Flow data derived from active phones yield information on only a statistical sample of all the travelling vehicles; some vehicles may carry more than one mobile phone, either phones of other operators or switched-off phones; even no calls may occur per vehicle. For these last situations, phones in movement are not detected. These aspects imply special treatment to correlate phone and vehicle counts. A calibration process is therefore required that uses vehicle volume measures obtained, for example, from loop detectors located spatially in the same monitored section. In this regard, different works using loop detector data gave accurate results by means of procedures to bring phone counts to vehicle counts based on empiric transfer functions [15], correction factors [10], or Newtonian relaxation techniques [16]. In other recent work [17,18], a set of models containing additional information about calling users' behaviour was proposed to infer vehicle volumes from call data. The models have had promising results in transforming call data into traffic movement data, which makes it possible to calculate accurate trafficflows on any road in any period. 653 INFERRING ORIGIN–DESTINATION TRIP MATRICES Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr Considering the findings in the field of O–D matrices and trafficflows, a methodology for matrix estimation that combines the traditional modelling approaches with trafficflows inferred from mobile phones is proposed. A mixed approach makes phone data attractive for matrix estimation applications because of the fact that they involve relatively low costs and wider coverage. However, the methodology continues to use a matrix derived from a sample survey as a prior matrix. Survey data offer the possibility of obtaining more useful trip data (trip purpose, transportation mode, trip length, etc.). At present, these pieces of information cannot be derived accurately from raw phone data, and they are necessary for the other stages in travel demand modelling. 3. METHOD FOR UPDATING ORIGIN–DESTINATION MATRICES 3.1. Introduction As already commented, most methods for matrix estimation use volumes on a subset of links and a prior O–D matrix so that the prior matrix is iteratively updated to reproduce the observed volumes. The matrix estimation problem can then be interpreted as pursuing two types of objectives, of which one is to fit the traffic counts as exactly as possible and the other is to search for a solution that is as close as possible to the prior matrix. Better matrix estimates can be obtained when information is available about the overall distribution of traffic through time and space. Other existing technologies are not used in matrix estimation methods because they collect volume data aggregated for groups of links, rather than on single links. The new feature of this contribution with respect to the traditional modelling approaches is the use of aggregate volumes on groups of links. Some modifications in the model formulation to use aggregate volumes must therefore be developed. Anyway, it is evident that an aggregate scheme may handle individual (disaggregate) links as one group composed of a single link. The proposed methodology does not exclude the use of information coming from either link volume data or other sources. 3.2. Mathematical formulation Consider a study area that has been partitioned into traffic zones with trips from any origin to all destinations. Each traffic zone is represented by a node called a centroid, where trips originate or terminate. An O–D trip matrix is denoted by T = [T ij ], its (i,j) element being the number of trips from origin ito destination jduring a certain period. A road network corresponding to the study area is abstracted into a graph model consisting of a set of regular nodes and a set of directed links. The service level associated with the links is given by link performance functions s a (v a ), which relate the travel time on each link to the flow across the link. Finally, the assignment of the matrix to the network model in order to obtain flow and travel time on each link is considered to be a deterministic (or stochastic) user-equilibrium procedure, whose behavioural principles are described by the two conditions usually attributed to J.G. Wardrop [19]. Regarding the adjustment problem, we have reformulated it to use aggregate volumes on groups of links. The formulation proposed to adjust the prior matrix includes a quadratic term to control deviations with respect to the observed volume data; the distance between prior and estimated matrices is controlled by a set of variable bounds and functional constraints, which define admissible ranges for individual O–D pairs, zone productions and attractions, and total number of trips. Therefore, it must be noted that we are not really minimizing the distance between both matrices but limiting the variations involved to certain feasible intervals. Next, the necessary mathematical conventions to formulate the matrix adjustment bi-level approach are summarized. Indices and sets: i2IOrigin zones (n o is the total number of origin zones) j2JDestination zones (n d is the total number of destination zones) a2ANetwork links 654 N. CACERES ET AL. Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr g2GGroups of links observed k2K ij Routes or paths from origin ito destination j Constants: d ak 1 if link abelongs to path k, 0 otherwise d a|g 1 if link abelongs to group g, 0 otherwise u ij ,l ij Upper and lower bounds for (i,j)O–D pair u i O ,l i O Upper and lower bounds for trips generated by zone i u j D ,l j D Upper and lower bounds for trips attracted by zone j u,lUpper and lower bounds for total network trips  v| g Observed travel demand through the group of links g a| g (Optional) weight factor associated with the volume on group of links g Functions: s a (v a ) Performance (volume delay or cost) function of link a Variables: v a Volume on link a h k Flow on path k pk¼hk Tij Probability or proportion of path k Pij;a¼P k2Kij dakpkProportion of trips from node ito node jthrough the link a v| g Estimated travel demand through the group of links g T ij Travel demand (trips) from origin ito destination j. Then, the bi-level approach proposed in this investigation is formulated as follows:  Upper Level Minimize Tij fT ij  ¼1 2X g2 ^ G ajgðvjg vg 2 s:t:lij≤Tij≤uij 8i2I;j2JaðÞ lO i≤P j2J Tij≤uO i8i2IbðÞ lD j≤X i2I Tij≤uD j8j2JcðÞ l≤P i2IP j2J Tij≤udðÞ  Lower Level Minimize va gv a ðÞ¼ X a2AZva 0 savðÞdv s:t:va¼X i2IX j2JX k2Kij dak hk;8a2A X k2Kij hk¼Tij;8i2I;j2J hk≥08k2Kij;i2I;j2J  (1) The lower-level programme, known as Beckmann's transformation, is the basic model for obtaining those volumes v a on all network links satisfying the user-equilibrium conditions for a given fixed demand T ij [19]. In order to obtain the aggregate volume v| g on every group g2G, it is necessary to carry out a sub-problem assignment that provides the standard results of the lower level (Equation (1)). The results can then be expressed in terms of path flows or path proportions as follows: vjg¼X a2g va¼X a2A dajgva¼X a2A dajgðX i2IX j2J Tij X k2Kij dakpk Þ ¼X a2A dajgðX i;j TijPij;a Þ8group g2G (2) Expression (2) shows that the aggregate volume on the group of links gis the sum of the volume on each link belonging to the group. The problem of estimating an O–D matrix from the aggregate 655INFERRING ORIGIN–DESTINATION TRIP MATRICES Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr volume consists in finding the values of n o n d variables (T ij ) from as many equations as there are independent observed volumes in the network. In most cases, the number of unknowns is greater than the total number of independent equations that can be found for the groups of links having the counts, so it will not be possible to determine a unique matrix, and the problem is underspecified. Thus, the objective of the estimation process becomes the estimation of a solution that is considered to be the best one according to some criteria. For the present approach, the criteria have already been set out and mathematically modelled in the upper level (Equation (1)) by means of the set of variable bounds (a) and functional constraints (b–d). Because of the existing uncertainty in the definition of the matrix, potential errors in the definition of the transportation network model, and noise associated with the vehicle counts, the rationale behind this makes reasonable that all the matrices in an adequate range can be considered equally suitable. In the formulation proposed, two different strategies manage the constraints, according to the type: the bounded constraints (restrictions on each element of the matrix) and the functional constraints (constraints on origin-row, on destinationcolumn aggregations, and on total number of trips). For instance, for an outdated 5-year-old matrix to be brought up-to-date with the actual vehicle counts, one can use the outdated matrix as a prior matrix, letting the total target matrix trips vary into an interval ranging from the outdated total trips (it is not usual for mobility to decrease in 5 years) and the predicted percentage increment by the time series record (lower and upper constraints on total trips). The constraints provide a better physical perception to pick out the most suitable matrix (for example, constraints might be imposed restricting the admissible variations to 20% in the trips production of a concrete traffic analysis zone, or accepting an increase greater than 15% in total mobility). These conditions would be part of the functional constraints and treated as terms of a new objective function, defined by the augmented Lagrangian function (ALF). Consequently, this type of constraint can be regarded as a function of some metrics (distance). The bounded constraints require a different treatment because of the large number of restrictions, their augmented Lagrangian would impose 2 n o n d additional terms in the objective function; this makes the optimization problem intractable, an approach to encircle this issue is dealt in the following section. 3.3. Implementation As mentioned earlier, the formulation using aggregate volume of groups of links is needed in order to use other available data from systems providing aggregate measurements. According to the literature, there are a large number of works that have already developed methodologies to estimate O–D matrices using link volumes. The approach followed in this research has selected one of these previously developed methods [20] as the starting point for the reformulation using volumes on groups of links. The reformulation and the validation of the resulting algorithm is a simple and unproblematic task that has never been used in matrix estimation to our knowledge, but it can be very useful for combining any available volume data in order to improve efficiency in matrix estimation. The selected method addresses the problem of estimating and updating observed O–D matrices based upon available link-flow information, preserving the prior structure of a survey matrix. Although the modification could be applied to any approach using observed link volumes, we have selected the cited method because of the well-behaved results that the method has obtained in matrix estimation. This approach combines an augmented Lagrangian method, called the method of multipliers, with the linear approximation method credited to Frank and Wolfe. The idea of the augmented Lagrangian scheme [21] consists of adding a quadratic loss penalty term to the classical Lagrangian to form an unconstrained function whose minimum is a Kuhn–Tucker point of the original problem. However, note that the ALF proposed here will not be completely unconstrained because variable bounds will not be included. In the model, the Lagrangian function includes the functional restrictions (corresponding to trips generated, attracted, and total) present in Equation (1b)–(1d) but bound ones associated with trips between O–D pairs in Equation (1a), which are those dealt with directly by the Frank–Wolfe method. The use of these functional restrictions and variable bounds limits the possible changes in the estimated matrix regarding the information contained in the prior matrix. For the sake of brevity, the details of the mathematical optimization 656 N. CACERES ET AL. Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr scheme are not pursued further and can be found in [20]. Then, the ALF for aggregate volume data can now be written as follows: Laug T;s;tðÞ¼ 1 2X g2 ^ GX i2IX j2J ajgX a2g ð Tij X k2Kij dakpk 0 @1 A vjg Þ 2 þ1 2X no i¼1 oO iuO iX nd j¼1 Tij þsO i *+ 2 sO i  2 0 @1 AþX no i¼1 oO iX nd j¼1 Tij lO iþtO i *+ 2 tO i  2 0 @1 A 0 @1 A þ1 2X nd j¼1 oD juD jX no i¼1 Tij þsD j *+ 2 sD j  2 0 @1 AþX nd j¼1 oD jX no i¼1 Tij lD jþtD j *+ 2 tD j  2 0 @1 A 0 @1 A þ1 2ouX no i¼1X nd j¼1 Tij þs *+ 2 s2 0 @1 AþX no i¼1X nd j¼1 Tij lþt *+ 2 t2 0 @1 A 0 @1 A; where ahi¼ aifa<0 0ifa≥0 (3) and (o i O ,o j D ,o) are the weight factors associated with the production constraints of zone i, the attraction constraints of zone j, and the total number of trips constraint, respectively. Lastly, s={s O ,s D }, t={t O ,t D } stand for vectors of multipliers associated with the mentioned constraints. The updating rule for sand ttakes the following form: smþ1ðÞ i¼uO iX nd j¼1 TmðÞ ij þsOmðÞ i *+ tmþ1ðÞ i¼X nd j¼1 TmðÞ ij lO iþtOmðÞ i *+ ;for each i2I smþ1ðÞ j¼uD jX no i¼1 TmðÞ ij þsDmðÞ j *+ tmþ1ðÞ j¼X no i¼1 TmðÞ ij lD jþtDmðÞ j *+ ;for each j2J smþ1ðÞ ¼uX no i¼1X nd j¼1 TmðÞ ij þsmðÞ *+ tmþ1ðÞ ¼X no i¼1X nd j¼1 TmðÞ ij lþtmðÞ *+ (4) Let mbe the counter to identify the successive estimates obtained by the algorithm. Then, the updating rule of the successive estimates of the Frank–Wolfe algorithm can be written as T ij (m+1) =T ij (m) +l (m) (y ij (m) T ij (m) )=T ij (m) +l (m) d ij (m) for each i2I,j2J, in accordance with the O–D notation. Note that d ij (m) =y ij (m) T ij (m) is the Frank–Wolfe descent direction, y ij (m) is the auxiliary extreme point, and l (m) is the step length in the mth iteration. This step is subject to lying within the interval l2[0,1] because the auxiliary point yis located in a vertex (and/or edge) of the feasible region defined by the linear problem. To obtain the step length, the ALF (Equation (3)) should be minimized by expressing it as a function of lat the new m+ 1 estimate, that is, evaluating the function for T ij (m+1) =T ij (m) +l (m) d ij (m) where T ij (m) and d ij (m) are known. Thus, a minimization of this one-dimensional function, where l2[0,1], has to be performed. Because of the numerical oscillations of the objective function values observed in the cited optimization approach, additional novelties for determining the optimum step have been developed. In this regard, the presence of the bracket operator hi has motivated the selection of the Golden Section Search algorithm for minimizing a quasi-convex function over the interval [a,b]. This algorithm is based on finding the minimum of the unimodal function by successively narrowing the range of values of l. In our problem, the optimum value of lis found by applying this algorithm iteratively within the interval l2[0,1] in the descent direction d ij (m) . The termination criteria of the algorithm designed are based on the following: (i) the maximum number of sub-problems (or Lagrangian stages) and (ii) the maximum number of iterations per sub-problem. 657 INFERRING ORIGIN–DESTINATION TRIP MATRICES Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr Specific rules are used to choose these maximum numbers of steps, and so, as was the case of the upper and lower bounds in Equation (1), they depend on error analysis and statistical confidence intervals. 4. ESTIMATES OF TRAFFIC VOLUMES FROM MOBILE PHONE DATA 4.1. Introduction In mobile networks, a service coverage area is divided into smaller areas referred to as cells. A cell is defined as the area in which a phone can communicate with a certain base station. A set of adjacent cells is grouped into one location area. The cell radius depends on many parameters, such as antenna type, power levels, or even topology and buildings around. The cell radius is smaller in urban areas, where population density is high and more antennae are necessary to provide good communication services, than in rural areas, varying from a few hundred metres to several kilometres. One of the main features of mobile systems is the ability of users to access communication services from any location within the telecommunications network. To support users' mobility, the mobile phone network has an inbuilt positioning system based on the cell of origin, which is used to keep track of the position of phones so as to deliver incoming calls, messages, or data packets to subscribers. When a call occurs, the system inserts a record into its databases including parameters related to the call such as start/end time, duration, caller phone number, or identification of the server cell (cell ID). During a call, the mobile system always knows the server cell to which the phone is connected in order to route the call to the antenna. Because subscribers are free to move within the network's service area, the mobility management in mobile networks includes processes that keep the databases updated with the user's position. When a phone with a call moves from one cell to another (it crosses the boundary of different cells), the call is routed to the new cell. The transference is executed by the handover process, which automatically updates the databases with the new cell ID and the time stamp. More details about mobile systems can be found in the literature [22]. The information about phones crossing inter-cell boundaries is related to the estimation of users moving from one area to another. Therefore, a mobile system can be regarded as a kind of detector monitoring the movement of phones with calls through inter-cell boundaries. The topology of a road network is complex, and several roads may connect two cells. By analysing the road network topology and cell distribution, the routes connecting two cells are identified; in Figure 1a, there are two routes connecting cell 1 and cell 3, but only one route connects cell 1 and cell 2. By representing the road network by nodes and links, an inter-cell boundary comprises the group of links whose starting node is in one cell and whose ending node is in another cell (Figure 1b). The ideal situation is to have a large set of individual links where the movement of phones can be analysed independently. Unfortunately (indeed fortunately), in most cases, the road network is denser than the cell distribution, so multiple links connect two cells. In this case, there is no certainty that a particular handset is moving along a particular link; it can only be asserted that it is moving along one of the roadways connecting two cells. In this case, an aggregate data approach is more valuable because it allows the number of observed links to be increased. If only volume data inferred from mobile networks at the individual link level cell 1→cell 3 Group 1={1 , 3} cell 3 → cell 1 Group 2 = { 2 , 4 } cell 1 → cell 2 Group 3 = { 5 } cell 2 → cell1 Group 4 = { 6 } cell 1 cell 2 cell 3 3 1 2 k i j s 23 4 5 6 cell 1 cell 2 cell 3 1 (a) (b) Figure 1. Groups of (a) roads and (b) links in a transport network. 658 N. CACERES ET AL. Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr to another. Utilizing existing mobile systems has a major advantage compared with other trafficflow capturing techniques because it avoids cost and coverage limitations associated with infrastructurebased solutions. The relatively low costs and wider-coverage data make mobile systems attractive for use as a complementary solution for collecting traffic volumes when detector data are unavailable or insufficient. Mobile phones sometimes cannot provide location accuracy for estimating flows on single links but can do so on groups of roadways (links) connecting two either adjacent or distant cells. After reviewing the state of the art, this paper presents a methodology adapted to the concept of volume aggregated on groups of links in order to use any available volume data source. To calculate volume data, we have used a model that transforms phone call data into traffic movement data. In comparison with measurements provided by counting stations, volumes inferred from call data achieve reasonable accuracy for use in matrix estimation. By applying the methodology for matrix estimation to vehicle volume obtained by the model, the experimental results reveal the efficiency and consistency of the solution proposed in comparison with a similar study using loop data. The most important objectives that have been reached are as follows: (i) mobile phone technology is proposed as a feasible system to infer aggregate volume on groups of links to be used as observed data for O–D matrix estimation; an aggregate scheme has never been used in matrix estimation to our knowledge, and it has great potential for combining any available data source and obtaining more accurate matrices; (ii) reformulation of the objective function taking aggregate volume notation into account; and (iii) numerical validation of the proposed methodology. Other minor contributions are as follows: (iv) analytical expressions for the gradient of the new objective function; and (v) methodological changes to correct oscillations observed in applying the optimization method, using the golden section algorithm instead of a bisection search. Future works are oriented towards developing mixed formulations using O–D matrices and trafficflows derived from phone data, as well as from traditional techniques (e.g. field surveys, loop detectors, and cameras). ACKNOWLEDGEMENTS This project was financed by the Spanish Ministry of Science through R&D National Programmes (TRA2005-09138, ENE2008-05552) and by Vodafone Spain through the Minerva Project (1C-021). REFERENCES 1. Abrahamsson T. Estimation of origin–destination matrices using traffic counts—a literature survey. Report IR-98021, Int. Institute for Applied Systems Analysis, 1998. 2. Ortuzar J de D, Willumsen LG. Modelling Transport. Third edn. John Wiley and Sons, Ltd.: West Sussex, England, 2001. 3. Caceres N, JP Wideberg, Benitez FG. Review of traffic data estimations extracted from cellular networks. IET Intelligent Transport Systems 2008; 2(3):179–192. 4. Qiu Z, Jin J, Cheng P, Ran B. State of the art and practice: cellular probe technology applied in ATIS. Transportation Research Board, 86th Annual Meeting, 2007; paper no. 07-0223. 5. Sohn K, D Kim. Dynamic origin–destination flow estimation using cellular communication system. IEEE Transaction on Vehicular Technology 2008; 57(5):2703–2713. 6. Zhang Y, Qin X, Dong S, Ran B. Daily O–D matrix estimation using cellular probe data. Transportation Research Board, 89th Annual Meeting, 2010; paper no. 10–2472. 7. White J, Wells I. Extracting origin destination information from mobile phone data. 11th International Conf. on Road Transport Information and Control, 2002; pp. 30–34. 8. Ahas R, Silm S, Saluveer E, Järv O. Modelling home and work locations of populations using passive mobile positioning data. In Location Based Services and TeleCartography II, Gartner G, Rehr K (Eds). Springer: Berlin, 2009; 301–315. 9. Pan C, Lu J, Di S, Ran B. Cellular-based data-extracting method for trip distribution. Transportation Research Record 1945, Journal of the Transportation Research Board, National Research Council, Washington, D.C., 2006; 33–39. 10. Friedrich M, Immisch K, Jehlicka P, Otterstätter T, Schlaich J. Generating OD matrices from mobile phone trajectories. Transportation Research Board,89th Annual Meeting, 2010; paper no. 10-1972. 11. Schlaich J, Otterstätter T, Friedrich M. Generating trajectories from mobile phone data. Transportation Research Board, 89th Annual Meeting, 2010; paper no. 10-0374. 12. Lehnhoff N. Quality of automatic data collection with loop detectors. Proc. of the 2nd International Symposium “Networks for Mobility”, 2004; Stuttgart, Germany. 665INFERRING ORIGIN–DESTINATION TRIP MATRICES Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr 13. Höpfner M, Lemmer K, Ehrenpfordt I. Cellular data for traffic management—first results of a field test. ITS Europe Conference, 2007; paper no. 2407. 14. Thiessenhusen KU, Schäfer RP, Lang T. Traffic data from cell phones: a comparison with loops and probe vehicle data. ITS World Congress, 2006; paper no. 1550. 15. Bekhor S, Hirsh M, Nimre S, Feldman I. Identifying spatial and temporal congestion characteristics using passive mobile phone data. Transportation Research Board, 87th Annual Meeting, 2008; paper no. 08-1534. 16. Herrera J, Bayen A. Trafficflow reconstruction using mobile sensors and loop detector data. Transportation Research Board, 87th Annual Meeting, 2008; paper no. 08-1868. 17. Caceres N, Romero L, Benitez FG, del Castillo JM. Trafficflow estimates inferred from mobile phone networks. 12th World Conference on Transport Research, 2010; paper no. 2720. 18. Caceres N. Mobility matrix estimate by using mobile phone data (in Spanish). Ph.D. Thesis Dissertation, Univ. of Seville, Spain. 2010; http://www.esi2.us.es/GT/docs/TesisNCS.pdf. 19. SheffiY. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Inc.: Englewood Cliffs, NJ, 1985. 20. Doblas FJ, Benitez FG. An approach to estimating and updating origin–destination matrices based upon traffic counts preserving the prior structure of a survey matrix. Transportation Research Part B, 2005; 39(7):565–591. 21. Reklaitis GV, Ravindran A, Ragsdell KM. Engineering Optimization: Methods and Applications. John Wiley & Sons, Inc.: New York, 1983. 22. Wakefield T, McNally D, Bowler D, Mayne A. Introduction to Mobile Communications: Technology, Services, Markets. Auerbach Publications: Boca Raton, FL, 2007 23. Sallent O, Perez-Romero J, Umbert A, Agusti R. Teaching wireless telecommunications: experiencing the network to stimulate the learning process. International Technology Education and Development Conference. 2008; 1–5. 666 N. CACERES ET AL. Copyright © 2011 John Wiley & Sons, Ltd. J. Adv. Transp. 2013; 47:650–666 DOI: 10.1002/atr