Abstract
Some optimization problems need to finding a permutation of a given set of items that minimizes a certain cost function. This paper introduces an effective memetic algorithm for the linear ordering problem with cumulative costs (LOPCC). The proposed algorithm combines an order-based recombination operator with an improved forward-backward local search procedure and employs a quality based replacement criterion for pool updating. Extensive experiments on 118 benchmark instances from the literature show that the proposed algorithm achieves competitive results by identifying 46 new upper bounds. Furthermore, some critical ingredients of our algorithm are analyzed to understand the source of its performance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bertacco, L., Brunetta, L., Fischetti, M.: The linear ordering problem with cumulative costs. Eur. J. Oper. Res. 189(3), 1345–1357 (2008)
Benvenuto, N., Carnevale, G., Tomasin, S.: Optimum power control and ordering in SIC receivers for uplink CDMA systems. IEEE Int. Conf. Commun. 4, 2333–2337 (2005)
Righini, G.: A branch-and-bound algorithm for the linear ordering problem with cumulative costs. Eur. J. Oper. Res. 186(3), 965–971 (2008)
Villanueva, D.T., Huacuja, H.J.F., Duarte, A., Pazos R., R., Valadez, J.M.C., Puga Soberanes, H.J.: Improving iterated local search solution for the Linear Ordering Problem with Cumulative Costs (LOPCC). In: Setchi, R., Jordanov, I., Howlett, R.J., Jain, L.C. (eds.) KES 2010. LNCS (LNAI), vol. 6277, pp. 183–192. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15390-7_19
Duarte, A., Laguna, M., Martí, R.: Tabu search for the linear ordering problem with cumulative costs. Comput. Optim. Appl. 48(3), 697–715 (2011)
Duarte, A., Martí, R., Álvarez, A., Ángel-Bello, F.: Metaheuristics for the linear ordering problem with cumulative costs. Eur. J. Oper. Res. 216(2), 270–277 (2012)
Campos, V., Glover, F., Laguna, M., Martí, R.: An experimental evaluation of a scatter search for the linear ordering problem. J. Glob. Optim. 21(4), 397–414 (2001)
Schiavinotto, T., Stützle, T.: The linear ordering problem: instances, search space analysis and algorithms. J. Math. Model. Algorithm 3(4), 367–402 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Zhou, T., Lü, Z., Ye, T., Zhou, K. (2017). A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs. In: Gao, X., Du, H., Han, M. (eds) Combinatorial Optimization and Applications. COCOA 2017. Lecture Notes in Computer Science(), vol 10628. Springer, Cham. https://doi.org/10.1007/978-3-319-71147-8_39
Download citation
DOI: https://doi.org/10.1007/978-3-319-71147-8_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71146-1
Online ISBN: 978-3-319-71147-8
eBook Packages: Computer ScienceComputer Science (R0)