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, we 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 our method, we made experimentations using random generated and real road network instances. We compare our approximate method with two exact algorithms (Dijkstra and integer programming). Results show that our 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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A Hybrid Metaheuristic for Routing in Road Networks


    Contributors:


    Publication date :

    2015-09-01


    Size :

    242153 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English





    Drone Arc Routing Problems and Metaheuristic Solution Approach

    Islam Altin / Aydin Sipahioglu | DOAJ | 2024

    Free access

    A Metaheuristic Approach to Emergency Vehicle Dispatch and Routing

    Giri, Aswin Raj / Chen, Tianjian / Rajendran, Vishnu Priya et al. | IEEE | 2022


    A metaheuristic for the time-dependent pollution-routing problem

    Franceschetti, Anna / Demir, Emrah / Honhon, Dorothée et al. | BASE | 2017

    Free access