DI-NEARP benchmark
Here you find instance definitions and the best known solutions (to our knowledge) for the 24 instances of the DI-NEARP benchmark generated from six real life cases from the design of carrier routes for home delivery of subscription newspapers and other media products in the Nordic countries [BHW]. The values for the upper and lower bounds reported in the table only include traversal costs, i.e. service costs are omitted.  

Instance definitions (text)

The DI-NEARP instance definitions can be found, as a zip-file here.

 

Best known results for the DI-NEARP benchmark

For the Upper Bound values in blue, you get the detailed solution by clicking on the value.

InstanceUpper Bound ReferenceLower BoundReferenceGAP(%)
DI-NEARP-n240-Q2k 23807  DDHI 16376 BHW 45.4
DI-NEARP-n240-Q4k 18197  DDHI 14362 BHW 26.7
DI-NEARP-n240-Q8k 15884 DDHI 13442 BHW 18.2
DI-NEARP-n240-Q16k 14717 DDHI 13116 BHW 12.2
DI-NEARP-n422-Q2k 18943  DDHI 11623 BHW 63.0
DI-NEARP-n422-Q4k 15869  DDHI 11284 BHW 40.6
DI-NEARP-n422-Q8k 14442  DDHI 11220 BHW 28.7
DI-NEARP-n422-Q16k 14339  DDHI 11198 BHW 28.1
DI-NEARP-n442-Q2k 51052  DDHI 35068 BHW 45.6
DI-NEARP-n442-Q4k 44952  DDHI 33585 BHW 33.9
DI-NEARP-n442-Q8k 43264  DDHI 32985 BHW 31.2
DI-NEARP-n442-Q16k 42683  DDHI 32713 BHW 30.5
DI-NEARP-n477-Q2k 22896  DDHI 19722 BHW 16.1
DI-NEARP-n477-Q4k 20035  DDHI 18031 BHW 11.1
DI-NEARP-n477-Q8k 18490 DDHI 17193 BHW 7.5
DI-NEARP-n477-Q16k 18040  DDHI 16873 BHW 6.9
DI-NEARP-n699-Q2k 58948  DDHI 34101 BHW 72.9
DI-NEARP-n699-Q4k 40124  DDHI 26891 BHW 49.2
DI-NEARP-n699-Q8k 30799  DDHI 23302 BHW 32.2
DI-NEARP-n699-Q16k 26999  DDHI 21967 BHW 22.9
DI-NEARP-n833-Q2k 56102  DDHI 32435 BHW 73.0
DI-NEARP-n833-Q4k 41192  DDHI 29381 BHW 40.2
DI-NEARP-n833-Q8k 34812  DDHI 28453 BHW 22.4
DI-NEARP-n833-Q16k 32567  DDHI 28233 BHW 15.4
 

References

BHW - Lukas Bach, Geir Hasle, Sanne Wøhlk: A Lower Bound for the Node, Edge, and Arc Routing Problem. Computers & Operations Research 40 (2013) 943–952.

DDHI - M. Dell'Amico, J. C. Díaz Díaz, G. Hasle, M. Iori. An Adaptive Iterated Local Search for the Mixed Capacitated General Routing Problem. SINTEF Report A26278. 2014-05-16. ISBN 978-82-14-05361-6.

HKSG - G. Hasle, O. Kloster, M. Smedsrud and K. Gaze, "Experiments on the node, edge, and arc routing problem. ," Technical report A23265, SINTEF, May 2012. ISBN 978-82-14-05288-6 (444 KB).

Published June 22, 2012