CBMix benchmark

Here you find instance definitions and the best known upper and lower bounds (to our knowledge) for the 23 instances of the CBMix benchmark created by Prins and Bouchenoua in 2004 [PB]. 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 CBMix instance definitions can be found, as a zip-file, here.

Best known results for the CBMix benchmark

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

Instance	Upper Bound	Reference	Lower Bound	Reference	GAP(%)
CBMix1	2569	BLW	2547	BLW	0.9
CBMix2	11749	DDHI	11487	BLW	2.3
CBMix3	3614	DDHI	3514	BLW	2.8
CBMix4	7483	DDHI	7300	BLW	2.5
CBMix5	4459	DDHI	4387	BLW	1.6
CBMix6	6969	DDHI	6738	BLW	3.4
CBMix7	9428	DDHI	9046	BLW	4.2
CBMix8	10338	DDHI	9976	BLW	3.6
CBMix9	3991	DDHI	3837	BLW	4.0
CBMix10	7525	DDHI	7343	BLW	2.5
CBMix11	4484	DDHI	4318	BLW	3.8
CBMix12*	3138	BLMV	3138	BHW	0
CBMix13	9037	DDHI	8681	BLW	4.1
CBMix14	8473	DDHI	8205	BLW	3.3
CBMix15	8221	DDHI	8013	BLW	2.6
CBMix16	8742	DDHI	8446	BLW	3.5
CBMix17	4034	DDHI	3943	BLW	2.3
CBMix18	7052	DDHI	6856	BLW	2.9
CBMix19	16155	DDHI	15628	BLW	3.4
CBMix20	4738	DDHI	4647	BLW	2.0
CBMix21	17875	DDHI	17295	BLW	3.4
CBMix22	1941	PB	1905	BLW	1.9
CBMix23*	780	PB	780	BLMV	0

* 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.

BLMV - A. Bosco, D. Lagana, R. Musmanno, and F. Vocaturo. Modeling and solving the mixed capacitated general routing problem. Optimization Letters (2012), pp 1-19, doi 10.1007/s11590-012-0552-y.

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).

KMK - H. Kokubugata, A. Moriyama and H. Kawashima, "A Practical Solution Using Simulated Annealing for General Routing Problems with Nodes, Edges, and Arcs", Japan, 2007

PB - C. Prins and S. Bouchenoua, "A Memetic Algorithm Solving VRP, the CARP and General Routing Problems with Nodes, Edges and Arcs", Recent advances in memetic algorithms, France, 2004

Published June 22, 2012