A high-level, modular and declarative modeling framework for routing problems

A high-level, modular and declarative modeling framework for routing problems

Renaud De Landtsheer, Yoann Guyot, Christophe Ponsard, A high-level, modular and declarative modeling framework for routing problems, 28th annual conference of the Belgian Operational Research Society, UMons, January 30-31, 2014.

Nowadays, the technology and algorithms for solving routing problems are widespreading.
This paper proposes a modeling approach for routing problems that aims at cutting the cost required for developing dedicated solvers. Our approach ensures that the resulting models include the minimal number of modeling artifacts such as variables, constraints, and invariants, to spare the procesing power.

Our modeling approach for relies on the mechanism of traits of the Scala programming language \citescala which supports partial implementation of interfaces. A scala class can also inherit from multiple traits. We have developed a library of traits, each of them includes an aspect of routing problem (e.g. nodes predecessors, time), bundling the necessary variables, invariants, and constraints. Any combination of routing problem features can be represented by assembling them on top of a base routing class. Our library is integrated in the CBLS engine of the OscaR open source optimisation framework.

PNG - 67.1 ko
Traits hierarchy of our routing library (click to enlarge)

Site web de la conférence