# A review of approaches to modeling applied vehicle routing problems

Konstantin Sidorov
Adeptik

<EMAIL_ADDRESS>
Alexander Morozov
Adeptik

<EMAIL_ADDRESS>

###### Abstract

Due to the practical importance of vehicle routing problems (VRP), there
exists the ever-growing body of research in algorithms and (meta)heuristics
for solving such problems. However, the diversity of VRP domains creates the
separate problem of modeling such problems – describing the domain entities
(and, in particular, the planning decisions), the set of valid planning
decisions, and the preferences between different plans. In this paper, we
review the approaches for modeling vehicle routing problems. To make the
comparison more straightforward, we formulate several criteria for evaluating
modeling methods reflecting the practical requirements of the development of
optimization algorithms for such problems. Finally, as a result of this
comparison, we discuss several future research avenues in the field of
modeling VRP domains.

##  1 Introduction

Vehicle routing problems (VRP) are computational problems that can be
generally formulated by the following description: given a set of
transportation requests and a fleet of vehicles, determine a set of vehicle
routes to perform transportation requests with the given vehicle fleet at
minimum cost. [1]

It is important to note that vehicle routing problems differ in some (or all)
of the following points:

  * •

What are the transportation requests?

  * •

How the transportation requests must (or should) be executed?

  * •

What is a vehicle and how can it move between locations?

  * •

Which sets of routes are feasible?

  * •

How is the cost of the route set defined?

Vehicle routing problems, while being a generic and loosely defined class of
problems, turn out to be of large practical importance – it is well-known [2]
that transportation normally has a significant contribution to the final price
of the product, and the computer-aided planning can yield tangible savings to
a producing company [3]. However, since VRP contain the traveling salesman
problem, any VRP can be considered an NP-hard problem.

Despite being a computationally difficult problem, many different variations
of VRP and their solution techniques have been extensively studied [4, 5, 6].
However, this amount of research creates another problem: papers on VRP
frequently lack the common language for defining the problem in question
(which we will further refer to as _modeling language_). In particular, this
creates a fragmentation not only in problem definitions but for their solution
techniques.

The goal of this study is to review the existing general approaches to
modeling vehicle routing problems with their strengths and weaknesses. Since
VRP is a vast scope of problems, we will focus on _deterministic vehicle
routing problems_ – i.e., we will assume that all necessary problem
information is known up-front, without having to model probability
distributions (if problem information is stochastic) or tree search (if
problem information is revealed sequentially, which is known as _dynamic VRP_
[7]).

The rest of the paper is structured as follows:

  * •

Section 2 provides a general overview of vehicle routing problems. Since
domain modeling normally facilitates the development of optimization
algorithms, this section overviews not only the VRP formulations but some of
the common approaches for solving them.

  * •

In Section 3 we introduce several criteria useful for comparing different VRP
modeling approaches. This list of criteria is derived from the typical needs
of developing algorithms described in the previous section.

  * •

We review the ad-hoc approaches for modeling VRP instances and the software
tools aiding this kind of modeling in Section 4.

  * •

In Section 5 we review the mathematical programming models. Since these models
also provide a way for _solving_ the problem instances, we also review
techniques used for developing optimization algorithms for mathematical
programming models corresponding to VRP instances.

  * •

We review the methods for storing the information about problem instances in a
machine-readable way in Section 6. While this approach does not give much in a
way of developing algorithms, it is the most “specialized” for VRP instances
in general and transferable between different VRP problem definitions.

  * •

In Section 7 we provide the concluding remarks on the direct comparison of
presented approaches.

##  2 Background: vehicle routing problems

VRP algorithms Mathematical programming Constraint programming Mixed-integer
programming Flow formulations Set partitioning formulations Heuristic
algorithms Constructive heuristics … Nearest neighbor Savings algorithm
Metaheuristics … Local search Large neighborhood search Simulated annealing
Tabu search Evolutionary algorithms Genetic algorithms Ant colony optimization
Particle swarm optimization Machine learning approaches End to end learning
Learning to configure ML alongside algorithms Figure 1: Mind map of
optimization algorithms for vehicle rounting problems.

The first non-trivial VRP problem variation that has been formulated and
computationally studied is _traveling salesman problem_ , which is the problem
of finding the shortest route through a graph that visits each node exactly
once. This problem has been first studied by Karl Menger, who also pointed out
that the nearest-neighbor heuristic does not give the optimal route [8].

The study of TSP has given rise to several important optimization techniques:

  * •

_Cutting plane methods_ – an algorithm for solving integer linear programs
(which, in particular, contain TSP as a sub-class of problems) that refine a
set of feasible values by introducing new inequalities into the problem (also
known as _cuts_). These methods have been introduced as an efficient method to
solve non-trivial TSP instances _to optimality_ by George Dantzig, Delbert Ray
Fulkerson, and Selmer M. Johnson in [9].

  * •

_Branch and bound algorithms_ – a paradigm for designing optimization
algorithms that prescripts to represent the solution space as a search tree
and exhaustively explore its branches, _discarding those that cannot improve
the solution_. The discarding is normally done by maintaining lower and upper
_bounds_ on the optimal solution for all branches and comparing them with the
“running optimal” solution. As for the term “branch and bound” itself, it has
been first used by Little et al. in [10].

The systematic study of vehicle routing problems originates from the seminal
paper [11] which introduced the real-world optimization of gasoline delivery
to gas stations. The optimization problem introduced there possessed many
traits typical for modern VRP domains:

  * •

it directly involved the concept of _capacity_ – on the one hand, the
customers had some fixed resource demand, on the other hand, the customers
that could be served by a single vehicle was constrained by the vehicle
capacity;

  * •

it included both the routing component (akin to TSP) and the assignment
component (the customers had to be partitioned into multiple routes).

The algorithms for solving vehicle routing problems are summarized in Figure 1
– the remainder of this section will provide a short review of the mentioned
algorithms and relevant publications.

The _heuristic algorithms_ are the most common algorithms for such problems
and can be roughly classified as _constructive heuristics_ and
_metaheuristics_.

