An Investigation into Many-objective Optimization Problems: A Case Study of the Dial-a-Ride Problem

Authors

  • Renan José dos Santos Viana Programa de Pós-Graduação em Modelagem Matemática Computacional do Centro Federal de Educação Tecnológica de Minas Gerais https://orcid.org/0000-0003-1441-1858
  • Flávio Vinícius Cruzeiro Martins Departamento de Computação do Centro Federal de Educação Tecnológica de Minas Gerais https://orcid.org/0000-0002-6666-653X
  • Elizabeth Fialho Wanner Departamento de Computação do Centro Federal de Educação Tecnológica de Minas Gerais https://orcid.org/0000-0001-6450-3043

Keywords:

Many-objective optimization, dial-a-ride problem, multi-objective evolutionary algorithms, combinatorial optimization

Abstract

Multi-objective optimization problems with more than three objectives are commonly referred to as many-objective optimization problems. Usually, this class of problem brings new and complex challenges to the current optimization methods, mainly maintaining the right balance between convergence and diversity. During the last years, various approaches have been proposed to solve many-objective problems. However, most existing experimental comparative studies are restricted to continuous problems. Few studies have encompassed the most recently proposed state-of-the-art approaches and made an experimental comparison applied to combinatorial optimization problems. Aiming to fill this gap, this paper presents a comparative analysis with eight algorithms covering various categories to solve a many-objective Dial-a-Ride problem. The results show that different observations can be made about the algorithms' behavior when using different test sets. Also, algorithms originally proposed to deal with problems with up to three objectives have overcome recently proposed ones.

Downloads

Download data is not yet available.

Author Biographies

Renan José dos Santos Viana, Programa de Pós-Graduação em Modelagem Matemática Computacional do Centro Federal de Educação Tecnológica de Minas Gerais

Possui graduação em Sistemas de Informação pela Universidade Federal de Ouro Preto (2013), mestrado em Ciência da Computação pela Universidade Federal de Viçosa (2016). É doutorando no Programa de Pós-Graduação em Modelagem Matemática Computacional do Centro Federal de Educação Tecnológica de Minas Gerais. Tem interesse na área de otimização, nos seguintes temas: algoritmos evolutivos, otimização multiobjetivo e otimização combinatória.

Flávio Vinícius Cruzeiro Martins, Departamento de Computação do Centro Federal de Educação Tecnológica de Minas Gerais

Possui graduação em Ciência da Computação (2007), mestrado (2009) e doutorado (2012) em Engenharia Elétrica ambos pela Universidade Federal de Minas Gerais. É professor no Centro Federal de Educação Tecnológica de Minas Gerais e Bolsista de Produtividade Desenvolvimento Tecnológico e Extensão Inovadora do CNPq, Nível 2. Tem experiência na área de otimização, atuando principalmente nos seguintes temas: algoritmos evolutivos, otimização mono e multiobjetivo e otimização combinatória.

Elizabeth Fialho Wanner, Departamento de Computação do Centro Federal de Educação Tecnológica de Minas Gerais

Possui mestrado em Matemática (2002), doutorado em Engenharia Elétrica (2006) ambos pela Universidade Federal de Minas Gerais e pós-doutorado em Ciência da Computação pela Universidade do Algarve, Portugal (2009). É professor do Departamento de Computação do Centro Federal de Educação Tecnológica de Minas Gerais. Tem experiência na área de Matemática Aplicada, atuando principalmente nos seguintes temas: algoritmos populacionais, aproximações quadráticas, restrições de igualdade, medidas de desempenho e otimização mono e multiobjetivo.

References

J. Mageean and J. D. Nelson, “The evaluation of demand responsive

transport services in europe,” Journal of Transport Geography, vol. 11,

no. 4, pp. 255–270, 2003.

G. Ambrosino, J. Nelson, and M. Romanazzo, Demand responsive

transport services: Towards the flexible mobility agency. ENEA, Italian

National Agency for New Technologies, Energy and the Environment,

J.-F. Cordeau and G. Laporte, “The dial-a-ride problem: models and

algorithms,” Annals of Operations Research, vol. 153, no. 1, pp. 29–46,

——, “A tabu search heuristic for the static multi-vehicle dial-a-ride

problem,” Transportation Research Part B: Methodological, vol. 37,

no. 6, pp. 579–594, 2003.

J.-F. Cordeau, “A branch-and-cut algorithm for the dial-a-ride problem,”

Operations Research, vol. 54, no. 3, pp. 573–586, 2006.

Y. Molenbruch, K. Braekers, and A. Caris, “Typology and literature

review for dial-a-ride problems,” Annals of Operations Research, vol.

, no. 1-2, pp. 295–325, 2017.

S. C. Ho, W. Szeto, Y.-H. Kuo, J. M. Leung, M. Petering, and T. W.

Tou, “A survey of dial-a-ride problems: Literature review and recent

developments,” Transportation Research Part B: Methodological, 2018.

U. Ritzinger, J. Puchinger, and R. F. Hartl, “Dynamic programming

