LIBRARY OF ARP INSTANCES
Dmitry Krushinsky 
Eindhoven, 2013-2014


CONTENTS
  I Introduction
     1. Networks with nested structure
     2. Rectangular grids
     3. Real road networks
     4. Networks from the literature
 II File formats
     5. Text data
     6. Graphical data
III References




I Introduction

This library contains several classes of benchmark instances 
for the arc routing problems (ARPs).


1. Networks with a nested structure.
These graphs were obtained (from a graph containing a single edge) by iteratively 
picking a random edge and replacing it with one of the predefined subgraphs (random choice), 
scaled and rotated appropriately.

The instances of this class have titles 't01'...'t20', where the number corresponds to the 
number of vertices divided by 10, i.e. 't01' has 10 vertices, 't15' - 150 vertices. These instances 
can be found in '\art' subdirectory.


2. Rectangular grids
These graphs vere obtained from a rectangular grid by deleting randomly chosen arcs, 
and then refined to ensure strong connectivity. Further, linear fragments (line subgraphs) 
were aggregated to single arcs.

This class includes instances 'R10x6' ... 'R40x23', where the numbers indicate the size of 
the original grid, i.e. 'R10x6' is derived from a 10x6 grid with 60 vertices. Note that 
during the processing some vertices are deleted, so the actual number of vertices in an 
instance is less than the corresponding product. These instances can be found in '\art'
subdirectory.


3. Real road networks
These graphs are derived from real road networks (based on data from the Open Street Map [1]).
There is no specific reason for choosing these particular locations. Many of them I have 
visited, others are otherwise known (e.g., I could not but include some representatives 
of US cities famous for their rectangular patterns). Probably, the only common feature of 
all the instances is that they remain visually attractive (this is subjective, of course) 
after fancy curves of the real roads are replaced by simplified arcs. Note that the weights 
of the arcs correspond to real distances (rounded to metres) and the coordinates of vertices 
correspond to real coordinates of special points (intersections or substantial bends of roads). 
These coordinates were first mapped using spherical Mercator projection from lat/lon to 
2D Cartesian coordinates and then scaled (and, sometimes, rotated) so that all x-coordinates 
fit in [-1;1]). The demands at arcs are equal to their weights on all arcs except those 
corresponding to highways and motorways (zero demand).

The instances are stored in files with the following naming convention "<title>[<numerical index>].txt",
where <title> is the title of a network (reflecting its placement, see below), optional <numerical index> 
is used to distinguish instances derived from the same network, mainly by contracting arcs with small 
weights. Instances without the index represent the most detailed data about the network, usually too 
detailed for any reasonable use, that is why instances with index 1 are a good starting point. Further, 
the higher the index, the fewer details are present and the smaller the problem size. These instances 
can be found in '\map' subdirectory.  

The list of instance titles and references to their geographic origin:
=========================================================
title   place                           approx. lat/lon
------  ------------------------------  -----------------
brookA  Brooklyn (US)                   40.62 /-73.93
brookB                                  40.62 /-73.93
chicA   Chicago (US)                    41.88 /-87.63
chicB                                   41.70 /-87.74
chicC                                   41.74 /-87.78
cord    Cordes (BE)                     50.68 /  3.53
dach    Dachne (UA)                     44.88 / 34.99
gron    Groningen (NL)                  53.21 /  6.56
kyivA   Kyiv (UA)                       50.46 / 30.36
kyivB                                   50.50 / 30.40
kyivC                                   50.51 / 30.49
kyivD                                   50.46 / 30.50
mons    Mons (BE)                       50.45 /  3.95
nyA     New York (US)                   40.75 /-73.97
nyB                                     40.73 /-74.00
nyC                                     40.74 /-74.00
romeA   Rome (IT)                       41.89 / 12.47
romeB                                   41.86 / 12.48
tour    Tournai (BE)                    50.60 /  3.39
tue     TU/e campus (Eindhoven, NL)     51.44 /  5.49
vdnipr  Verhnjodniprovsk (UA)           48.65 / 34.33
vepr    Vepryk (UA)                     50.10 / 29.80
vypas   Vypasne (UA)                    46.20 / 30.26
=========================================================