The constructive heuristics are procedures that construct the valid VRP
solution, normally in time polynomial in the input size and without any
guarantees in terms of solution quality. The most natural and general
constructive heuristic is _nearest neighbor algorithm_ , which constructs
vehicle routes incrementally by choosing the nearest available location on
every step, starting from the depot. The first efficient construction
heuristic for such problems has been proposed in [12] and is known as _savings
algorithm_. The algorithm proceeds as following:

  1. 1.

Make a route for each of the nodes $v_{k}$ that visits only that node:
$v_{0}\to v_{k}\to v_{0}$, where $v_{0}$ is the depot.

  2. 2.

For each pair of customers $v_{i},v_{j}$ compute savings for merging this pair
as $s_{ij}=d_{i0}+d_{j0}-d_{ij}$.

  3. 3.

For each pair of customers $v_{i},v_{j}$ _in decreasing order of savings_
merge the corresponding routes if:

     * •

customers $v_{i},v_{j}$ are not already on the same route,

     * •

both customers are directly connected to the depot (i.e., are either first or
last in the route)

     * •

the merge does not violate the capacity constraint.

  4. 4.

Return the resulting solution after no more merges can be applied.

While such procedures are normally guaranteed to terminate quickly and return
a valid solution, in general, such a solution can be arbitrarily suboptimal.
For this reason, the most efficient VRP algorithms rely on some kind of search
procedure. The most common approach for VRP domains is _metaheuristics_ –
general procedures that can be used for designing an approximation algorithm
for a problem at hand.

The simplest and most common example of a metaheuristic is _local search_ – a
family of search procedures that have the following common traits:

  * •

they start the search from a single valid solution (normally generated by some
constructive heuristic),

  * •

on each iteration, they produce a _neighborhood_ of the incumbent solution – a
set of valid solutions, normally of polynomial size and consisting of
solutions “similar” to the incumbent,

  * •

for a neighborhood of the incumbent, they choose one solution and accept it
(promote it to the incumbent solution) according to some rule – which can be
both deterministic (accept if better than incumbent) and stochastic (accept if
better, otherwise accept with some probability).

For a general review of local search applications in VRP, see [13].

While this scheme can be implemented naïvely by choosing some appropriate
neighborhood and using the trivial acceptance rule, varying the components of
local search gives rise to even more efficient metaheuristics. For example,
the _simulated annealing_ is a metaheuristic that closely follows this scheme,
differing only in the acceptance rule: if the incumbent solution has the
objective value $J$, and the new solution has the objective $J^{\prime}$, then
the new solution is accepted with the probability

$\begin{cases}1&J^{\prime}>J\\\
\exp\left(\frac{J^{\prime}-J}{T}\right)&\text{otherwise,}\end{cases}$

where $T>0$ is a _temperature_ – an algorithm parameter controlling the
“randomness” of transitions that degrade the solutions. In particular,

  * •

as $T\to 0$, the transition rule degenerates into a “greedy rule” that only
accepts improving solutions;

  * •

on the other hand, as $T\to+\infty$, the transition rule degenerates into a
“random search” which accepts _any_ proposed solution regardless of its
quality.

These two extremes are normally used in the following way: the temperature is
initialized to some large value at the start of the algorithm and gradually
reduced according to some _annealing schedule_ , thus interpolating between
the random search in the beginning and “greedy” search on later stages of the
algorithm.

The first usage of the term “simulated annealing”, as well as the first
application of this technique to TSP, can be found at [14]. The first study
that used simulated annealing for solving VRP is [15]; the paper [16] has the
first description of non-hybrid simulation annealing strategy for VRP.

Another local search technique widely known in the VRP community is _tabu
search_. The metaheuristic can be generally described by changing the
acceptance rule: in tabu search, the new solution can be accepted even if it
is worse than the incumbent, but the search algorithm maintains the _tabu
list_ – a special data structures that maintain the recent solutions and
forbid returning to them.

The first application of tabu search to VRP can be found at [17]; for the more
comprehensive review of tabu search algorithms and domain-specific techniques
used for implementing such algorithms, see [18].

Another important class of algorithms is _evolutionary algorithms_ – unlike
local search, they maintain a _population_ of valid solutions and iteratively
improve the population as a whole. The prime example is the family of _genetic
algorithms_ , which repeats the following operations with the population:

  1. 1.

_Selection_. This operation removes the part of existing solutions, normally
preferring to remove worse solutions.

  2. 2.

_Crossover_. This operation selects multiple pairs of solutions (typically in
a way that prefers the best solutions) and constructs new solutions from
them111This process can be informally seen as breeding a new generation of
solutions..

  3. 3.

_Mutation._ At this stage, the solutions of the population are _individually_
and randomly changed in a way similar to a single step of local search.

The first work that described the genetic algorithm competitive with the tabu
search on vehicle routing problems is [19]. For the classic introduction to
the field of genetic algorithms, see [20].

A comprehensive treatment of metaheuristic algorithms, their implementation
details, and theoretical analysis, can be found in the monograph [21].

The _mathematical programming_ models are mathematical models constructed by
the following scheme:

  * •

The model introduces _decision variables_ for domain decisions (i.e.,
assignment of customers to vehicles or a sequence of visits for vehicles).

  * •

The set of valid assignments for decision variables is defined by the set of
_constraints_ – predicates involving decision variables, normally having some
restricted form.

  * •

The assignments for decision variables are ranked by _objective function_ – a
function that maps such assignments to real values. The objective function is
used to encode preferences between valid solutions.

In the context of VRP domains, the most relevant classes of mathematical
programming models are:

  * •

_Mixed-integer programming_ (MIP), which is a class of mathematical
programming problems in which the problem domain is specified by inequalities
over real and/or integer variables. A very important special case is mixed-
integer _linear_ programming, which further restricts the problem to linear
inequalities and linear objective function.

  * •

_Constraint programming_ (CP) is another class of mathematical programming
models, in which the decision variables are restricted to _finite sets_ , but
the constraints can be specified by _arbitrary relations_ between decision
variables.

For further discussion of mathematical programming models for VRP domains, see
Section 5.

