Invited Session Tue.1.H 3003A

Tuesday, 10:30 - 12:00 h, Room: H 3003A

Cluster 5: Constraint programming [...]

Constraint programming for routing and scheduling


Chair: Louis-Martin Rousseau



Tuesday, 10:30 - 10:55 h, Room: H 3003A, Talk 1

Jean-Guillaume Fages
Solving the traveling salesman problem with constraint programming

Coauthor: Xavier Lorca


The Traveling Salesman Problem (TSP) is one of the most studied problem by the operation research community and has various practical applications, such as vehicle routing problems of logistics, microchips production optimization or even scheduling. Recent improvements have enabled constraint programming (CP) approaches to tackle medium size TSP instances. We discuss basic CP representations of the TSP and provide a short survey over state of the art models as well as an experimental study.



Tuesday, 11:00 - 11:25 h, Room: H 3003A, Talk 2

Arnaud Malapert
Scheduling a batch processing machine with constraints

Coauthors: Christelle Guéret, Louis-Martin Rousseau


We present a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and we aim to minimize several regular objective functions. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then scheduling the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on relaxed problems and applies cost-based domain filtering techniques. Cost based domain filtering aims to remove combination of values which cannot lead to solutions whose cost is better than the best one found so far. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach.



Tuesday, 11:30 - 11:55 h, Room: H 3003A, Talk 3

Louis-Martin Rousseau
Formal language for retail store workforce scheduling

Coauthors: Nicolas Chapados, Marc Joliveau, Pierre L'Écuyer


The dual role played by the sale personnels in retail store industry, which can be seen as a costly resource, as well as a set of agents that generate incomes, makes this area very specific as, unlike traditional approaches whose goal is to minimize the operating costs, the schedules of the employees can be optimized such that it directly maximize the net incomes generated by the store over a given horizon (e.g., a day or a week). In this framework, we introduce a constraint program (CP) and a mixed integer program (MIP), both based on the use of a formal language, that schedule the workforce of a retail store while considering both operating costs and operating incomes. Comparison on more than 5000 day instances measured in a clothing and apparel chain will demonstrate the advantage of CP to accurately handle the specific work regulation rules of the retailer in comparison to MIP.


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra No RX influence on blood clots.