Accendo Reliability

Your Reliability Engineering Professional Development Site

  • Home
  • About
    • Contributors
  • Reliability.fm
    • Speaking Of Reliability
    • Rooted in Reliability: The Plant Performance Podcast
    • Quality during Design
    • Critical Talks
    • Dare to Know
    • Maintenance Disrupted
    • Metal Conversations
    • The Leadership Connection
    • Practical Reliability Podcast
    • Reliability Matters
    • Reliability it Matters
    • Maintenance Mavericks Podcast
    • Women in Maintenance
    • Accendo Reliability Webinar Series
    • Asset Reliability @ Work
  • Articles
    • CRE Preparation Notes
    • on Leadership & Career
      • Advanced Engineering Culture
      • Engineering Leadership
      • Managing in the 2000s
      • Product Development and Process Improvement
    • on Maintenance Reliability
      • Aasan Asset Management
      • CMMS and Reliability
      • Conscious Asset
      • EAM & CMMS
      • Everyday RCM
      • History of Maintenance Management
      • Life Cycle Asset Management
      • Maintenance and Reliability
      • Maintenance Management
      • Plant Maintenance
      • Process Plant Reliability Engineering
      • ReliabilityXperience
      • RCM Blitz®
      • Rob’s Reliability Project
      • The Intelligent Transformer Blog
    • on Product Reliability
      • Accelerated Reliability
      • Achieving the Benefits of Reliability
      • Apex Ridge
      • Metals Engineering and Product Reliability
      • Musings on Reliability and Maintenance Topics
      • Product Validation
      • Reliability Engineering Insights
      • Reliability in Emerging Technology
    • on Risk & Safety
      • CERM® Risk Insights
      • Equipment Risk and Reliability in Downhole Applications
      • Operational Risk Process Safety
    • on Systems Thinking
      • Communicating with FINESSE
      • The RCA
    • on Tools & Techniques
      • Big Data & Analytics
      • Experimental Design for NPD
      • Innovative Thinking in Reliability and Durability
      • Inside and Beyond HALT
      • Inside FMEA
      • Integral Concepts
      • Learning from Failures
      • Progress in Field Reliability?
      • Reliability Engineering Using Python
      • Reliability Reflections
      • Testing 1 2 3
      • The Manufacturing Academy
  • eBooks
  • Resources
    • Accendo Authors
    • FMEA Resources
    • Feed Forward Publications
    • Openings
    • Books
    • Webinars
    • Journals
    • Higher Education
    • Podcasts
  • Courses
    • 14 Ways to Acquire Reliability Engineering Knowledge
    • Reliability Analysis Methods online course
    • Measurement System Assessment
    • SPC-Process Capability Course
    • Design of Experiments
    • Foundations of RCM online course
    • Quality during Design Journey
    • Reliability Engineering Statistics
    • An Introduction to Reliability Engineering
    • An Introduction to Quality Engineering
    • Process Capability Analysis course
    • Root Cause Analysis and the 8D Corrective Action Process course
    • Return on Investment online course
    • CRE Preparation Online Course
    • Quondam Courses
  • Webinars
    • Upcoming Live Events
  • Calendar
    • Call for Papers Listing
    • Upcoming Webinars
    • Webinar Calendar
  • Login
    • Member Home

by Larry George Leave a Comment

Origin-Destination Matrix and Travel Time Distribution Estimation, Without Survey Data

Origin-Destination Matrix and Travel Time Distribution Estimation, Without Survey Data

Bob Butler nuclear engineer, musician (www.pleasantonband.org), former city councilman and Mayor of Pleasanton, California  died October fifth https://www.pleasantonweekly.com/news/2021/10/14/what-a-week-remembering-bob-butler-former-pleasanton-mayor-and-councilman. He helped me get traffic counts data from the Pleasanton Traffic Department.

Image of Bob Butler
Bob Butler

The objective is to estimate origin-destination (O-D) matrix proportions and travel time distributions, without individual data, and use the matrix and distributions to help manage traffic. The traffic model is a network of k-dimension M/G/infinity nodes and edges connecting them. Data are transient arrivals and departure counts, without individual vehicle identification. Within nodes individuals turn or go straight randomly. Reconstruct route information by product and convolution.  

Pleasanton is in the armpit of the intersection of two major freeways: in the southeast corner of the highways 580 and 680 intersection. Freeway drivers cut through Pleasanton to avoid the congested freeway interchange. In year 2000, Pleasanton assigned city cars to follow cars getting off freeways and driving into the city to see where they went and whether they went through. Drivers complained about being followed. Popular sentiment and complaints stopped city cars from tracking people driving through town. 

