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

 

Best known results for the mggdb_0.25 benchmark

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

InstanceUpper Bound ReferenceLower BoundReferenceGAP(%)
mggdb_0.25_1* 280 BLMV 280 BLMV 0
mggdb_0.25_2* 349 BLMV 349 BILV 0
mggdb_0.25_3* 278 BLMV 278 BLMV 0
mggdb_0.25_4* 289 BLMV 289 BLMV 0
mggdb_0.25_5* 394 BLMV 394 BLW 0
mggdb_0.25_6* 292 BLMV 292 BLMV 0
mggdb_0.25_7* 290 BLMV 290 BLMV 0
mggdb_0.25_8  336 DDHI 333 BLW 0.90
mggdb_0.25_9  309 DDHI 308 BLW 0.32
mggdb_0.25_10* 265 BLMV 265 BLMV 0
mggdb_0.25_11* 356 BLMV 356 BILV 0
mggdb_0.25_12* 459 BLMV 459 BLW 0
mggdb_0.25_13* 388 BLMV 388 G 0
mggdb_0.25_14* 107 BLMV 107 BLMV 0
mggdb_0.25_15* 55 BLMV 55 BLMV 0
mggdb_0.25_16* 98 BLMV 98 BLMV 0
mggdb_0.25_17* 71 BLMV 71 BLMV 0
mggdb_0.25_18* 144 BLMV 144 BILV 0
mggdb_0.25_19* 53 BLMV 53 BLMV 0
mggdb_0.25_20* 116 BLMV 116 BLMV 0
mggdb_0.25_21* 146 BLMV 146 BLMV 0
 mggdb_0.25_22* 160  DDHI 160 G 0
 mggdb_0.25_23* 181  DDHI 181 G 0
 

References

BILV - C. Bode, S. Irnich, D. Laganà, F. Vocaturo. Two-Phase Branch-and-Cut for the Mixed Capacitated General Routing Problem. Technical Report LM-2014-02, University of Mainz.

BLMV - A. Bosco, D. Laganà, 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. Gaze. Exact Optimization Methods for the Mixed Capacitated General Routing Problem. MSc Thesis NTNU, July 2013.

Published June 22, 2012