based metaheuristics for the dial-a-ride problem,” Annals of Operations

Research, vol. 236, no. 2, pp. 341–358, 2016.

R. Chevrier, A. Liefooghe, L. Jourdan, and C. Dhaenens, “Solving a

dial-a-ride problem with a hybrid evolutionary multi-objective approach:

Application to demand responsive transport,” Applied Soft Computing,

vol. 12, no. 4, pp. 1247–1258, 2012.

B. Rekiek, A. Delchambre, and H. A. Saleh, “Handicapped person

transportation: An application of the grouping genetic algorithm,” Engineering

Applications of Artificial Intelligence, vol. 19, no. 5, pp. 511–

, 2006.

T. Garaix, C. Artigues, D. Feillet, and D. Josselin, “Optimization of

occupancy rate in dial-a-ride problems via linear fractional column

generation,” Computers & Operations Research, vol. 38, no. 10, pp.

–1442, 2011.

S. N. Parragh, J. Pinho de Sousa, and B. Almada-Lobo, “The dial-a-ride

problem with split requests and profits,” Transportation Science, vol. 49,

no. 2, pp. 311–334, 2014.

A. Lim, Z. Zhang, and H. Qin, “Pickup and delivery service with

manpower planning in hong kong public hospitals,” Transportation Science, vol. 51, no. 2, pp. 688–705, 2016.

R. M. Jorgensen, J. Larsen, and K. B. Bergvinsdottir, “Solving the diala-

ride problem using genetic algorithms,” Journal of the operational

research society, vol. 58, no. 10, pp. 1321–1331, 2007.

D. Kirchler and R. W. Calvo, “A granular tabu search algorithm for the

dial-a-ride problem,” Transportation Research Part B: Methodological,

vol. 56, pp. 120–135, 2013.

M. Schilde, K. F. Doerner, and R. F. Hartl, “Integrating stochastic timedependent

travel speed in solution methods for the dynamic dial-a-ride

problem,” European journal of operational research, vol. 238, no. 1, pp.

–30, 2014.

R. Chevrier, A. Liefooghe, L. Jourdan, and C. Dhaenens, “On optimizing

a demand responsive transport with an evolutionary multi-objective

approach,” in Intelligent Transportation Systems (ITSC), 2010 13th

International IEEE Conference on. IEEE, 2010, pp. 575–580.

J. Paquette, J.-F. Cordeau, G. Laporte, and M. M. Pascoal, “Combining

multicriteria analysis and tabu search for dial-a-ride problems,” Transportation Research Part B: Methodological, vol. 52, pp. 1–16, 2013.

Y. Molenbruch, K. Braekers, A. Caris, and G. V. Berghe, “Multidirectional

local search for a bi-objective dial-a-ride problem in patient

transportation,” Computers & Operations Research, vol. 77, pp. 58–71,

R. J. S. Viana, A. G. Santos, F. V. C. Martins, and E. F.

Wanner, “Optimization of a demand responsive transport service

using multi-objective evolutionary algorithms,” in Proceedings of the

Genetic and Evolutionary Computation Conference Companion,

ser. GECCO ’19. New York, NY, USA: Association for

Computing Machinery, 2019, p. 2064–2067. [Online]. Available:

https://doi.org/10.1145/3319619.3328528

R. S. Mendes, D. S. Miranda, E. F. Wanner, J. F. M. Sarubbi, and F. V. C.

Martins, “Multiobjective approach to the vehicle routing problem with

demand responsive transport,” in 2016 IEEE Congress on Evolutionary

Computation (CEC), 2016, pp. 3761–3768.

R. Mendes, E. Wanner, F. Martins, and J. Sarubbi, “Dimensionality

reduction approach for many-objective vehicle routing problem with demand

responsive transport,” in International Conference on Evolutionary

Multi-Criterion Optimization. Springer, 2017, pp. 438–452.

R. S. Mendes, V. Lush, E. F. Wanner, F. V. Martins, J. F.

Sarubbi, and K. Deb, “Online clustering reduction based on

parametric and non-parametric correlation for a many-objective vehicle

routing problem with demand responsive transport,” Expert Systems

with Applications, vol. 170, p. 114467, 2021. [Online]. Available:

http://www.sciencedirect.com/science/article/pii/S0957417420311180

A. A. Anwar and I. Younas, “Optimization of many objective pickup and

delivery problem with delay time of vehicle using memetic decomposition

based evolutionary algorithm,” International Journal on Artificial

Intelligence Tools, vol. 29, no. 01, 2020.

H. Zhao, C. Zhang, J. Ning, B. Zhang, P. Sun, and Y. Feng, “A comparative

study of the evolutionary many-objective algorithms,” Progress

in Artificial Intelligence, vol. 8, no. 1, pp. 15–43, 2019.

B. Li, J. Li, K. Tang, and X. Yao, “Many-objective evolutionary

algorithms: A survey,” ACM Comput. Surv., vol. 48, no. 1, Sep. 2015.

