 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.
\item
  \emph{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.
\end{itemize}

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

\begin{itemize}
\item
  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.
\item
  \emph{Hamiltonian cycle problem} -- a problem of testing whether a graph has a Hamiltonian cycle.
\item
  \emph{Sequential ordering problem} -- a restricted version of asymmetrical TSP with an additional set of \emph{precedence} restrictions requiring that for some locations A and B the route has to visit A before B.
\item
  \emph{Capacitated VRP}.
\end{itemize}

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:

\begin{itemize}
\item
  The type of problem is given by the line \texttt{TYPE\ :\ CVRP}.
\item
  The number of nodes is given by the line \texttt{DIMENSION\ :\ 6}, where 6 stands for the \emph{total} number of nodes.
\item
  The vehicle capacity is given by the line \texttt{CAPACITY\ :\ 100}.
\item
  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 \texttt{EDGE\_WEIGHT\_TYPE\ :\ GEO} and \texttt{NODE\_COORD\_TYPE\ :\ TWOD\_COORDINATES} (the latter used for specifying the latitude and longitude).
\end{itemize}

As for the data part, it is given by:

\begin{itemize}
\item
  The node locations are given in \texttt{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:

\begin{verbatim}
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
\end{verbatim}
\item
  The depot nodes are listed in section \texttt{DEPOT\_SECTION}; for example, we can specify that nodes 2 and 4 are depots as follows:

\begin{verbatim}
2
4
-1
\end{verbatim}
\item
  The demands of the remaining nodes are given in \texttt{DEMAND\_SECTION} (the depot demands also have to be filled in by zero values). In our example, this may look as follows:

\begin{verbatim}
1 50
2 0
3 70
4 0
5 30
6 60
\end{verbatim}
\end{itemize}

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

\begin{itemize}

\item
  TSPLIB gives a direct, unambiguous model for domain entities (albeit cluttered between file parts): this model is, in fact, explicitly stated in the specification.
\item
  TSPLIB allows switching between different domain models, even if the choices for that are rather restricted.
\item
  Last but not least, TSPLIB is \emph{tailored} for modeling VRP domains -- in particular, it contains vehicles and locations as \emph{native} constructs.
\end{itemize}

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

\begin{itemize}

\item
  \emph{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.
\item
  \emph{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.
\item
  \emph{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).
\end{itemize}

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.

\hypertarget{embedding-into-general-purpose-languages}{%
\subsection{Embedding into general-purpose languages}\label{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 \citep{Mendoza2014}, 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 \citep{world2006extensible} 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 \citep{thompson2009w3c} -- 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 \texttt{\textless{}instance\textgreater{}} containing the following children:

\begin{itemize}
\item
  The element \texttt{\textless{}info\textgreater{}} stores instance metadata -- the dataset name and the instance name.
\item
  The element \texttt{\textless{}network\textgreater{}} describes the nodes of the network and the links between nodes, which are given by child elements \texttt{\textless{}nodes\textgreater{}} and \texttt{\textless{}links\textgreater{}} respectively:

  \begin{itemize}
  
  \item
    The \texttt{\textless{}nodes\textgreater{}} element contains a collection of \texttt{\textless{}node\textgreater{}} 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:
  \end{itemize}

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{\textless{}}\KeywordTok{node}\OtherTok{ id=}\StringTok{"1"}\OtherTok{ type=}\StringTok{"1"}\NormalTok{\textgreater{}}
\NormalTok{  \textless{}}\KeywordTok{latitude}\NormalTok{\textgreater{}48.0\textless{}/}\KeywordTok{latitude}\NormalTok{\textgreater{}}
\NormalTok{  \textless{}}\KeywordTok{longitude}\NormalTok{\textgreater{}46.0\textless{}/}\KeywordTok{longitude}\NormalTok{\textgreater{}}
\NormalTok{\textless{}/}\KeywordTok{node}\NormalTok{\textgreater{}}
\end{Highlighting}
\end{Shaded}

  \begin{itemize}
  
  \item
    The \texttt{\textless{}links\textgreater{}} element contains a collection of \texttt{\textless{}link\textgreater{}} 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