A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem
| Autor: | Chris N. Potts, Teodor Gabriel Crainic, Tolga Bektaş, Dimitris C. Paraskevopoulos |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Information Systems and Management General Computer Science Iterated local search 0211 other engineering and technologies Evolutionary algorithm Perturbation (astronomy) 02 engineering and technology Management Science and Operations Research Evolutionary algorithms Industrial and Manufacturing Engineering Variable cost Arc (geometry) Scatter search 0502 economics and business QA Fixed cost Mathematics Multi-commodity network design 050210 logistics & transportation 021103 operations research 05 social sciences Ejection chains Network planning and design Fixed charge Modeling and Simulation HD28 |
| Zdroj: | Paraskevopoulos, D C, Bektaş, T, Crainic, T G & Potts, C N 2016, ' A cycle-based evolutionary algorithm for the fixed-charge capacitated multi-commodity network design problem ', European Journal of Operational Research, vol. 253, no. 2, pp. 265-279 . https://doi.org/10.1016/j.ejor.2015.12.051 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2015.12.051 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect