Path inconsistency: models and exact approaches

  • Philipp Salzmann (Vortragende*r)

Aktivität: VorträgeVortragScience to Science


We discuss and solve multiple problems with relation to path inconsistency. Multiple branch-and-price approaches were tested as well as
two set partitioning formulations. One is very similar to the classical
periodic vehicle routing problem while the other uses problem specific
characteristics to reduce symmetries. The exact procedure was enhanced with different concepts that were proposed in the literature for
similar problems and common heuristic strategies. In addition to the
exact procedure, we discuss the existing modelling concepts for path
inconsistency with respect to their applicability in real world scenarios. We analyze their advantages and drawbacks in certain real-world
scenarios. We tested the framework on capacitated vehicle routing instances, Solomon instances, and instances for the k-dissimilar and the
m-peripatetic routing problem. The results show the impact of different
enhancement methods to the solution time and the solution characteristics of different modelling concepts. The run times can be reduced
easily by more than 75 percent with small changes to the classical labelling procedures. Even without cuts, we are able to solve a solid
proportion of the classical as well as the problem specific instances.
The strength of our framework is in its ability to solve instances with
multiple periods for different inconsistency problems. For future discussion, we propose a set of new urban instances from Vienna.
Zeitraum8 Juli 201811 Juli 2018
EreignistitelEURO 2018: 29th European Conference
OrtValencia, SpanienAuf Karte anzeigen