Distributed optimization in transportation and logistics networks

Article English OPEN
Wong, K.Y. Michael ; Saad, David ; Yeung, Chi Ho (2016)

Many important problems in communication networks, transportation networks, and logistics networks are solved by the minimization of cost functions. In general, these can be complex optimization problems involving many variables. However, physicists noted that in a network, a node variable (such as the amount of resources of the nodes) is connected to a set of link variables (such as the flow connecting the node), and similarly each link variable is connected to a number of (usually two) node variables. This enables one to break the problem into local components, often arriving at distributive algorithms to solve the problems. Compared with centralized algorithms, distributed algorithms have the advantages of lower computational complexity, and lower communication overhead. Since they have a faster response to local changes of the environment, they are especially useful for networks with evolving conditions. This review will cover message-passing algorithms in applications such as resource allocation, transportation networks, facility location, traffic routing, and stability of power grids.
  • References (41)
    41 references, page 1 of 5

    [1] J. R. Banavar, F. Colaiori, A. Flammini, A. Maritan, and A. Rinaldo, Topology of the Fittest Transportation Network, Phys. Rev. Lett. 84, 4745 (2000).

    [2] A. L. Barabási and R. Albert, Science 286, 509 (1999).

    [3] A. Bernstein, D, Bienstock, D, Hay, M. Uzunoglu, and G. Zussman, Clumbia University, Electrical Engineering Technical Report #2011- 05-06 (2011).

    [4] D. Bertsekas, Linear Network Optimization (MIT Press, Cambridge MA, 1991).

    [5] D. Bertsekas and R. Gallager, Data Networks (Prentice Hall, Englewood Cliffs, NJ, 1992).

    [6] S. Boettcher and A. G. Percus, Phys. Rev. Lett. 86, 5211 (2001).

    [7] S. Bohn and M. O. Magnasco, Structure, Scaling, and Phase transition in the Optimal Transport Network, Phys. Rev. Lett. 98, 088702 (2007).

    [8] S. Bounkong, J. van Mourik, and D. Saad, Phys. Rev. E 74, 057101 (2006).

    [9] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K. K. Saluja, in Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications, WSNA'02, 2002 (ACM, New York, 2002), pp. 42-48.

    [10] J. R. L. de Almeida and D. J. Thouless, J. Phys. A: Math. Gen. 11, 983 (1978).

  • Metrics
    No metrics available
Share - Bookmark