A Primal-Dual Algorithm for Link Dependent Origin Destination Matrix Estimation

G. Michau, N. Pustelnik, P. Borgnat, P. Abry, A. Nantes, A. Bhaskar, Edward Chin Shin Chung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)


© 2015 IEEE.Origin-destination matrix (ODM) estimation is a classical problem in transport engineering aiming to recover flows from every Origin to every Destination from measured traffic counts and a priori model information. Taking advantage of probe trajectories, whose capture is made possible by new measurement technologies, the present contribution extends the concept of ODM to that of link-dependent ODM (LODM). LODM also contains the flow distribution on links making specification of assignment models, e.g., by means of routing matrices, unnecessary. An original formulation of LODM estimation, from traffic counts and probe trajectories is presented as an optimization problem, where the functional to be minimized consists of five convex functions, each modeling a constraint or property of the transport problem: consistency with traffic counts, consistency with sampled probe trajectories, consistency with traffic conservation (Kirchhoff's law), similarity of flows having similar origins and destinations, and positivity of traffic flows. A proximal primal-dual algorithm is devised to minimize the designed functional, as the corresponding objective functions are not necessarily differentiable. A case study, on a simulated network and traffic, validates the feasibility of the procedure and details its benefits for the estimation of an LODM matching real-network constraints and observations.
Original languageEnglish
Article number7725515
Pages (from-to)104-113
Number of pages10
JournalIEEE Transactions on Signal and Information Processing over Networks
Issue number1
Publication statusPublished - 1 Mar 2017
Externally publishedYes


  • Convex optimisation
  • origin destination matrices
  • proximal primal-dual algorithm
  • traffic flows

ASJC Scopus subject areas

  • Signal Processing
  • Information Systems
  • Computer Networks and Communications

Cite this