ATTENTION/WARNING - NE PAS DÉPOSER ICI/DO NOT SUBMIT HERE

Ceci est la version de TEST de DIAL.mem. Veuillez ne pas soumettre votre mémoire sur ce site mais bien à l'URL suivante: 'https://thesis.dial.uclouvain.be'.
This is the TEST version of DIAL.mem. Please use the following URL to submit your master thesis: 'https://thesis.dial.uclouvain.be'.
 

Insertion Sequence Variables in MiniCP

Delmelle, Quentin
(2022)

Files

Delmelle_17491500_2022.pdf
  • Open access
  • Adobe PDF
  • 1.14 MB
Download

Details

Supervisors
Schaus, Pierre
Faculty
Ecole polytechnique de Louvain
Degree label
Master [120] : ingénieur civil en informatique, à finalité spécialisée
Abstract
The Insertion Sequence Variable or ISV is a recently developed high-level dynamic data structure used for modeling sequences of events in constraint-programming environments. It is designed to be used as a tool for solving CP-based scheduling and routing problems. LNS-FFPA is a state of the art search algorithm for the Dial-A-Ride-Problem or DARP, a well known routing problem with many real life applications. The goal of this paper is to study the impact of the introduction of ISVs to replace regular sequence models in a LNS-FFPA solver for the DARP. To do this, 2 implementations of LNS-FFPA have been developed in MiniCP, a lightweight open-source CP environment. One uses ISVs while the other uses a regular successor array. Experimental results have shown that ISVs do not improve performance when used in a strictly implemented LNS-FFPA solver, but some modified versions of LNS-FFPA using ISVs might be promising.