[Online]. Available: https://doi.org/10.1145/2792984

R. J. D. S. VIANA, “Abordagens heur´ısticas para otimizac¸ ˜ao de um

servic¸o de transporte reativo a demanda,” Master’s thesis, Programa de

P´os-Graduac¸ ˜ao em Ciˆencia da Computac¸ ˜ao, Universidade Federal de

Vic¸osa, 2016.

C. C. Coello, G. B. Lamont, and D. A. Van Veldhuizen, Evolutionary

algorithms for solving multi-objective problems. Springer, 2007.

V. Pareto, “Cours deconomie, vol. I and II, f,” Rouge, Lausanne, 1896.

K. Deb, Multi-objective optimization using evolutionary algorithms.

John Wiley & Sons, 2001, vol. 16.

A. Abraham and L. Jain, Evolutionary multiobjective optimization.

Springer, 2005.

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist

multiobjective genetic algorithm: Nsga-ii,” Evolutionary Computation,

IEEE Transactions on, vol. 6, no. 2, pp. 182–197, 2002.

E. Zitzler, M. Laumanns, L. Thiele, E. Zitzler, E. Zitzler, L. Thiele,

and L. Thiele, “SPEA2: Improving the strength pareto evolutionary algorithm,”

Eidgen¨ossische Technische Hochschule Z¨urich (ETH), Institut

f¨ur Technische Informatik und Kommunikationsnetze (TIK), Tech. Rep.,

Q. Zhang and H. Li, “Moea/d: A multiobjective evolutionary algorithm

based on decomposition,” IEEE Transactions on evolutionary computation,

vol. 11, no. 6, pp. 712–731, 2007.

Z. Wang, Q. Zhang, M. Gong, and A. Zhou, “A replacement strategy for

balancing convergence and diversity in moea/d,” in 2014 IEEE Congress

on Evolutionary Computation (CEC). IEEE, 2014, pp. 2132–2139.

E. Zitzler and S. K¨unzli, “Indicator-based selection in multiobjective

search,” in Parallel Problem Solving from Nature-PPSN VIII. Springer,

, pp. 832–842.

K. DEB and H. JAIN, “An evolutionary many-objective optimization

algorithm using reference-point-based nondominated sorting approach,

part i: Solving problems with box constraints,” IEEE transactions on

evolutionary computation, vol. 18, no. 4, pp. 577–601, 2014.

S. Jiang and S. Yang, “A strength pareto evolutionary algorithm based on

reference direction for multiobjective and many-objective optimization,”

IEEE Transactions on Evolutionary Computation, vol. 21, no. 3, pp.

–346, 2017.

H. Wang, L. Jiao, and X. Yao, “Two arch2: An improved two-archive

algorithm for many-objective optimization,” IEEE Transactions on Evolutionary

Computation, vol. 19, no. 4, pp. 524–541, 2015.

J. D. Knowles, L. Thiele, and E. Zitzler, “A tutorial on the performance

assessment of stochastic multiobjective optimizers,” TIK-Report, vol.

, 2006.

E. Zitzler and L. Thiele, “Multiobjective optimization using evolutionary

algorithms - a comparative case study,” in Parallel problem solving from

nature - PPSN V. Springer, 1998, pp. 292–301.

E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca,

“Performance assessment of multiobjective optimizers: An analysis

and review,” Evolutionary Computation, IEEE Transactions on, vol. 7,

no. 2, pp. 117–132, 2003.

C. M. Fonseca, J. D. Knowles, L. Thiele, and E. Zitzler, “A tutorial on

the performance assessment of stochastic multiobjective optimizers,” in

Third International Conference on Evolutionary Multi-Criterion Optimization

(EMO 2005), vol. 216, 2005, p. 240.

J. Bader and E. Zitzler, “Hype: An algorithm for fast hypervolume-based

many-objective optimization,” Evolutionary computation, vol. 19, no. 1,

pp. 45–76, 2011.

I. Das and J. E. Dennis, “Normal-boundary intersection: A new method

for generating the pareto surface in nonlinear multicriteria optimization

problems,” SIAM journal on optimization, vol. 8, no. 3, pp. 631–657,

R. Tanabe, H. Ishibuchi, and A. Oyama, “Benchmarking multi- and

many-objective evolutionary algorithms under two optimization scenarios,”

IEEE Access, vol. 5, pp. 19 597–19 619, 2017.

L. C. Bezerra, M. L´opez-Ib´a˜nez, and T. St¨utzle, “A large-scale experimental

evaluation of high-performing multi-and many-objective evolutionary

algorithms,” Evolutionary computation, vol. 26, no. 4, pp. 621–

, 2018.

Published

2021-08-12

How to Cite

dos Santos Viana, R. J., Cruzeiro Martins, F. V. ., & Fialho Wanner, E. (2021). An Investigation into Many-objective Optimization Problems: A Case Study of the Dial-a-Ride Problem. IEEE Latin America Transactions, 100(XXX). Retrieved from https://latamt.ieeer9.org/index.php/transactions/article/view/5064