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

 

Best known results for the mggdb_0.45 benchmark

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

InstanceUpper Bound ReferenceLower BoundReferenceGAP(%)
mggdb_0.45_1* 259 BLMV 259 BLMV 0
mggdb_0.45_2* 298 BLMV 298 BLW 0
mggdb_0.45_3* 237 BLMV 237 BLMV 0
mggdb_0.45_4* 228 BLMV 228 BLMV 0
mggdb_0.45_5* 350 BLMV 350 BLW 0
mggdb_0.45_6* 218 BLMV 218 BLMV 0
mggdb_0.45_7* 243 BLMV 243 BLMV 0
mggdb_0.45_8* 296 DDHI 296 G 0
mggdb_0.45_9* 277 DDHI 277 BLW 0
mggdb_0.45_10* 214 BLMV 214 BLMV 0
mggdb_0.45_11 297 BLMV 289 BLW 2.77
mggdb_0.45_12* 393 BLMV 393 BLW 0
mggdb_0.45_13* 423 DDHI 423 BLW 0
mggdb_0.45_14* 66 BLMV 66 BLMV 0
mggdb_0.45_15* 34 BLMV 34 BLMV 0
mggdb_0.45_16* 70 BLMV 70 BLMV 0
mggdb_0.45_17* 53 BLMV 53 BLMV 0
mggdb_0.45_18 123 BLMV 121 BLW 1.65
mggdb_0.45_19* 48 BLMV 48 BLMV 0
mggdb_0.45_20* 78 BLMV 78 BLMV 0
mggdb_0.45_21* 122 BLMV  122 BLMV 0
mggdb_0.45_22* 136 DDHI  136 BLW 0
mggdb_0.45_23* 144 BLW  144 BLW 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