Insertion Sequence Variables in MiniCP

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.