mggdb_0.50
Here you find instance definitions and the best known upper and lower bounds (to our knowledge) for the 23 instances of the mggdb (ß=0.50) benchmark derived from the CARP by Bosco et al. [BLMV]. 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 mggdb_0.50 instance definitions can be found, as a zip-file here.

 

Best known results for the mggdb_0.50 benchmark

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

InstanceUpper Bound ReferenceLower BoundReferenceGAP(%)
mggdb_0.50_1* 214 BLMV 214 BLMV 0
mggdb_0.50_2* 269 BLMV 269 BLW 0
mggdb_0.50_3* 218 BLMV 218 BLMV 0
mggdb_0.50_4* 219 BLMV 219 BLMV 0
mggdb_0.50_5* 292 BLMV 292 BLMV 0
mggdb_0.50_6* 276 BLMV 276 BLMV 0
mggdb_0.50_7* 265 BLMV 265 BLMV 0
mggdb_0.50_8  310 DDHI 309  BLW 0.32
mggdb_0.50_9 265 DDHI 260 G 1.92
mggdb_0.50_10* 194 BLMV 194 BLMV 0
mggdb_0.50_11 275 BLMV 267 G 3.00
mggdb_0.50_12* 445 BLMV 445 BLMV 0
mggdb_0.50_13* 259 BLMV 259 G 0
mggdb_0.50_14* 75 BLMV 75 BLMV 0
mggdb_0.50_15* 37 BLMV 37 BLMV 0
mggdb_0.50_16* 66 BLMV 66 BLMV 0
mggdb_0.50_17* 53 BLMV 53 BLMV 0
mggdb_0.50_18 121 BLMV 117 G 3.42
mggdb_0.50_19* 44 BLMV 44 BLMV 0
mggdb_0.50_20* 81 BLMV 81 BLMV 0
mggdb_0.50_21* 86 BLMV  86 BLMV 0
mggdb_0.50_22* 123 DDHI 123  G 0
mggdb_0.50_23* 125 BLW 125  G 0
 

References

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.

Published June 22, 2012