BHW benchmark
Here you find instance definitions and the best known upper and lower bounds (to our knowledge) for the 20 instances of the BHW benchmark generated from popular benchmark instances for the CARP [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 BHW instance definitions can be found, as a zip-file here.

 

Best known results for the BHW benchmark

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

InstanceUpper Bound ReferenceLower BoundReferenceGAP(%)
BHW1* 337 HKSG 337 BLW 0
BHW2* 470 HKSG 470 BHW 0
BHW3* 415 HKSG 415 BLW 0
BHW4* 240 HKSG 240 BHW 0
BHW5* 502  DDHI 502 BHW 0
BHW6* 388  HKSG 388 BHW 0
BHW7 1070  DDHI 1047 BLW 2.2
BHW8 668  DDHI 665 BLW 0.5
BHW9 875  DDHI 858 BLW 2.0
BHW10 8524  DDHI 8310 BLW 2.6
BHW11 4914  DDHI 4690 BLW 4.8
BHW12 10887  DDHI 10605 BLW 2.7
BHW13 14346  DDHI 13952 BLW 2.8
BHW14 24833  DDHI 24377 BLW 1.9
BHW15 15354  DDHI 15130 BLW 1.5
BHW16 43948  DDHI 42506 BLW 3.4
BHW17 26235  DDHI 25570 BLW 2.6
BHW18 15170  DDHI 14840 BLW 2.2
BHW19 9388  DDHI 9197 BLW 2.1
BHW20 16291  DDHI 10730 BHW 51.8

 

* Optimal value, instance has been closed.

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.

BLW - L. Bach, J. Lysgaard, S. Wøhlk. A Branch-and-Cut-and-Price Algorithm for the Mixed Capacitated General Routing Problem. In L. Bach: Routing and Scheduling Problems – Optimization using Exact and Heuristic Methods. Ph.D. dissertation, School of Business and Social Sciences, Aarhus University, Denmark, 2014.

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.

G - K. A. Gaze, G. Hasle, C. Mannino. Column Generation for the Mixed Capacitated General Routing Problem. Talk at WARP 1 - First Workshop on Arc Routing Problems, Copenhagen May 22-24 2013.

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