Solving dial-a-ride problems with a low-level hybridization of ants and constraint programming

BRODERICK CRAWFORD LABRIN, Carlos Castro, Eric Monfroy

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

This paper is about Set Partitioning formulation and resolution for a particular case of VRP, the Dial-a-ride Problem. Set Partitioning has demonstrated to be useful modeling this problem and others very visible and economically significant problems. But the main disadvantage of this model is the need to explicitly generate a large set of possibilities to obtain good solutions. Additionally, in many cases a prohibitive time is needed to find the exact solution. Nowadays, many efficient metaheuristic methods have been developed to make possible a good solution in a reasonable amount of time. In this work we try to solve it with Low-level Hybridizations of Ant Colony Optimization and Constraint Programming techniques helping the construction phase of the ants. Computational results solving some benchmark instances are presented showing the advantages of using this kind of hybridization.

Original languageEnglish
Title of host publicationNature Inspired Problem-Solving Methods in Knowledge Engineering - Second International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2007, Proceedings
Pages317-327
Number of pages11
EditionPART 2
StatePublished - 1 Dec 2007
Event2nd International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2007 - La Manga del Mar Menor, Spain
Duration: 18 Jun 200721 Jun 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume4528 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2007
CountrySpain
CityLa Manga del Mar Menor
Period18/06/0721/06/07

Keywords

  • Ant colony optimization
  • Constraint programming
  • Dial-a-ride problem
  • Hybrid algorithm
  • Set partitioning

Fingerprint Dive into the research topics of 'Solving dial-a-ride problems with a low-level hybridization of ants and constraint programming'. Together they form a unique fingerprint.

Cite this