Pleasanton changed traffic signal timing near freeway exits to discourage drivers from driving through town. Stopped cars backed up onto the freeways and caused accidents. I offered to help. 

Pleasanton traffic department gave me traffic counts in 15 minute intervals from major intersections around edges of city. The intersection data told how many cars go straight, turn left, or turn right, minute by minute. I produced nonparametric least squares estimates of vehicle O-D matrixes and travel time distributions. [George 2000] 

The Pleasanton O-D and travel-time traffic model is a network of M(t)/G/Infinity self-service queuing systems [Keilson and Servi] with non-stationary Poisson arrivals. Analyses of this kind of model have been called “network tomography,” https://en.wikipedia.org/wiki/Network_tomography [Castro et al.]. Leonard Kleinrock, a fellow UC Berkeley grad student, made a career analyzing the packet-switching Internet as networks of queues, https://nationalmedals.org/laureate/leonard-kleinrock/. 

Table 1. Typical Pleasanton data, vehicle counts starting at beginning of rush hours. I combined several intersections into N, S, E, and W. 

 Input   Output   
TimeNSEWNSEW
Start151045416447468
0:15127337143604310
0:3017745013342189
0:4585641113312910
1:009363413221276
1:15539226021286
1:30831231227215

Table 2. Simple O-D matrix. Body is proportion of inputs “From…” that go out “To…” “From 0” and “To 0” are those that originate in Pleasanton and those whose destination is within Pleasanton. 

O from\D to->From 0From NFrom SFrom EFrom W
To 00.00000.86400.00000.00000.7801
To N0.21360.00000.01350.00000.0721
To S0.18010.02850.00001.00000.0000
To E0.17550.01770.26790.00000.1479
To W0.43080.08990.71860.00000.0000
Sum11111

Table 3. Travel-time distribution estimates. Data counts were in 15-minute intervals, so could not quantify discrete probability density more finely. 

MinutesPleasanton originThrough Pleasanton
0-1510.979148
15-3000
30-4500.020852

The Pleasanton traffic manager didn’t understand O-D matrixes, probability distributions, or their use for managing traffic. In year 2009, Pleasanton stationed cheap labor at major intersections around edges of city to record license numbers of cars entering or leaving Pleasanton. That gave some sample data to estimate travel times through Pleasanton by license number. Some tollway operators are doing that using license-plate readers, to cite speeders or suspend their toll passes. 

Sample or population?

It’s human nature to doubt statistically significant conclusions based on a sample that is a small fraction of the population.

Air travel surveys ~10%, on the day surveyors choose. Commuter surveys have non-response, bias. People asked, “Why are they surveying me?” I want Origin-Destination matrix  population proportions and travel time distributions, without sample uncertainty.

The M/G/infinity self-service system service-time distribution G(t) can be estimated, without customer identification! Imagine the supermarket analog of estimating the probability distribution of time in store. Observe supermarket arrivals and departures, starting from the time the doors open but without identifying individual shoppers. The reliability analog is to regard products or parts as entering self-service when sold or installed, departing when they fail (complaints, failures, return, repair, replacements, spares sales, etc.): data required by GAAP! The traffic analog is to regard traffic as going into and coming out of a network of M(t)/G/infinity self-service systems plus some originating or terminating in Pleasanton. That uses population data!

