Recent methods in the literature to parallelize the traffic assignment problem consider partitioning a network into subnetworks to reduce the computation time. In this article, a partitioning method is sought that generates subnetworks minimizing the computation time of a decomposition approach for solving the traffic assignment (DSTAP). The aim is to minimize the number of boundary nodes, the interflow between subnetworks, and the computation time when the traffic assignment problem is solved in parallel on the subnetworks. Two different methods for partitioning are tested. The first is an agglomerative clustering heuristic that reduces the subnetwork boundary nodes. The second is a flow weighted spectral partitioning algorithm that uses the normalized graph Laplacian to partition the network. The performance of both algorithms is assessed on different test networks. The results indicate that the agglomerative heuristic generates subnetworks with a lower number of boundary nodes, which reduces the per iteration computation time of DSTAP. However, the partitions generated may be heavily imbalanced leading to a higher computation time when the subnetworks are solved in parallel separately at a particular DSTAP iteration. For the Austin network partitioned into four subnetworks, the agglomerative heuristic requires 3.5 times more computation time to solve the subnetworks in parallel. The results also show that the spectral partitioning method is superior for minimizing the interflow between subnetworks. This leads to a faster convergence rate of the DSTAP algorithm.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Network Partitioning Algorithms for Solving the Traffic Assignment Problem using a Decomposition Approach


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:


    Publication date :

    2018-10-10




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Solving airport gate assignment problem using Genetic Algorithms approach

    Ghazouani, Hammadi / Hammami, Moez / Korbaa, Ouajdi | IEEE | 2015


    An efficient approach to solving the road network equilibrium traffic assignment problem

    LeBlanc, Larry J. / Morlok, Edward K. / Pierskalla, William P. | Elsevier | 1975


    Algorithms for solving fisk's stochastic traffic assignment model

    Mingyuan Chen / Attahiru Sule Alfa | Elsevier | 1991



    Dynamic Traffic Assignment: Genetic Algorithms Approach

    Sadek, A. W. / Smith, B. L. / Demetsky, M. J. et al. | British Library Conference Proceedings | 1997