Recent developments in the field of machine learning have created the _machine
learning_ approach to solving vehicle routing problems. The general overview
of the machine learning applications to the more general context of
combinatorial optimization can be found in the review [22]. Such approaches
can be classified by their place in the resulting algorithm:

  * •

_End to end learning_ approaches attempt to build a model that _directly_
solves the problem instance. This approach is implemented in many papers
utilizing such an approach – some of the examples are [23], [24], [25], and
[26].

  * •

_Learning to configure algorithms_ approaches, on the contrary, don’t
influence the search process directly – rather, they attempt to provide useful
information for other solving approaches (e.g., by selecting the algorithm
parameters). This approach is similar to _meta-learning_ approach in machine
learning, which is used to select the most performing machine learning model
for a given dataset [27]. Applications of this approach to vehicle routing
problems include [28] and [29], while paper [30] investigates feature
selection for applying this approach to TSP.

  * •

_Machine learning alongside optimization algorithms_ approaches combine the
previous two approaches in the sense that they build a model for guiding the
search algorithm. The research in this area for VRP is more sparse than for
the other two approaches – one of the recent papers that studies this approach
for VRP domains is [31].

##  3 Evaluation criteria

The wide range of VRP models and their solution methods creates a separate
problem for _modeling_ VRP domains. In the remainder of this review we will
introduce several modeling methods – but, since the field of vehicle routing
problems is diverse, we need a way to define the strong and weak sides of such
methods. To this end, we have to define a set of criteria that will be used to
evaluate modeling approaches. From the discussion of the approaches to solving
VRP domains, we derived the following criteria:

  * •

_Expressiveness of modeling language_. The modeling languages satisfying this
criterion should provide modeling constructs for various situations typical to
VRP domains (which include temporal constraints or modeling different entity
types).

  * •

_Unambiguous domain entity modeling_. This criterion separates the modeling
approaches that inherently allow modeling standard VRP constructs. In
particular, this criterion is somewhat similar to the following quote of _Zen
of Python_ [32]: “There should be one — and preferably only one — obvious way
to do it”.

  * •

_Separation of domain-level and instance-level modeling_. Using this
criterion, we would like to separate the modeling systems that have a clear
divide between the part that models the domain and the part that encodes the
actual problem instance data. In the VRP context, this is particularly useful,
because, as we have already seen, modeling the domain entities in VRP domains
can itself be a non-trivial task.

  * •

_Additional complexity of developing optimization algorithms for problem
domains_. This criterion will be used to show how much overhead does the
modeling approach introduces to the task of algorithm development (in
comparison with the ad-hoc modeling).

  * •

_Portability of optimization modules across problem domains_. This criterion
separates the systems for which developing the optimization algorithms working
_across_ the problem domains is not substantially harder than developing the
optimization algorithms for a _single_ problem domain.

##  4 Ad-hoc VRP models

The most natural way to model the optimization problem in question is by
laying out its domain model in code – an approach which we will further refer
to as _ad-hoc modeling_.

As we will see further, there are more “principled” approaches to VRP modeling
– however, the strong side of ad-hoc modeling is that it scales well if there
is _only one_ problem domain that needs to be dealt with. In particular, this
approach is dominant for _rich VRPs_ , which are commonly defined as VRP
models with multiple heterogeneous entities and/or constraints. A taxonomy for
such problems, as well as a statistical definition for “richness”, is provided
in [33]. In particular, even though _VRP-REP_ , the collection of VRP domains
and their respective instances [34], provides its standard for defining
instances, at the moment of writing _less than a half_ of domains represented
at VRP-REP, actually use this standard. (For further information about VRP-
REP, see Section 6.2.)

One of the most well-known software toolkits for this modeling approach is
OptaPlanner [35] – a Java library branded as “an AI constraint solver” which
aids the development of optimization algorithms by providing the workflow with
the following steps:

  * •

_Domain model introduction_. At this stage, the entities of the domain are
defined as POJOs222 _Plain Old Java Objects_ – a software engineering concept
that normally denotes a Java object. This term is normally understood as an
antonym for objects used in more complicated frameworks that, in particular,
frequently have to implement prespecified interfaces, extend prespecified
classes or contain prespecified annotations [36]. in the same way it is
normally done in software engineering.

  * •

_Search space definition_. At this stage, the developer annotates some of the
entities as _planning_ entities (a concept also known as “decision variables”)
and defines their respective ranges. This is normally done by defining a POJO
for a solution (e.g., in VRP case it would likely contain a mapping between
vehicles and their routes) and specifying constraints (and an objective as
well) with a factory class that returns a list of hard/soft constraints for
given domain entities.

  * •

_Finding the solution_. In the case of OptaPlanner, this stage reduces to the
invocation of the built-in Solver class which contains the actual optimization
logic. It should be stressed, however, that the OptaPlanner only provides
building blocks for implementing local search algorithms, somewhat limiting
the performance of the resulting algorithm.

##  5 Mathematical programming models

The more principled approach to modeling VRP problems is to state them as
_mathematical programming_ problems, i.e. representing the problem domain in
question as a problem of selecting an element of a set (normally given by a
list of _constraints_ parameterized by _decision variables_) that
maximizes/minimizes the _objective function_ (a function that maps the
elements of the domain to real numbers).

This approach is well known far beyond VRP context – in fact, it has a vast
body of research both for theoretical properties of such problems and for its
practical applications. Since the scope of this work is limited to the VRP
applications, we will introduce only a (small) part of mathematical
programming research directly relevant to the VRP context. More exactly, we
will review two classes of models mentioned in Section 2: mixed-integer
programming (Section 5.1) and constraint programming (Section 5.2).

###  5.1 Mixed-integer programming models

Aside from ad-hoc modeling, the most common approach to model routing problems
is _mixed-integer programming_ – a class of mathematical optimization models
that employ numeric variables, some types of algebraic constraints (e.g.,
linear or quadratic), and integrality constraints on some of the variables.

The simplest VRP variant that can be modeled with this approach is _traveling
salesman problem_. Without loss of generality we will assume that the graph
has $n$ nodes $1,2,\dotsc,n$ and edges having lengths $c_{ij}$.

