Hybrid PACO with enhanced pheromone initialization for solving the vehicle routing problem with time windows

Warning The system is temporarily closed to updates for reporting purpose.

Shi, Wei and Weise, Thomas and Chiong, Raymond and Çatay, Bülent (2015) Hybrid PACO with enhanced pheromone initialization for solving the vehicle routing problem with time windows. In: IEEE Symposium Series on Computational Intelligence (2015), Cape Town, South Africa

This is the latest version of this item.

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

Abstract

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known combinatorial optimization problem found in many practical logistics planning operations. While exact methods designed for solving the VRPTW aim at minimizing the total distance traveled by the vehicles, heuristic methods usually employ a hierarchical objective approach in which the primary objective is to reduce the number of vehicles needed to serve the customers while the secondary objective is to minimize the total distance. In this paper, we apply a holistic approach that optimizes both objectives simultaneously. We consider several state-of-the-art Ant Colony Optimization (ACO) techniques from the literature, including the Min-Max Ant System, Ant Colony System, and Population-based Ant Colony Optimization (PACO). Our experimental investigation shows that PACO outperforms the others. Subsequently, we introduce a new pheromone matrix initialization approach for PACO (PI-PACO) that uses information extracted from the problem instance at hand and enforces pheromone assignments to edges that form feasible building blocks of tours. Our computational tests show that PI-PACO performs better than PACO. To further enhance its performance, we hybridize it with a local search method. The resulting algorithm is efficient in producing high quality solutions and outperforms similar hybrid ACO techniques.
Item Type: Papers in Conference Proceedings
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: 22 Feb 2016 10:23
Last Modified: 26 Apr 2022 09:22
URI: https://research.sabanciuniv.edu/id/eprint/29140

Available Versions of this Item

Actions (login required)

View Item
View Item