The vehicle routing problem (VRP) involves routing a fleet of vehicles for serving to a number of customers, with the objective of minimizing the total distance traveled by all the vehicles. In this Problem, the vehicles are required to return to the depot after completing service. The open vehicle routing problem (OVRP) is different from most variants of vehicle routing problems from the literature in that the vehicle does not return to the depot after serving the last customer. The constraints considered in this problem are the following: all the vehicles have the same capacity the traveling time of each vehicle should not exceed a given threshold, which is defined by the drivers_ legal traveling time the total demand of all the customers on a route must not exceed the capacity of the vehicle each customer is visited just once by one of the vehicles, and its requirements must be completely fulfilled. The ant colony system (ACS) is one of the most famous metaheuristic algorithms that differs from the other ant colony optimization (ACO) instances due to its transition rule and updating pheromone. Aimed at the disadvantages existed in the current ACS algorithms for solving the OVRP, two effective modificitions including heuristic information and transition rule are proposed in this paper. Furthermore, this algorithm is mixed with lin-kernigan local search for improving solutions of the ants and exploites more strong solutions. Computational results on sixteen standard benchmark problem instances show that the proposed algorithm is comparable in terms of solution quality to the best performing published heuristics.


    Access

    Download


    Export, share and cite



    Title :

    A Hybrid Modified Ant Colony for Solving the Capacitated Open Vehicle Routing Problem


    Contributors:


    Publication date :

    2017




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    Unknown




    Hybrid Heuristic Algorithm for solving Capacitated Vehicle Routing problem

    AbdElAziz, Moh. M. / A. El-Ghareeb, Haitham / Ksasy, M. S. M. | BASE | 2014

    Free access


    Capacitated Vehicle Routing Problem using Ant Colony Optimization and PuLP Library

    Umbrani, Kunal / Choreria, Pratham / Kulkarni, Pradnya V. et al. | IEEE | 2025


    Optimasi Capacitated Vehicle Routing Problem with Time Windows dengan Menggunakan Ant Colony Optimization

    Soenandi, Iwan Aang / Joice, Joice / Marpaung, Budi | BASE | 2019

    Free access

    An efficient meta-heuristic algorithm for solving capacitated vehicle routing problem

    Faiz, Alfian / Subiyanto, Subiyanto / Arief, Ulfah Mediaty | BASE | 2018

    Free access