Assume Poisson input at rate λ, service time distribution is G(t), and self-service. Output is Poisson at rate λG(t). Arrival and departure times or counts, without identification, are statistically sufficient to make nonparametric estimates of service-time distribution G(t). Same is true for non-stationary Poisson input M(t)/G/infinity systems. [https://accendoreliability.com/estimation-of-a-hidden-service-time-distribution-of-an-mt-g-%e2%88%9e-self-service-system/#more-450442]

Tandem M/G/infinity Self-Service Systems

Imagine two M/G/infinity self-service systems with the output of one being the input to the second. Input Poisson at rate λG1(t) to a second M(t)/G2/infinity self-service system. Output is Poisson at rate 

∫λG1(u)G2(t-u)dG1(u), (INTEGRATE[λG1(u)G2(t-u)dG1(u)]),

where the integral is from 0 to t. 

Estimate distributions G1(t) and G2(t) from input, intermediate, and output observation counts. Refer to diffusion approximation to tandem or parallel queues, [George, 1973], for generalizations or approximations to non-Poisson inputs.

Simple Traffic M/G2/∞2/p Model

Imagine two crossing M/G/infinity self-service systems, one North-South and the other East-West. Customers from N-S may switch to E-W and vice-versa with probability p (Figure 1). Assume p and travel-time distribution G(t) are the same regardless of directions. Assuming symmetry gives you twice as much data to estimate p and G(t)

Figure 1. Simple intersection modeled as two queuing systems

Observe 2 inputs and 2 outputs. Estimate average arrival rates λ1 and λ2 from input counts. Estimate p and G(t) from output counts t=1,2,…. 

r1(t) = ((1-p)λ1 +pλ2)G(t)

r2(t) = ((1-p)λ2 +pλ1)G(t)

M/G2/∞2/p with one observation at time t

Suppose you observe output counts r1(t) and r2(t) at time t, then

p = (λ2*r1(t) – λ1*r2(t)) / ((-λ1 + λ2)*(r1(t) + r2(t))) and  

G(t) = (r1(t) + r2(t))/(λ1 + λ2).

Solve the two linear equations in two unknowns obtained by equating observed and expected output rates. Estimate lambdas from input rates:

r1(t) = 4, r2(t) = 3, λ1 = 10, λ2 = 20 gives

p = 5/7 and G(t) = 7/30.

Solutions for several observations 

Use least squares estimation when more than one observation gives multiple solutions. If underdetermined, minimize sums of squared errors, SUM[(observed-expected)2]. For example:

r1(1) = 3, r2(1)= 4, r1(2) = 6, r2(2)= 8, l1 = 10, l2 = 20 gives

p = 0.285714, G(1) = 0.233333, G(2) = 0.466667. 

With multiple observations and different turn rates and travel times, p1, p2, G11(t), G12 (t), G21(t), G22(t) depend on whether you want answers at time t or for all (i,j) pairs. If the system of equations is overdetermined, take more observations. Solutions must be constrained to have 0<p<1 and G(t) increasing in t. I used Excel Solver

M(t)/Gk/∞k network with switching

Imagine a network of intersection nodes and connecting routes. The whole thing could be modeled as a (filtration of) Markov process using states as node arrival and departure counts at arrival and departure times. Observe node inputs and outputs; inputs can have nonstationary rates. Assume stationary switching and travel time distributions. Route frequency is product of switch probabilities (assuming independence). Travel time is convolution of intra-node travel time distributions. 

Summary

Estimation of O-D matrix proportions and travel time distributions doesn’t require customer or vehicle identification. Population data beats sample data. Least squares method works for transient processes: e.g. commutes, BART, other daily cycles and traffic light cycles.

References

Sharminda Bera and K. V. Krishna Rao , “Estimation of origin-destination matrix from traffic counts: the state of the art,” European Transport no. 49 (2011): 3-23  

George, L. L., “Origin-Destination and Travel-Time Distribution, Without Surveys,” INFORMS, Salt Lake City, May 2000 

George, L. L., “Diffusion Approximation for Two Channel, Poisson-Exponential Service Systems with Dependence,” Ph. D. thesis, University of California, Berkeley; Advisor, Richard E. Barlow, 1973

J. Keilson and L. D. Servi, “A Distributional Form of Little’s Law”, 1965, also Operations Research Letters, Volume 7, Issue 5, 1988, Pages 223-227, ISSN 0167-6377, https://doi.org/10.1016/0167-6377(88)90035-1. 

Rui Castro, Mark Coates, Gang Liang, Robert Nowak, and Bin Yu, “Network Tomography: Recent Developments,” 2003

Filed Under: Articles, on Tools & Techniques, Progress in Field Reliability?

« Is RCM Just for Maintenance?
Agile ERM #3 »

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Articles by Larry George
in the Progress in Field Reliability? article series

Join Accendo

Receive information and updates about articles and many other resources offered by Accendo Reliability by becoming a member.

It’s free and only takes a minute.

Join Today

Recent Articles

  • Self-Discipline Part 1
  • Is Safety Training Helpful?
  • FINESSE Facilitation: What Are Best Practices for Qualitative Assessment Analysis?
  • ISO 9001 Context and in the Real World, What do we do?
  • The Galvanic Corrosion Piping Trap!

© 2023 FMS Reliability · Privacy Policy · Terms of Service · Cookies Policy

This site uses cookies to give you a better experience, analyze site traffic, and gain insight to products or offers that may interest you. By continuing, you consent to the use of cookies. Learn how we use cookies, how they work, and how to set your browser preferences by reading our Cookies Policy.