The common issue of TSP modeling via MIP is the _subtour elimination_ , i.e.
imposing a constraint that forbids selecting two or more different tours
partitioning the node set and otherwise giving a feasible solution. There are
two common formulations for the TSP which differ by the way they define the
subtour elimination constraints:

  * •

_Miller-Tucker-Zemlin formulation_ (MTZ) defines a variable $x_{ij}\in{0,1}$
for each edge and a dummy variable $u_{i}\in\mathbb{Z},1\leq u_{i}\leq n-1$
for each node (except the node $1$, which is implicitly assumed to start the
tour). The subtour elimination is implemented by introducing a constraint
$u_{i}-u_{j}+nx_{ij}\leq n-1$ for each edge $(i,j)$ not incident to node $1$ –
thus, the dummy variables implement the tour ordering. It can be shown that
this constraint (1) successfully eliminates subtour solutions and (2) remains
feasible for any complete tour defined by $x$-variables. [37]

  * •

_Dantzig–Fulkerson–Johnson formulation_ (DFJ) defines only variables
$x_{ij}\in{0,1}$ for each edge $(i,j)$ and implements the subtour elimination
by imposing a flow constraint for each node subset $Q\subset\\{1,\dotsc,n\\}$
such that $1<\\#Q<n$ (i.e., it has at least two nodes but is a strict subset):
$\sum_{i\in Q,j\in Q,i\neq j}x_{ij}\geq 1$. [9]

While MTZ formulation, unlike DFJ, can be formulated with a _polynomial-size_
integer linear program, it is known [38] that DFJ formulation ends up being
stronger in a sense that the relaxations resulting from it give tighter upper
bounds on the optimal solution value.

Unlike TSP, however, VRP has an additional decision-making level, since the
customers should not only be served but also partitioned between vehicles. Two
common approaches to this are _flow formulations_ and _set partitioning
formulations_.

Flow formulations are the direct generalizations of DFJ formulation, which
introduce a binary variable for each edge and constrain their value in a way
that preserves both the flow structure of the tours and does not generate sub-
tours.

The typical example of such formulation has been first introduced by [39]. Let
$G=(V,E,\mathbf{c})$ be a weighted graph for which we have to solve the
_capacitated VRP_ – a problem of selecting $K$ routes of shortest total length
partitioning the set of customers and starting from the depot node $0\in V$.
The model in question introduces the decision variable $x(e)\in\\{0,1\\}$ for
each edge of the network that represents the decision on whether to take the
edge in the route. Let $\delta^{+}(v)$ and $\delta^{-}(v)$ be respectively a
set of edges outgoing from $v$ and incoming to $v$, and for any set of edges
$E^{\prime}\subset E$ we will introduce the notation
$x(E^{\prime}):=\sum_{e\in E^{\prime}}x(e)$. In this framework, the final MIP
is as follows:

$\displaystyle\bm{c}^{T}\bm{x}\to\min$ $\displaystyle\forall v\in V$
$\displaystyle:x(\delta^{+}(v))=1$ $\displaystyle\forall v\in V$
$\displaystyle:x(\delta^{-}(v))=1$ $\displaystyle x(\delta^{+}(0))=K$
$\displaystyle\mathbf{1}^{T}\bm{\lambda}=K$ $\displaystyle\forall
V^{\prime}\subset V$ $\displaystyle:x(\delta^{+}(V^{\prime}))\geq
r(V^{\prime})$

The constraints model (respectively) the degree restrictions (each node should
be entered and left exactly once), the route count, and the sub-tour
elimination constraints.

This type of MIP models, while simple, has several major drawbacks:

  * •

Flow models are constrained to the case when the objective and constraints are
linear with respect to the variables. In particular, this makes the modeling
of non-linear constructs, such as time windows or commodity compatibility,
practically impossible.

  * •

Flow models do not give any way to point the vehicle that traverses any given
edge. In particular, this kind of model cannot be applied for modeling
problems in which the travel cost for an arc/feasibility of the vehicle move
depends on the vehicle that travels through it.

More advanced approach to modeling VRP is set partition formulations. The key
difference from flow formulations is that the variables are introduced not for
the edges, but for the _circuits_ – cyclic routes that go through the
customers starting from the depot. For capacitated VRP the first such model
has been introduced in [40]. Let
$\Lambda=\\{\Lambda_{1},\dotsc,\Lambda_{C}\\}$ be the set of all circuits, and
for all vertices $v$ let $\bm{a}_{v}\in\\{0,1\\}^{C}$ be the vector that
specifies which circuits pass through this vertex: $a_{vc}=1\Leftrightarrow
v\in\Lambda_{c}$. The model in question introduces the decision variables
$\bm{\lambda}\in\\{0,1\\}^{C}$ and formulates the following MIP:

$\displaystyle\bm{c}^{T}\bm{\lambda}\to\min$ $\displaystyle\forall v\in V$
$\displaystyle:\bm{a}_{v}^{T}\bm{\lambda}=1$
$\displaystyle\bm{1}^{T}\bm{\lambda}=K$ $\displaystyle\forall r$
$\displaystyle:\lambda_{r}\in\\{0,1\\}$

The decision variables $\bm{\lambda}$ correspond to all feasible circuits, and
the constraints require that (respectively) each customer has to be served
exactly once, a total of $K$ circuits has to be selected and each circuit can
be selected at most once.

The way to address this issue is _column generation_ , which can be described
for VRP as follows:

  1. 1.

Choose a (small) set of circuits for optimization.

  2. 2.

Solve the linear relaxation of the VRP formulation and derive the optimal dual
variables for constraints.

  3. 3.

Find a circuit that (a) has not been selected yet and (b) has the most
negative reduced cost. The optimization problem solved at this step is called
the _pricing problem_.

  4. 4.

If no such circuit exists, return the best incumbent solution (it is optimal).
If not, add the new circuit to the set of circuits and return to (2).

Set partition formulations, unlike flow formulations, resolve the feasibility
issue _implicitly_ , i.e. by specifying the set of routes rather than by
direct constructions of constraints. This makes such an approach much more
general than the flow formulations. However, its key problem is the number of
variables, which is at least exponential with respect to the instance size.

