A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem

Hightlights•New and enhanced cycle-based neighborhood operators.•An innovative perturbation strategy based on ejection chains, namely the Ejection Cycles.•An efficient scatter search that considers the search history and “solvency-based” measures to produce offspring.•Competitive results produced fo...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2016-09, Vol.253 (2), p.265-279
Main Authors: Paraskevopoulos, Dimitris C., Bektaş, Tolga, Crainic, Teodor Gabriel, Potts, Chris N.
Format: Article
Language:English
Subjects:
Algorithms
Benchmarks
Commodities
Costs
Design engineering
Ejection
Ejection chains
Evolutionary algorithms
Genetic algorithms
Iterated local search
Mathematical models
Mathematical problems
Multi-commodity network design
Networks
Scatter search
Searching
Studies
Variable costs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Hightlights•New and enhanced cycle-based neighborhood operators.•An innovative perturbation strategy based on ejection chains, namely the Ejection Cycles.•An efficient scatter search that considers the search history and “solvency-based” measures to produce offspring.•Competitive results produced for well known benchmarks of literature. This paper presents an evolutionary algorithm for the fixed-charge multicommodity network design problem (MCNDP), which concerns routing multiple commodities from origins to destinations by designing a network through selecting arcs, with an objective of minimizing the fixed costs of the selected arcs plus the variable costs of the flows on each arc. The proposed algorithm evolves a pool of solutions using principles of scatter search, interlinked with an iterated local search as an improvement method. New cycle-based neighborhood operators are presented which enable complete or partial re-routing of multiple commodities. An efficient perturbation strategy, inspired by ejection chains, is introduced to perform local compound cycle-based moves to explore different parts of the solution space. The algorithm also allows infeasible solutions violating arc capacities while performing the “ejection cycles”, and subsequently restores feasibility by systematically applying correction moves. Computational experiments on benchmark MCNDP instances show that the proposed solution method consistently produces high-quality solutions in reasonable computational times.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2015.12.051