期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 253, 期 2, 页码 265-279出版社
ELSEVIER
DOI: 10.1016/j.ejor.2015.12.051
关键词
Multi-commodity network design; Scatter search; Evolutionary algorithms; Ejection chains; Iterated local search
资金
- Engineering and Physical Sciences Research Council (EPSRC)
- Rail Safety and Standards Board (RSSB)
- Department of Transport, UK
- Natural Sciences and Engineering Council of Canada (NSERC)
- Faculty of Business and Law at the University of Southampton
- Fonds de recherche du Quebec, Canada
- Engineering and Physical Sciences Research Council [EP/I010777/1] Funding Source: researchfish
- EPSRC [EP/I010777/1] Funding Source: UKRI
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. (C) 2016 Published by Elsevier B.V.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据