While MIP is a common approach for mathematical optimization, it has several
limitations which make it unsuitable for many practical problems:

  * •

_Modeling constructs_. MIP solvers normally are very restricted in the form of
constraints – i.e., linear programs only allow the usage of linear
expressions. However, many practical constraints are inherently non-linear –
for instance, modeling different vehicle types, compatibility between
resources or depot constraints, while technically viable to MIP modeling, do
not result in models that are suitable for modern MIP solvers.

  * •

_Non-trivial solution methods_. Unlike most typical MIP use cases, modeling
VRP with MIP requires more than just constructing a model for a MIP solver –
it also requires a careful approach for orchestrating MIP solver runs (column
generation in set partitioning formulations, valid inequality generation in
the flow models). This point, in particular, weakens this approach with
respect to ad-hoc modeling, for which a vast family of metaheuristic
strategies has been devised.

  * •

_Temporal constraints_. The major problem with employing time windows in the
MIP models is that the resulting models are inherently nonlinear – for
example, see the [41] for the description of the first such model – and if
they can be successfully linearized, the resulting models normally contain
many big-M constraints, which are known to be computationally difficult for
MIP solvers.

###  5.2 Constraint programming models

Another approach to VRP modeling is rewriting the problem in question as a
_constraint programming_ problem – an optimization problem with the following
traits:

  * •

The variables are specified by their domain, which is given as a _finite_ set.

  * •

The set of feasible solutions is defined by the set of constraints – unlike
MIP constraints, CP constraints are specified as an _arbitrary_ relation
specified on a subset of variables.

Constraint programming is known to be a feasible approach for domains in which
the optimization problem (or satisfiability problem) is specified on a set
without a “good” geometry, like type inference [42] or automated planning
[43].

The most common approach to modeling VRP problems as CP problems is as
follows:

  1. 1.

For each customer model the next customer visited by the same vehicle as a
decision variable.

  2. 2.

Introduce any other domain quantities (current time, load, etc.) as decision
variables, and define them for each trip using the path constraint.

  3. 3.

Introduce the domain constraints by appropriately constraining the decision
variables introduced in (2).

One of the first studies to explore this approach is [44], which introduces a
CP model for a VRP variant with vehicle capacities and time windows. This
study sidesteps the traditional tree search algorithms, introducing instead of
them ad-hoc local search algorithms. This can be seen as a way of exploiting
the domain knowledge (in this case, the local search operators known to work
well on VRP problems) in the constraint programming framework.

Constraint programming can also be used to optimize parts of the search
algorithm. For example, [45] presents an approach that uses LNS for searching
the solution space, and constraint programming to efficiently restore the
parts of the solution during the construction phase.

While this approach is less studied than MIP modeling, its key practical
benefit is the _rich modeling language_ it provides. Unlike MIP models which
are heavily restricted in the expressions that can be used in them, CP
modeling languages allow using a wide range of constructs, normally including
arbitrary logical expressions and custom constructs such as “all-different”.
The prime example of such modeling language is MiniZinc [46], which directly
supports several constructs directly useful for modeling vehicle routing
problems, such as circuit constraints, path constraints, or “all-different”
constraint, which are impossible to model in the MIP framework practically.

The downsides of reducing a VRP problem to a CP problem are:

  * •

_Non-trivial modeling choices_. The flexibility of the modeling approach
frequently introduces several ways to implement the same construct, which can
subtly influence the performance of the solver. The simplest relevant example
is the traveling salesman problem, for which multiple fundamentally different
MiniZinc models can be devised; see [47] for a review of this topic.

  * •

_Complexity of the constraint programming_. The normal downside of having a
flexible modeling language is the complexity of algorithms for resolving this
language. CP, in general, is an NP-complete problem – while there are CP
subcases that allow polynomial algorithms, such as Datalog, they turn out to
be not sufficient for VRP modeling cases.

##  6 Formal languages for VRP problem instances

While the amount of VRP research grows, one of the problems common for many
research papers is the benchmark problem set – in most cases, it is defined in
an ad-hoc way and specified with the instance statistics and their
distribution (e.g., “the depot is located in a point uniformly distributed at
the unit square”). The existence of such benchmark set (as seen with, for
example, MIPLIB [48] and MiniZinc Challenge [49]) can be helpful in several
ways, such as:

  * •

the unified, reproducible benchmark for further research,

  * •

unambiguous evaluation method for new optimization techniques,

  * •

centralized location for new problem instances.

The main approaches for defining and collecting VRP instances are:

  * •

extending and customizing plain-text formats for similar problems,

  * •

embedding an instance specification into a general-purpose document language.

###  6.1 Customizing plain-text formats

One of the most widespread formats for describing VRP instances is TSPLIB and
its variations. TSPLIB [50] is a plain-text format for traveling salesman
problems (and some of its variants) which mandates the following instance
structure:

  * •

_Problem specification part_. In this part the problem type (such as TSP or
capacitated VRP) is explicitly declared; this part defines what inputs can be
used further. In particular, one of the problem types explicitly defined in
the specification is the standard capacitated vehicle routing problem.

  * •

_Data part_. In this part, the entities from the instance (such as the depot,
vehicles, and customers) are completely defined with all of their features.

The list of problems that can be modeled by TSPLIB is explicitly specified by
the specification and contains the following problems:

  * •

TSP, both in symmetrical and asymmetrical forms – the former differing in the
additional assumption that the distance from A to B is the same as the
distance from B to A.

  * •

_Hamiltonian cycle problem_ – a problem of testing whether a graph has a
Hamiltonian cycle.

  * •

_Sequential ordering problem_ – a restricted version of asymmetrical TSP with
an additional set of _precedence_ restrictions requiring that for some
locations A and B the route has to visit A before B.

  * •

_Capacitated VRP_.

For example, to specify the capacitated VRP, the TSPLIB file has to provide
the specification part and the data part. As a running example, we will
demonstrate how to model the CVRP with 4 nodes, 2 depots, and a vehicle
capacity of 100. The specification part would be structured as follows:

  * •

The type of problem is given by the line TYPE : CVRP.

  * •

