Multi-directional local search. (English) Zbl 1349.90751

Summary: This paper introduces multi-directional local search, a metaheuristic for multi-objective optimization. We first motivate the method and present an algorithmic framework for it. We then apply it to several known multi-objective problems such as the multi-objective multi-dimensional knapsack problem, the bi-objective set packing problem and the bi-objective orienteering problem. Experimental results show that our method systematically provides solution sets of comparable quality with state-of-the-art methods applied to benchmark instances of these problems, within reasonable CPU effort. We conclude that the proposed algorithmic framework is a viable option when solving multi-objective optimization problems.


90C29 Multi-objective and goal programming
90C27 Combinatorial optimization
Full Text: DOI


[1] João Alves, M.; Almeida, M., MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem, Computers & operations research, 34, 3458-3470, (2007) · Zbl 1127.90059
[2] Alves, M.J.; Climaco, J., An interactive method for 0-1 multiobjective problems using simulated annealing and tabu search, Journal of heuristics, 6, 385-403, (2000) · Zbl 1071.90561
[3] Bazgan, C.; Hugot, H.; Vanderpooten, D., Solving efficiently the 0-1 multi-objective knapsack problem, Computers & operations research, 36, 260-279, (2009) · Zbl 1175.90323
[4] Bérubé, J.F.; Gendreau, M.; Potvin, J.Y., An exact epsilon-constraint method for bi-objective combinatorial optimization problems: application to the traveling salesman problem with profits, European journal of operational research, 194, 39-50, (2009) · Zbl 1179.90274
[5] Branke, J.; Greco, S.; Slowínski, R.; Zielniewicz, P., Interactive evolutionary multiobjective optimization using robust ordinal regression, (), 554-568 · Zbl 1428.90148
[6] Chao IM. Algorithms and solutions to multi-level vehicle routing problems. PhD thesis. College Park, MD, USA. Chairman-Bruce L. Golden; 1993.
[7] Chao, I.M.; Golden, B.L.; Wasil, E.A., A fast and effective heuristic for the orienteering problem, European journal of operational research, 88, 475-489, (1996) · Zbl 0911.90146
[8] Coello, C.A.C.; Christiansen, A.D., Two new GA-based methods for multiobjective optimization, Civil engineering and environmental systems, 15, 207-243, (1998)
[9] Coello Coello, A.; Van Veldhuizen, D.; Lamont, G., Evolutionary algorithms for solving multi-objective problems, (2002), Kluwer Academic Publishers · Zbl 1130.90002
[10] Czyzak, P.; Jaszkiewicz, A., Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization, Journal of multi-criteria decision analysis, 7, 34-47, (1998) · Zbl 0904.90146
[11] Da Fonseca VG, Fonseca CM, Hall AO. Inferential performance assessment of stochastic optimisers and the attainment function. In: First international conference on evolutionary multi-criterion optimization. Springer-Verlag; 2001. p. 213-25.
[12] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multi-objective genetic algorithm: NSGA II, IEEE transactions on evolutionary computation, 6, 182-197, (2002)
[13] Delorme X. Modélisation et résolution de problèmes liés à l’exploitation d’infrastructures ferroviaires. PhD thesis. Université de Valenciennes et du Hainaut Cambrésis [in French]; 2003.
[14] Delorme, X.; Gandibleux, X.; Degoutin, F., Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem, European journal of operational research, 204, 206-217, (2010) · Zbl 1178.90303
[15] Doerner, K.F.; Gutjahr, W.J.; Hartl, R.F.; Strauss, C.; Stummer, C., Pareto ant colony optimization: a metaheuristic approach to multiobjective portfolio selection, Annals of operations research, 131, 79-99, (2004) · Zbl 1067.91028
[16] Escudero, L.; Landete, M.; Marín, A., A branch-and-cut algorithm for the winner determination problem, Decision support systems, 46, 649-659, (2009)
[17] Festa, P.; Resende, M., GRASP: an annotated bibliography, (), 325-367 · Zbl 1017.90001
[18] Figueira, J.R.; Greco, S.; Slowínski, R., Building a set of additive value functions representing a reference preorder and intensities of preference: GRIP method, European journal of operational research, 195, 460-486, (2009) · Zbl 1159.91341
[19] Florios, K.; Mavrotas, G.; Diakoulaki, D., Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms, European journal of operational research, 203, 14-21, (2010) · Zbl 1177.90341
[20] Fonseca C, Paquete L, López-Ibáñez M. An improved dimension-sweep algorithm for the hypervolume indicator. In: IEEE congress on evolutionary computation; 2006. p. 1157-63.
[21] Fonseca CM, Fleming PJ. Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. In: Genetic algorithms: proceedings of the fifth international conference; 1993. p. 416-23.
[22] Framinan, J.; Leisten, R., A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria, OR spectrum, 30, 787-804, (2008) · Zbl 1193.90099
[23] Gandibleux, X.; Fréville, A., Tabu search based procedure for solving the 0-1 multiobjective knapsack problem: the two objectives case, Journal of heuristics, 6, 361-383, (2000) · Zbl 0969.90079
[24] Gandibleux, X.; Mezdaoui, N.; Fréville, A., A tabu search procedure to solve multiobjective combinatorial optimization problems, (), 103-108
[25] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Norwell · Zbl 0930.90083
[26] Hapke, M.; Jaszkiewicz, A.; Slowinski, R., Pareto simulated annealing for fuzzy multi-objective combinatorial optimization, Journal of heuristics, 6, 329-345, (2000) · Zbl 1071.90588
[27] Hoos, H.; Stützle, T., Stochastic local search: foundations & applications, (2004), Elsevier/Morgan Kaufmann San Francisco, CA, USA · Zbl 1126.68032
[28] Jaszkiewicz, A., On the performance of multiple-objective genetic local search on the 0/1 knapsack problem—a comparative experiment, IEEE transactions on evolutionary computation, 6, 402-412, (2002)
[29] Jaszkiewicz, A.; Branke, J., Interactive multiobjective evolutionary algorithms, (), 179-193
[30] Jaszkiewicz, A.; Ferhat, A.B., Solving multiple criteria problems by interactive trichotomy segmentation, European journal of operational research, 113, 271-280, (1999) · Zbl 0938.90037
[31] Khare, V.; Yao, X.; Deb, K., Performance scaling of multi-objective evolutionary algorithms, (), 376-390 · Zbl 1036.90541
[32] Knowles, J.; Corne, D., Approximating the nondominated front using the Pareto archived evolution strategy, Evolutionary computation, 8, 149-172, (2000)
[33] Knowles J, Thiele L, Zitzler E. A tutorial on the performance assessment of stochastic multiobjective optimizers. Technical report TIK-report no. 214. Computer engineering and Networks Laboratory, ETH Zurich; 2006.
[34] Laumanns, M.; Thiele, L.; Zitzler, E., An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European journal of operational research, 169, 932-942, (2006) · Zbl 1079.90122
[35] Lusby R, Larsen J, Ryan D, Ehrgott M. Routing trains through railway junctions: a new set packing approach. Technical report. Informatics and Mathematical Modelling, Technical University of Denmark, DTU; 2006.
[36] Mavrotas, G.; Diakoulaki, D., A branch and bound algorithm for mixed zero-one multiple objective linear programming, European journal of operational research, 107, 530-541, (1998) · Zbl 0943.90063
[37] Minella, G.; Ruiz, R.; Ciavotta, M., Restarted iterated Pareto greedy algorithm for multi-objective flowshop scheduling problems, Computers & operations research, 38, 1521-1533, (2011)
[38] Mostaghim, S.; Teich, J., Quad-trees: a data structure for storing Pareto sets in multiobjective evolutionary algorithms with elitism, (), 81-104, [Advanced information and knowledge processing] · Zbl 1079.90124
[39] Paquete, L.; Chiarandini, M.; Stützle, T., Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study, Lecture notes in economics and mathematical systems: metaheuristics for multiobjective optimization, vol. 535, 177-200, (2004) · Zbl 1070.90102
[40] Paquete, L.; Schiavinotto, T.; Stützle, T., On local optima in multiobjective combinatorial optimization problems, Annals of operations research, 156, 83-97, (2007) · Zbl 1145.90067
[41] Parragh, S.N.; Doerner, K.F.; Gandibleux, X.; Hartl, R.F., A heuristic two-phase solution method for the multi-objective dial-a-ride problem, Networks, 54, 227-242, (2009) · Zbl 1204.90096
[42] Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Computers & operations research, 34, 2403-2435, (2007) · Zbl 1144.90318
[43] Pisinger, D.; Ropke, S., Large neighborhood search, (), 399-419
[44] Ropke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation science, 40, 455-472, (2006)
[45] Schaffer, J., Multiple objective optimization with vector evaluated genetic algorithms, (), 93-100 · Zbl 0676.68047
[46] Schilde, M.; Doerner, K.F.; Hartl, R.F.; Kiechle, G., Metaheuristics for the bi-objective orienteering problem, Swarm intelligence, 3, 179-201, (2009)
[47] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G., Record breaking optimization results using the ruin and recreate principle, Journal of computational physics, 159, 139-171, (2000) · Zbl 0997.90105
[48] Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In: Principles and practice of constraint programming CP98. Springer-Verlag; 1998. p. 417-31.
[49] Srinivas, K., Multiobjective optimization using non-dominated sorting in genetic algorithms, Evolutionary computation, 2, 221-248, (1994)
[50] Tricoire, F.; Romauch, M.; Doerner, K.F.; Hartl, R.F., Heuristics for the multi-period orienteering problem with multiple time windows, Computers & operations research, 37, 351-367, (2010) · Zbl 1175.90212
[51] Tsiligirides, T., Heuristic methods applied to orienteering, The journal of the operational research society, 35, 797-809, (1984)
[52] Ulungu, E.; Teghem, J.; Fortemps, P.; Tuyttens, D., MOSA method: a tool for solving multiobjective combinatorial optimization problems, Journal of multi-criteria decision analysis, 8, 221-236, (1999) · Zbl 0935.90034
[53] Ulungu, E.L.; Teghem, J.; Fortemps, P., Heuristics for multiobjective combinatorial optimization by simulated annealing, (), 228-238
[54] Van Veldhuizen, D.; Lamont, G., Multiobjective evolutionary algorithms: analyzing the state-of-the-art, Evolutionary computation, 8, 125-147, (2000)
[55] Varadharajan, T.; Rajendran, C., A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs, European journal of operational research, 167, 772-795, (2005) · Zbl 1154.90499
[56] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE transactions on evolutionary computation, 11, 712-731, (2007)
[57] Zitzler E, Laumanns M, Thiele L. Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Evolutionary methods for design, optimisation, and control, CIMNE, Barcelona, Spain; 2002. p. 95-100.
[58] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE transactions on evolutionary computation, 3, 257-271, (1999)
[59] Zitzler, E.; Thiele, L.; Laumanns, M., Performance assessment of multiobjective optimizers: an analysis and review, IEEE transactions on evolutionary computation, 7, 117-132, (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.