A Hybrid Metaheuristic for Routing in Road Networks

Computing the optimal route to go from one place to another is a highly important issue in road networks. The problem consists of finding the path that minimizes a metric such as distance, time, cost etc. to go from one node to another in a directed or undirected graph. Although standard algorithms and techniques such as Dijkstra and integer programming are capable of computing shortest paths in polynomial times, they become very slow when the network becomes very large. Furthermore, traditional methods are incapable of meeting additional constraints that may arise during routing in transportation systems such as computing multi-objective routes, routing in stochastic networks. Therefore, the authors have thought about using meta-heuristics to solve the routing issue in road networks. Meta-heuristics are capable of copying with additional constraints and providing optimal or near optimal routes within reasonable computational times in large-scale road networks. The proposed approach is a combination between genetic algorithm (GA) and variable neighborhood search (VNS). To evaluate this method, the authors made experimentations using random generated and real road network instances. The authors compare their approximate method with two exact algorithms (Dijkstra and integer programming). Results show that the authors' approach is able to give high quality solutions within milliseconds even in large-scale networks. Moreover, the selected meta-heuristics show high flexibility rate in terms of meeting other problem requirements.

Language

  • English

Media Info

  • Media Type: Web
  • Features: References;
  • Pagination: pp 765-770
  • Monograph Title: 18th International IEEE Conference on Intelligent Transportation Systems (ITSC 2015)

Subject/Index Terms

Filing Info

  • Accession Number: 01602981
  • Record Type: Publication
  • ISBN: 9781467365956
  • Files: TRIS
  • Created Date: May 2 2016 3:18PM