The number of nodes is given by the line DIMENSION : 6 , where 6 stands for
the _total_ number of nodes.

  * •

The vehicle capacity is given by the line CAPACITY : 100.

  * •

The distances between the locations can be given in different ways – however,
for brevity, we will use the geographical distance, which is specified by
lines EDGE_WEIGHT_TYPE : GEO and NODE_COORD_TYPE : TWOD_COORDINATES (the
latter used for specifying the latitude and longitude).

As for the data part, it is given by:

  * •

The node locations are given in NODE_COORD_SECTION by writing a numerical
identifier and a list of coordinates for each of the locations. In our
example, this might look as follows:

        1 48.0 46.0
    2 48.1 45.9
    3 48.2 46.0
    4 47.9 46.2
    5 47.8 46.1
    6 47.7 45.8

  * •

The depot nodes are listed in section DEPOT_SECTION; for example, we can
specify that nodes 2 and 4 are depots as follows:

        2
    4
    -1

  * •

The demands of the remaining nodes are given in DEMAND_SECTION (the depot
demands also have to be filled in by zero values). In our example, this may
look as follows:

        1 50
    2 0
    3 70
    4 0
    5 30
    6 60

On this example we can already see unique traits of such representations
useful for VRP modeling:

  * •

TSPLIB gives a direct, unambiguous model for domain entities (albeit cluttered
between file parts): this model is, in fact, explicitly stated in the
specification.

  * •

TSPLIB allows switching between different domain models, even if the choices
for that are rather restricted.

  * •

Last but not least, TSPLIB is _tailored_ for modeling VRP domains – in
particular, it contains vehicles and locations as _native_ constructs.

However, there are several obvious drawbacks for general-purpose vehicle
routing problem modeling:

  * •

_Ontological complexity of the underlying problems_. Unlike MIP or CP, VRP is
not a well-defined class of problems. This creates difficulties for any format
that explicitly depends on the problem structure – in fact, this problem is a
key feature of VRP that makes it harder for formal modeling than MIP or CP.

  * •

_Poor extensibility of the instance format_. While the TSPLIB format itself is
strictly defined, the extension mechanism for it is not regulated. For this
reason, the proposed extensions of the format are defined only with respect to
the original format – neither the interoperability of the extensions nor their
logical consistency rules are not defined, which creates additional
difficulties for any unification attempts.

  * •

_Lack of distinct separation between domain model and instance data_.
Arguably, the problem specification part of TSPLIB is supposed to be a domain
model, but it contains multiple numeric fields that are not essential for the
problem domain (for example, the number of vehicles and locations).

Some of these drawbacks are related to the fact that the TSPLIB offers an ad-
hoc format for storing the problem information – and, indeed, some of them
have been successfully resolved by leveraging more general-purpose
representations. One of the most successful such attempts is presented in the
next subsection.

###  6.2 Embedding into general-purpose languages

Another approach to model this class of problems is using some existing
language, defining its subset, and adapting existing tools for processing this
language for domain requirements. The most well-known effort of this kind is
VRP-REP [34], which is a collaborative platform that allows users to share
instances with the public or privately with platform editors and referees, as
well as solutions to the published instances.

VRP-REP gives an option for using the specification format – which can be
described as an XML document [51] with some predefined syntactic structure of
the problem instances. It should be explicitly noted that this specification
is not mandatory for uploading data to VRP-REP, and thus it also contains
instances written in custom (and even ad-hoc) formats.

The latest version of the specification (0.5.0, January 8, 2016) is
implemented as XML schema [52] – an XML document providing the formal
syntactic structure of the instances, as well as the documentation of the
syntactic structures. The problem instance is provided by the element
<instance> containing the following children:

  * •

The element <info> stores instance metadata – the dataset name and the
instance name.

  * •

The element <network> describes the nodes of the network and the links between
nodes, which are given by child elements <nodes> and <links> respectively:

    * –

The <nodes> element contains a collection of <node> elements describing
individual nodes. Each of such elements contains an identifier, a type (0 for
depots, 1 for customers) and coordinates. For instance, one of the customer
nodes from the example above would be described as:

<node id="1" type="1">

<latitude>48.0</latitude>

<longitude>46.0</longitude>

</node>

    * –

The <links> element contains a collection of <link> elements describing
individual links. Each of such elements contains a head, a tail (node
identifiers) and optional descriptions, such as length, travel time, time
window, etc. For instance, to specify that the travel time between node 1 and
3 is 10 minutes, one can use the following construction:

<link head="1" tail="3">

<travel_time>10</travel_time>

</link>

  * •

The <fleet> element describes the fleet available for executing the requests
and is described by a set of vehicle profiles provided in <vehicle_profile>
elements. Each vehicle profile is defined by its departure nodes, arrival
nodes, as well as with such VRP-specific characteristics as capacity, speed
profile, costs, etc. For example, to specify a single vehicle with a fixed
capacity that can start from any depot, one can use the following node:

<vehicle_profile type="1">

<departure_node>2</departure_node>

<departure_node>4</departure_node>

<arrival_at_any_node />

<capacity>100</capacity>

</vehicle_profile>

  * •

The <requests> element contains the information about the demands of the
network nodes. Each request is specified by the <request> node and provides
information about the requesting node, the amount, the time window, etc. The
request for the first node can be modeled with the following node:

<request id="1" node="1">

<quantity>50</quantity>

</request>

  * •

