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

 

Best known results for the mgval_0.50 benchmark

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

InstanceUpper Bound ReferenceLower BoundReferenceGAP(%)
mgval_0.50_1A* 145 BLMV 145 BLMV 0
mgval_0.50_2A* 248 BLMV 248 BLMV 0
mgval_0.50_3A* 75 BLMV 75 BLMV 0
mgval_0.50_4A* 350 BLMV 350 BLMV 0
mgval_0.50_5A* 367 BLMV 367 BLMV 0
mgval_0.50_6A* 210 BLMV 210 BLMV 0
mgval_0.50_7A* 248 BLMV 248 BLMV 0
mgval_0.50_8A 388 BLMV 386 BLW 0.52
mgval_0.50_9A* 306 BLMV 306 BLMV 0
mgval_0.50_10A 385 BLMV 380 BLMV 1.26
mgval_0.50_1B* 170 BLMV 170 BLMV 0
mgval_0.50_2B* 284 BLMV 284 BLMV 0
mgval_0.50_3B* 107 BLMV 107 BLMV 0
mgval_0.50_4B 413 BLMV 396 BLMV 4.20
mgval_0.50_5B 378 BLMV 364 BLMV 3.71
mgval_0.50_6B* 210 BLMV 210 BLMV 0
mgval_0.50_7B* 276 BLMV 276 BLMV 0
mgval_0.50_8B 350 BLMV 334 BLMV 4.69
mgval_0.50_9B 278 BLMV 268 BLMV 3.54
mgval_0.50_10B 369 BLMV 364 BLMV 1.36
mgval_0.50_1C  261 BLMV2 253 BLW 3.16
mgval_0.50_2C 464 DDHI 453 BLW 4.41
mgval_0.50_3C* 137 BLMV 137 BLW 0
mgval_0.50_4C 488 BLMV 472 BLW 3.39
mgval_0.50_5C 457 DDHI 449 BLW 1.78
mgval_0.50_6C 293 DDHI 281 BLW 4.27
mgval_0.50_7C 320 DDHI 306 BLW 4.58
mgval_0.50_8C 501 DDHI 485 BLW 3.30
mgval_0.50_9C 292 BLMV 283 BLW 3.18
mgval_0.50_10C 406 BLMV 396 BLW 2.53
mgval_0.50_4D 580 DDHI 565 BLW 2.65
mgval_0.50_5D 541

DDHI

527

 BLW 2.66
mgval_0.50_9D 358 DDHI 349 BLW 2.58
mgval_0.50_10D 457 DDHI 436 BLW 4.82
 

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.

BLMV2 - A. Bosco, D. Lagana, R. Musmanno, and F. Vocaturo. A matheuristic algorithm for the mixed capacitated general routing problem. Networks, in press.

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