A Differential Evolution for Optimization of Multiobjective Urban Transit Routing Problem

  • Authors

    • Ahmed Tarajo BUBA
    • Lai Soon LEE
    2018-09-01
    https://doi.org/10.14419/ijet.v7i3.20.18999
  • transit network design, differential evolution, repair mechanism, urban routing.

  • Abstract

    In this paper, the urban transit routing problem is addressed by using a real-world urban transit network. Given the road network infrastructure and the demand, the problem consists in designing routes such that the service level as well as the operator cost are optimized. The optimality of the service level is measured in terms of average journey time and the route set length. A differential evolution approach is proposed to solve the problem. An improved sub-route reversal repair mechanism is introduced to deal with the infeasibility of route sets. Computational results on a real network produce solutions that are close to the lower bound values of the passenger and the operator costs. In addition, the proposed algorithm produces approximate Pareto fronts that enable the transit operator to evaluate the trade-off between the passenger and passenger costs.

     

  • References

    1. [1] Arbex, R.O. and C.B. da Cunha, 2015. Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm. Transportation Research Part B: Methodological, 81: 355–376.

      [2] Baaj, M.H. and H.S. Mahmassani, 1991. An AIâ€based approach for transit route system planning and design. Journal of Advanced Transportation, 25(2): 187-209.

      [3] Bagherian, M., S. Massah, and S. Kermanshahi, 2013. A swarm based method for solving transit network design problem. Proceedings of the 36th Australasian Transport Research Forum, Brisbane, Australia.

      [4] Bagloe, S.A. and A. Ceder, 2011. Transit network design for actual size networks. Transportation Research Part B, 45: 1787–1804.

      [5] Beasley, D., D.R. Bull, and R.R. Martin, 1993. An overview of genetic algorithms: part 2, research topics. University Computing, 15(4): 170–181.

      [6] Buba, A.T. and L.S. Lee, 2016a. Urban transit network design problems: a review of population-based metaheuristics. Pertanika Journal of Scholarly Research Review, 2(3): 86–99.

      [7] Buba, A.T. and L.S. Lee, 2016b. Differential evolution for urban transit routing problem. Journal of Computer and Communications, 4: 11–25.

      [8] Chakroborty, P. and T. Wivedi, 2002. Optimal route network design for transit systems using genetic algorithms. Engineering Optimization, 34(1): 83–100.

      [9] Chew, J.S.C., L.S. Lee, and H.V. Seow, 2013. Genetic algorithm for biobjective urban transit routing problem. Journal of Applied Mathematics, 2013. Article ID 698645, 15 pages.

      [10] Dijkstra, E.W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1): 269–271.

      [11] Fan, L. and C.L. Mumford, 2010. A metaheuristic approach to the urban transit routing problem. Journal of Heuristics, 16(3): 353–372.

      [12] Farahani, R.Z., E. Miandoabchi, W.Y. Szeto, and H. Rashidi, 2013. A review of urban transportation network design problems. European Journal of Operational Research, 229(2): 281–302.

      [13] Guihaire, V. and J-K. Hao, 2008. Transit network design and scheduling: a global review. Transportation Research Part A: Policy and Practice, 42(10): 1251–1273.

      [14] Ibarra-Rojas, O., F. Delgado, R. Giesen, and J. Muñoz, 2015. Planning, operation, and control of bus transport systems: a literature review. Transportation Research Part B: Methodological, 77: 38–75.

      [15] John, M.P., C.L. Mumford, and R. Lewis, 2014. An improved multi-objective algorithm for the urban transit routing problem. In: Blum, C., Ochoa, G. (eds) Evolutionary Computation in Combinatorial Optimisation. EVOCOP Lecture Notes in Computer Science, vol 8600. Springer, Berlin, Heidelberg.

      [16] Kechagiopoulos, P.N. and G.N. Beligiannis, 2014. Solving the urban transit routing problem using a particle swarm optimization based algorithm. Applied Soft Computing, 21: 654–676.

      [17] Kepaptsoglou, K. and M. Karlaftis, 2009. Transit route network design problem: review. Journal of Transportation Engineering, 135: 491–505.

      [18] Kiliç, F. and M. Gӧk, 2014. A demand based route generation algorithm for public transit network design. Computers and Operations Research, 51: 21–29.

      [19] Lee, Y.J. and V.R. Vuchic, 2005. Transport network design with variable demand. Journal of Transportation Engineering, 131(1): 1–10.

      [20] Mandl, C.E., 1980. Evaluation and optimization of urban public transportation networks. European Journal of Operational Research, 5(6): 396–404.

      [21] Mumford, C.L., 2013. New heuristic and evolutionary operators for the multi-objective urban transit routing problem. 2013 IEEE Congress on Evolutionary Computation, 939–946.

      [22] Nayeem, M.A., M.K. Rahman, and M.S. Rahman, 2014. Transit network design by genetic algorithm with elitism. Transportation Research Part C: Emerging Technologies, 46: 30–45.

      [23] Ngamchai, S. and D.J. Lovell, 2003. Optimal time transfer in bus transit route network design using a genetic algorithm. Journal of Transportation Engineering, 129(5): 510–521.

      [24] Nikolić, M. and D. Teodorović, 2013. Transit network design by bee colony optimization. Expert Systems with Applications, 40(15): 5945–5955.

      [25] Pattnaik, S., S. Mohan, and V. Tom, 1998. Urban bus transit route network design using genetic algorithm. Journal of Transportation Engineering, 124(4): 368–375.

      [26] Storn, R. and K. Price, 1995. Differential Evolution – A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, International Computer Science Institute, Berkeley. Berkeley, CA.

      [27] Zhao, H. and R. Jiang, 2015. The memetic algorithm for the optimization of urban transit network. Expert Systems with Applications, 42(7): 3760–3773.

  • Downloads

  • How to Cite

    Tarajo BUBA, A., & Soon LEE, L. (2018). A Differential Evolution for Optimization of Multiobjective Urban Transit Routing Problem. International Journal of Engineering & Technology, 7(3.20), 140-145. https://doi.org/10.14419/ijet.v7i3.20.18999

    Received date: 2018-09-04

    Accepted date: 2018-09-04

    Published date: 2018-09-01