Optional elements <resources> and <drivers> can be provided to model the
domains in which it is important to (respectively) introduce the resources
(for example, fuel or charge) and differentiate not only vehicles but their
drivers (for example, to model special vehicle types requiring some special
skillset or compatibility.

Using XML schema for the definition of the instance structure is an
improvement to the plain-text format. Indeed, it offloads the ontological
complexity of VRP to XML toolchain, and (partially) solves the extensibility
problem by involving users in the discussion of the XML specification. Another
strength of this approach is the multitude of modeling constructs provided by
the specification, which cover various practical situations.

However, this approach also has a clear drawback in _lack of clear “problem
specification”_ : the problem specification is controlled by the XML schema,
which allows constructing instances (which corresponds to TSPLIB “data part”),
but fails to give tools for constructing a specification of the problem at
hand – i.e., defining custom entities and the relations between them. Even
though TSPLIB does not completely manage to separate these two sides of the
problem, its specification introduces the explicit divide between them – for
this reason, this shortcoming of VRP-REP can be seen as a “step backward” with
respect to existing approaches.

Another weakness of this approach is the _complexity of the specification_ –
to support so many various constructs, the specification has to explicitly
include all of them, which results in the XML schema of 1351 lines. This can
partially explain the fact that many VRP-REP users choose not to use the
official specification – moving to the new format requires understanding this
specification first, which turns out to be an issue due to its sheer size.

##  7 Conclusions and future work

Given the growing economical importance of vehicle routing problems, the new
approaches for modeling them develop. For this reason, it becomes increasingly
more important to be aware not only of their existence but about their
strengths and weaknesses. In this review we introduced the most important
modeling approaches for vehicle routing problems; the results of our analysis
(with respect to the criteria from Section 3) are summarized in Table 1. The
main conclusions for the studied approaches are as follows:

  * •

_Ad-hoc modeling_ is normally used to directly transfer the domain model into
source code. This approach sacrifices the modeling flexibility, which, in
particular, hinders the portability of optimization modules. Since the most
common approaches for VRP are metaheuristic approaches, the ad-hoc approach is
effective for developing optimization algorithms – this approach leverages the
toolchain of the selected programming language to aid the algorithm
development.

  * •

_Mathematical programming modeling_ explicitly allows separating the domain
model from the instance data. However, since such models are not tailored for
VRP constructs, most rich models involve using unintuitive modeling constructs
(and choosing between them, which also affects the algorithm quality). Using
such models also involves using rather complex schemes for solving them (for
example, the column generation in MIP models) – which, on the other hand, end
up being transferable between different models.

  * •

_Formal language modeling_ eliminates modeling ambiguity by design but does
not provide a boundary between domain model and instance data. For this
reason, the complexity and portability of optimization algorithms heavily
depend on the language specification.

Table 1: Comparison of modeling approaches introduced in the review Criterion |  Ad-hoc modeling |  Mathematical
programming |  Formal languages
---|---|---|---
Expressiveness of modeling language |  Expressive |  Lacks multiple typical features of VRP domains |  Expressive
Unambiguous domain entity modeling |  Unambiguous |  Ambiguous |  Unambiguous
Separation of domain modeling |  No separation |  Clear separation |  Minimal separation, not extensible
Complexity of developing optimization algorithms |  Low |  High |  Low
Portability of optimization modules |  Not portable |  Portable |  Portable

From this comparison, it is clear that the key direction for further research
is developing the modeling technology having a more clear balance between the
evaluation criteria. In our opinion, the approach that is the most suitable
for this development is the approach based on formal languages. In that case,
the key problem is how to integrate the strengths of other approaches with the
formal language in question.

## Funding

This research did not receive any specific grant from funding agencies in the
public, commercial, or not-for-profit sectors.

## References

  * [1] Stefan Irnich, Paolo Toth, and Daniele Vigo.  Chapter 1: The Family of Vehicle Routing Problems.  In Vehicle Routing, pages 1–33. Society for Industrial and Applied Mathematics, nov 2014.
  * [2] Jean-Paul Rodrigue.  The Geography of Transport Systems.  Routledge, 5 edition, 2020.
  * [3] Geir Hasle and Oddvar Kloster.  Industrial vehicle routing.  In Geometric Modelling, Numerical Simulation, and Optimization: Applied Mathematics at SINTEF, pages 397–435. Springer Berlin Heidelberg, 2007\.
  * [4] Burak Eksioglu, Arif Volkan Vural, and Arnold Reisman.  The vehicle routing problem: A taxonomic review.  Computers and Industrial Engineering, 57(4):1472–1483, nov 2009\.
  * [5] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, and Christian Prins.  Heuristics for multi-attribute vehicle routing problems: A survey and synthesis.  European Journal of Operational Research, 231(1):1–21, nov 2013\.
  * [6] Kris Braekers, Katrien Ramaekers, and Inneke Van Nieuwenhuyse.  The vehicle routing problem: State of the art classification and review.  Computers and Industrial Engineering, 99:300–313, sep 2016.
  * [7] Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L. Medaglia.  A review of dynamic vehicle routing problems.  European Journal of Operational Research, 225(1):1–11, feb 2013\.
  * [8] Alexander Schrijver.  On the History of Combinatorial Optimization (Till 1960), pages 1–68.  Elsevier, 2005.
  * [9] G. Dantzig, R. Fulkerson, and S. Johnson.  Solution of a Large-Scale Traveling-Salesman Problem.  Journal of the Operations Research Society of America, 2(4):393–410, nov 1954.
  * [10] John D. C. Little, Katta G. Murty, Dura W. Sweeney, and Caroline Karel.  An algorithm for the traveling salesman problem.  Operations Research, 11(6):972–989, 12 1963.
  * [11] G. B. Dantzig and J. H. Ramser.  The truck dispatching problem.  Management Science, 6(1):80–91, 10 1959.
  * [12] G. Clarke and J. W. Wright.  Scheduling of vehicles from a central depot to a number of delivery points.  Operations Research, 12(4):568–581, 08 1964.
  * [13] Olli Bräysy and Michel Gendreau.  Vehicle routing problem with time windows, part i: Route construction and local search algorithms.  Transportation Science, 39(1):104–118, 02 2005.
  * [14] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.  Optimization by simulated annealing.  Science, 220(4598):671–680, 1983.
  * [15] Ibrahim Hassan Osman.  Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem.  Annals of Operations Research, 41(4):421–451, 12 1993.
  * [16] Wen-Chyuan Chiang and Robert A. Russell.  Simulated annealing metaheuristics for the vehicle routing problem with time windows.  Annals of Operations Research, 63(1):3–27, 02 1996.
  * [17] Michel Gendreau, Alain Hertz, and Gilbert Laporte.  A tabu search heuristic for the vehicle routing problem.  Management Science, 40(10):1276–1290, 10 1994.
  * [18] Fred Glover and Manuel Laguna.  Tabu Search.  Springer US, 1997.
  * [19] Barrie M. Baker and M.A. Ayechew.  A genetic algorithm for the vehicle routing problem.  Computers & Operations Research, 30(5):787–800, 04 2003.
  * [20] David E. Goldberg.  Genetic Algorithms in Search, Optimization and Machine Learning.  Addison-Wesley Longman Publishing Co., Inc., USA, 1st edition, 1989.
  * [21] Michel Gendreau and Jean-Yves Potvin, editors.  Handbook of Metaheuristics.  Springer US, 2010.
  * [22] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost.  Machine learning for combinatorial optimization: A methodological tour d’horizon.  European Journal of Operational Research, 290(2):405–421, 2021\.
  * [23] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio.  Neural combinatorial optimization with reinforcement learning.  arXiv preprint arXiv:1611.09940, 2016.
  * [24] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial optimization algorithms over graphs.  arXiv preprint arXiv:1704.01665, 2017.
  * [25] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V Snyder, and Martin Takáč.  Reinforcement learning for solving the vehicle routing problem.  arXiv preprint arXiv:1802.04240, 2018.
  * [26] Wouter Kool, Herke Van Hoof, and Max Welling.  Attention, learn to solve routing problems!  arXiv preprint arXiv:1803.08475, 2018.
  * [27] Joaquin Vanschoren.  Meta-Learning, pages 35–61.  Springer International Publishing, 2019.
  * [28] Raras Tyasnurita, Ender Ozcan, and Robert John.  2017 ieee congress on evolutionary computation (cec).  IEEE, 06 2017.
  * [29] Andres E. Gutierrez-Rodríguez, Santiago E. Conant-Pablos, José C. Ortiz-Bayliss, and Hugo Terashima-Marín.  Selecting meta-heuristics for solving vehicle routing problems with time windows via meta-learning.  Expert Systems with Applications, 118:470–481, 03 2019.
  * [30] Jorge Kanda, Andre de Carvalho, Eduardo Hruschka, Carlos Soares, and Pavel Brazdil.  Meta-learning to select the best meta-heuristic for the traveling salesman problem: A comparison of meta-features.  Neurocomputing, 205:393–406, 09 2016.
  * [31] Lei Gao, Mingxiang Chen, Qichang Chen, Ganzhong Luo, Nuoyi Zhu, and Zhixin Liu.  Learn to design the heuristics for vehicle routing problem, 2020.
  * [32] Tim Peters.  The Zen of Python.  PEP 20, 2004.
  * [33] Rahma Lahyani, Mahdi Khemakhem, and Frédéric Semet.  Rich vehicle routing problems: From a taxonomy to a definition.  European Journal of Operational Research, 241(1):1–14, 02 2015\.
  * [34] Jorge Mendoza, M. Hoskins, Christelle Guéret, Victor Pillac, and D. Vigo.  VRP-REP: a vehicle routing community repository, 2014.
  * [35] Geoffrey De Smet and open source contributors.  OptaPlanner User Guide.  Red Hat, Inc. or third-party contributors, 2006.  OptaPlanner is an open source constraint solver in Java.
  * [36] Martin Fowler.  Mf bliki: Pojo.  https://www.martinfowler.com/bliki/POJO.html.  Accessed: 2021-03-22.
  * [37] C. E. Miller, A. W. Tucker, and R. A. Zemlin.  Integer Programming Formulation of Traveling Salesman Problems.  Journal of the ACM, 7(4):326–329, oct 1960.
  * [38] Mark Velednitsky.  Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem.  Operations Research Letters, 45(4):323–324, jul 2017.
  * [39] Gilbert Laporte, Hélène Mercure, and Yves Nobert.  An exact algorithm for the asymmetrical capacitated vehicle routing problem.  Networks, 16(1):33–46, 1986.
  * [40] M. L. Balinski and R. E. Quandt.  On an Integer Program for a Delivery Problem.  Operations Research, 12(2):300–304, apr 1964.
  * [41] Edward K. Baker.  Exact Algorithm for the Time-Constrained Traveling Salesman Problem.  Operations Research, 31(5):938–945, oct 1983.
  * [42] Satish Chandra, Colin S Gordon, Jean-Baptiste Jeannin, Cole Schlesinger, Manu Sridharan, Frank Tip, and Youngil Choi.  Type inference for static compilation of JavaScript.  In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 410–429, New York, NY, USA, oct 2016. ACM.
  * [43] Antonio Garrido, Marlene Arangu, and Eva Onaindia.  A constraint programming formulation for planning: From plan scheduling to plan generation.  Journal of Scheduling, 12(3):227–256, jun 2009.
  * [44] Bruno De Backer, Vincent Furnon, Paul Shaw, Philip Kilby, and Patrick Prosser.  Solving vehicle routing problems using constraint programming and metaheuristics.  Journal of Heuristics, 6(4):501–523, sep 2000.
  * [45] Paul Shaw.  Using constraint programming and local search methods to solve vehicle routing problems.  In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 1520, pages 417–431. Springer Verlag, oct 1998.
  * [46] Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack.  MiniZinc: Towards a standard CP modelling language.  In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 4741 LNCS, pages 529–543. Springer Verlag, 2007.
  * [47] Mark Wallace.  Building Decision Support Systems.  Springer International Publishing, 2020.
  * [48] Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano.  MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library.  Mathematical Programming Computation, pages 1–48, jan 2021.
  * [49] Peter J. Stuckey, Ralph Becket, and Julien Fischer.  Philosophy of the MiniZinc challenge, jul 2010.
  * [50] Gerhard Reinelt.  TSPLIB. A traveling salesman problem library.  ORSA journal on computing, 3(4):376–384, nov 1991.
  * [51] World Wide Web Consortium et al.  Extensible markup language (xml) 1.1.  2006\.
  * [52] Henry S Thompson, Noah Mendelsohn, David Beech, and Murray Maloney.  W3c xml schema definition language (xsd) 1.1 part 1: Structures.  The World Wide Web Consortium (W3C), W3C Working Draft Dec, 3, 2009\.