Retour au site du LAAS-CNRS

Abstract

The ATMOSTSEQCARD constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n - q + 1 constraints ATMOST u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In [18], two algorithms designed for the AMONGSEQ constraint were adapted to this constraint with a O(2^q n) and O(n^3) worst case time complexity, respectively. In [10], another algorithm with a O(n2 log n) worst case time complexity and similarly adaptable to filter ATMOSTSEQCARD in O(n log n) was proposed. In this paper, we introduce an algorithm for achieving Arc Consistency on the ATMOSTSEQCARD constraint with a O(n) (hence optimal) worst case time complexity. We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.

Abstract

In this paper, we propose mechanisms to improve instantiation heuristics by incorporating weighted factors on variables. The proposed weight-based heuristics are evaluated on several tree search methods such as chronological backtracking and discrepancy-based search for both constraint satisfaction and optimization problems. Experiments are carried out on random constraint satisfaction problems, car sequencing problems, and jobshop scheduling with time-lags, considering various parameter settings and variants of the methods.

Abstract

Taking into account the multimodality of urban transportation networks for computing the itinerary of an individual passenger introduces a number of additional constraints such as mode restrictions and various objective functions. In this paper, constraints on modes are gathered under the concept of viable path, modeled by a non deterministic finite state automaton (NFA). The goal is to find the nondominated viable shortest paths considering the minimization of the travel time and of the number of modal transfers. We show that the problem, initially considered by Lozano and Storchi (2001), is a polynomially-solvable bi-objective variant of the mono-objective regular language-constrained shortest path problem (Barett et al., 2000, Delling et al., 2009). We propose several label setting algorithms for solving the problem: a topological label-setting algorithm improving on algorithms proposed by Pallottino and Scutella (1998) and Lozano and Storchi (2001), a multi-label algorithm using buckets and its bidirectional variant, as well as dedicated goal oriented techniques. Furthermore, we propose a new NFA state-based dominance rule. The computational experiments, carried-out on a realistic urban network, show that the state-based dominance rule associated with bidirectional search yields significant average speed-ups. On an expanded graph comprising 1 859 350 nodes, we obtain on average 3.5 nondominated shortest paths in less than 180 ms.

Résumé

Les travaux présentés dans ce document traitent de méthodes arborescentes pour la résolution de problèmes combinatoires d’optimisation ou de décision. Le premier chapitre présente les contributions que nous avons apportées pour les méthodes de résolution dites " à divergences ". Ces contributions concernent les modes de comptage des divergences pour les problèmes à variables discrètes, le développement d’une heuristique dynamique à pondération de variables, ainsi que, dans un contexte d’optimisation, l’utilisation de bornes ou d’heuristiques pour la sélection des points de divergences. Ces différentes contributions sont illustrées sur des problèmes d’ordonnancement ou sur des problèmes de satisfaction de contraintes. Le deuxième chapitre traite de propagation de contraintes pour la résolution de problèmes d’ordonnancement disjonctifs en présence de contraintes temporelles généralisées. Des extensions de méthodes de propagation de contraintes efficaces dans ce contexte sont proposées et des applications à la résolution de différents problèmes d’ordonnancement sont également présentées. Le troisième chapitre s’intéresse à un problème de calcul d’itinéraires point à point sur des réseaux de transport multi-modaux. La prise en compte de la multi-modalité fait surgir à la fois de nouvelles contraintes permettant d’exprimer si la séquence de modes d’un itinéraire conduit ou non à une solution admissible, mais aussi de nouveaux objectifs comme la minimisation du nombre de changement de modes. Le problème étudié (minimisation du temps de trajet et du nombre de transferts) est polynomial et différentes variantes basées sur le principe de l’algorithme de Dijkstra sont présentées et évaluées sur un cas réel.

Mots-Clés / Keywords