An ant colony-based matheuristic approach for solving a class of vehicle routing problems

Yıldırım, Mahir Umman and Çatay, Bülent (2015) An ant colony-based matheuristic approach for solving a class of vehicle routing problems. In: 6th International Conference on Computational Logistics (ICCL 2015), Delft, The Netherlands

Full text not available from this repository. (Request a copy)

Abstract

We propose a matheuristic approach to solve several types of vehicle routing problems (VRP). In the VRP, a fleet of capacitated vehicles visits a set of customers exactly once to satisfy their demands while obeying problem specific characteristics and constraints such as homogeneous or heterogeneous fleet, customer service time windows, single or multiple depots. The proposed matheuristic is based on an ant colony optimization (ACO) algorithm which constructs good feasible solutions. The routes obtained in the ACO procedure are accumulated in a pool as columns which are then fed to an integer programming (IP) optimizer that solves the set-partitioning (-covering) formulation of the particular VRP. The (near-)optimal solution found by the solver is used to reinforce the pheromone trails in ACO. This feedback mechanism between the ACO and IP procedures helps the matheuristic better converge to high quality solutions. We test the performance of the proposed matheuristic on different VRP variants using the well-known benchmark instances from the literature. Our computational experiments reveal competitive results: we report 6 new best solutions and meet the best-known solution in 120 instances out of 193.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Vehicle routing problem ; Matheuristic ; Ant colony optimization
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Bülent Çatay
Date Deposited: 18 Nov 2015 15:00
Last Modified: 26 Apr 2022 09:19
URI: https://research.sabanciuniv.edu/id/eprint/27248

Actions (login required)

View Item
View Item