abstract

A new hybrid evolutionary algorithm for dial-a-ride problems

Authors:

Sonia Nasri,

Hend Bouziri,

Wassila Aggoune-MtalaaAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 57 - 58

https://doi.org/10.1145/3449726.3462733

Published: 08 July 2021 Publication History

Get Access

Abstract

This work aims at planning the vehicle routes and schedules within Dial and Ride Problems. Therefore, we propose a new hybrid evolutionary algorithm that combines the evolutionary schema with a Tabu Search method. New controlled mutation operators and an original crossover for minimizing the redundancy of solutions are investigated. A comparison between different hybridized methods is operated on benchmark instances from the literature. Computational experiments show the effectiveness of our method in comparison with the current techniques from the state-of-the-art.

References

[1]

Amroun, K., Habbas, Z., and Aggoune-Mtalaa, W. A compressed generalized hypertree decomposition-based solving technique for non-binary constraint satisfaction problems. AI Communications 29, 2 (2016), 371--392.

Digital Library

Google Scholar

[2]

Bennekrouf, M., Aggoune-Mtalaa, W., and Sari, Z. A generic model for network design including remanufacturing activities. Supply Chain Forum 14, 2 (2013), 4--17.

Google Scholar

[3]

Braekers, K., Caris, A., and Janssens, G. K. Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Research Part B: Methodological 67 (2014), 166--186.

Crossref

Google Scholar

[4]

Chassaing, M., Duhamel, C., and Lacomme, P. An els-based approach with dynamic probabilities management in local search for the dial-a-ride problem. Engineering Applications of Artificial Intelligence 48 (2016), 119--133.

Digital Library

Google Scholar

[5]

Cordeau. instances of Cordeau. http://neumann.hec.ca/chairedistributique/data/darp/, 2003. [Online; accessed 19-April-2020].

Google Scholar

[6]

Cordeau, J.-F., and Laporte, G. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological 37, 6 (2003), 579--594.

Crossref

Google Scholar

[7]

Masmoudi, M. A., Braekers, K., Masmoudi, M., and Dammak, A. A hybrid genetic algorithm for the heterogeneous dial-a-ride problem. Computers & operations research 81 (2017), 1--13.

Google Scholar

[8]

Nasri, S., and Bouziri, H. Improving total transit time in dial-a-ride problem with customers-dependent criteria. In 2017 IEEE/ACS 14th International Conference on Computer Systems and Applications (AICCSA) (2017), pp. 1141--1148.

Crossref

Google Scholar

[9]

Parragh, S. N., and Schmid, V. Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers & Operations Research 40, 1 (2013), 490--497.

Digital Library

Google Scholar

A new hybrid evolutionary algorithm for dial-a-ride problems
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

A tabu search based hybrid evolutionary algorithm for the max-cut problem

Graphical abstractDisplay Omitted HighlightsWe design a hybrid evolutionary algorithm (TSHEA) for the max-cut problem.Results disclose TSHEA discovers new best solutions for 15 out of 91 instances.Analysis indicates the effectiveness of the designed key ...
A new hybrid island model genetic algorithm for job shop scheduling problem

A new algorithm combining island model genetic algorithm (IMGA) and tabu search (TS) is proposed.It utilizes a new self-adaptation phase strategy: best individuals do a local search, and worst ones do a global search.It was tested on 76 benchmark ...
A hybrid self-adaptive evolutionary algorithm for the minimum weight dominating set problem

Given an undirected graph with weights associated with its vertices, the minimum weight dominating set problem MWDSP is to determinate a subset of vertices with minimum sum of weights such that each vertex of the graph either belongs to the subset or is ...

Comments

Information & Contributors

Information

Published In

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2021

2047 pages

ISBN:9781450383516

DOI:10.1145/3449726

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2021

Check for updates

Author Tags

Qualifiers

Abstract

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
58
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Sep 2024

Other Metrics

View Author Metrics

Citations

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Recommendations

A tabu search based hybrid evolutionary algorithm for the max-cut problem

A new hybrid island model genetic algorithm for job shop scheduling problem

A hybrid self-adaptive evolutionary algorithm for the minimum weight dominating set problem