A Modeling Language for Rich Vehicle Routing Problems

Tuukka Puranen

Transportation is an important human activity, and moving goods,
information and people is crucial to effectiveness of our society.
A well-known combinatorial optimization problem, the Vehicle
Routing Problem (VPR) is at the core of designing effective
transportation.

In VRP a set of vehicles is to be optimally routed to visit a set
of customers with known demands subject to capacity constraints on
the vehicles. VRP has a number of extensions that consider for
instance constraints on delivery times or optimize vehicles of
different sizes. Recently, attention has been devoted to complex
variants of VRP that comprise of several of these extensions.
These problems are sometimes named “rich” VRPs.

However, we lack a unified view of vehicle routing problems. This
prevents an effective analysis of different VRP models, their
complexity and expressiveness. An extensive view on the VRP domain
is would ease cooperation and communication in scientific
community, and would raise the level of abstraction in VRP
research.

To address these issues we analyzed a number of VRP models, and
developed a modeling language for describing rich VRP models in a
unified way. In this talk we present the way to describe VRPs
using this language. Moreover, based on this analysis, we will
provide a new framework for categorizing the aspects present in
real-life routing problems.

We will argue that analyzing and categorizing the aspects of this
model will broaden our knowledge of VRP and provide us with better
ways to include real-life aspects into vehicle routing problems.