4. Networks from the literature
This class includes some instances proposed by Li and Eglese [2,3] and Benavent et al. [4] 
(also available at http://www.uv.es/belengue/carp.html). We have replaced each edge by two opposite 
arcs, converted the data from the original format to ours and generated a visual representation. The 
visual representations are generated automatically in such a way that arc weights are approximately 
proportional to the Euclidean distances between their endpoints and the number of arcs intersections 
is minimal. Thus, the generated pictures may substantially differ from the original networks.

Original filenames are preserved. These instances can be found in '\lit' subdirectory.



II File formats 

The file names obey the following convention. Instances are stored in files <title>.txt and 
their graphical representations - <title>.ps, where <title> is the title of the instance.
Note that the graphical representation serves purely for illustrative purposes, the actual
arc weights and demands cannot be derived from it.  

5. Text data
The file has the following format:

=====================================================
nodes:=DATA{0..<|V|-1>};
routes:=DATA{0..<|K|-1>};
C:=<C>;

COMPOSITE TABLE
     i     j          d          w
!----- ----- ---------- ----------
 <arc data: 
origin destination demand    weight, e.g.:>
     0     8          3          7
    49    48          2          8
;

COMPOSITE TABLE
     i         cx         cy
!----- ---------- ----------
<vertex data (needed only for visualisation):
 index    x-coord    y-coord , e.g.: >
     0   0.318996  -0.206561
    49  -0.652494   0.366235
;

where 
|V| - number of vertices, 
|K| - number of routes (vehicles), 
 C  - capacity of a route (vehicle).
=====================================================

This format is directly supported by AIMMS [5], and can be easily converted 
to any other format, if needed.


6. Graphical data
Graphical representations of the instances are stored in PostScript [6] format.
A PS viewer is needed to open the files (e.g. GSView [7]). The advantage over 'static' 
formats (like PDF or JPEG) is that one may adjust the representation to his needs by 
changing some parameters within the file. Note that PS files can be edited in any text 
editor, but certain knowledge of PS scripting language is needed to reach the goal. 
In particular, the following parameters can be changed as needed:
    /node_unit 10 def %controls the size of the nodes
    /arc_curv  0.1 def %arc curvature, 0 - straight line
The numbers of nodes and all/required arcs are provided in the left upper corner; 
arcs with zero demand (non-required) are shown as dashed lines.

Note: the arcs are drawn without arrows for the sake of visibility. Yet, their orientation 
can be unambiguously determined using either of the following equivalent rules 
(see arc_orientation.png for a visual representation):
1. right-hand rule:
    - put your right hand on a sheet, the palm facing you;
    - set your thumb perpendicular to the fingers;
    - when your fingers point the direction of the bend, the thumb points the direction 
      of the arc.
2. clockwise rule:
    - consider the arc as a fragment of some circle;
    - the clockwise traversal of the circle gives the orientation of the arc.
A self-check: ( is directed upwards.



III References

[1] Open Street Map, www.openstreetmap.org
[2] L.Y.O. Li (1992). Vehicle Routeing for Winter Gritting. Ph.D. Thesis, Dept. of Management Science, Lancaster University.
[3] L.Y.O. Li, R.W. Eglese (1996). An Interactive Algorithm for Vehicle Routeing for Winter-Gritting. Journal of the Operational Research Society 47, p. 217-228.
[4] E. Benavent, V. Campos, A. Corberan and E. Mota (1992). The Capacitated Chinese Postman Problem: Lower Bounds. Networks 22 (7), p. 669-690.
[5] AIMMS modelling environment, www.aimms.com
[6] PostScript language reference, https://www.adobe.com/products/postscript/pdfs/PLRM.pdf
[7] GSView - a PostScript viewer, http://www.ghostscript.com/GSview.html

