mggdb_0.40
Here you find instance definitions and the best known upper and lower bounds (to our knowledge) for the 23 instances of the mggdb (ß=0.40) 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.40 instance definitions can be found, as a zip-file here.

 

Best known results for the mggdb_0.40 benchmark

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

InstanceUpper Bound ReferenceLower BoundReferenceGAP(%)
mggdb_0.40_1* 279 BLMV 279 BLMV 0
mggdb_0.40_2* 308 BLMV 308 BLW 0
mggdb_0.40_3* 225 BLMV 225 BLMV 0
mggdb_0.40_4* 238 BLMV 238 BLMV 0
mggdb_0.40_5 344 BLMV 344 BLW 0
mggdb_0.40_6* 270 BLMV 270 BLMV 0
mggdb_0.40_7* 282 BLMV 282 BLMV 0
mggdb_0.40_8 331 DDHI 326 BLW 1.53
mggdb_0.40_9 275 DDHI  273 BLW 0.73
mggdb_0.40_10* 191 BLMV 191 BLMV 0
mggdb_0.40_11 283 BLMV 277 G 2.17
mggdb_0.40_12* 412 BLMV 412 BLMV 0
mggdb_0.40_13* 405 BLMV 405 BLW 0
mggdb_0.40_14* 62 BLMV 62 BLMV 0
mggdb_0.40_15* 37 BLMV 37 BLMV 0
mggdb_0.40_16* 84 BLMV 84 BLMV 0
mggdb_0.40_17* 65 BLMV 65 BLMV 0
mggdb_0.40_18* 119 BLMV 119 BLMV 0
mggdb_0.40_19* 38 BLMV 38 BLMV 0
mggdb_0.40_20* 94 BLMV 94 BLMV 0
mggdb_0.40_21* 104 BLMV  104 BLMV 0
 mggdb_0.40_22* 129 G 129   G 0
 mggdb_0.40_23* 160 DDHI 160   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