Benchmarks

Split Delivery Vehicle Routing Problem with Time Windows

The working paper

N. Bianchessi, M.Drexl, S. Irnich (2017). The Split Delivery Vehicle Routing Problem with Time Windows and
Customer Inconvenience Constraints. Technical report LM-2017-02, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Mainz, Germany.

uses 560 new benchmark instances that are generated similar to Solomon's instances, but with different demand scenarios.

Zip file with instances.

 

Capacitated Arc Routing Problem (CARP)

Lower and upper bound values and integer solutions for CARP benchmark instances are listed below. 

 

KSHS Instances

The KSHS instances were introduced in:

M. Kiuchi, Y. Shinano, R. Hirabayashi and Y. Saruwatari (1995). An exact algorithm for the Capacitated Arc Routing Problem using Parallel Branch and Bound method. Abstracts of the 1995 Spring National Conference of the Oper. Res. Soc. of Japan, 28-29.

 

Zip file with instances as provided by José Manuel Belenguer and Enrique Benavent's website (see also format file).

  Lower Bounds Upper Bounds Integer Solutions
Instances Belenguer Benavent 2003 Longo et al. 2006 best known LB best known UB Beullens et al. 2003 (modified costs) Optimal Solution Longo et al. 2006
kshs1 14661 14661 14661 14661 14661 14661 14661
kshs2 9863 9863 9863 9863 9863 9863 9863
kshs3 9320 9320 9320 9320 9320 9320 9320
kshs4 11098 11498 11498 11498 11498 11498 11498
kshs5 10957 10957 10957 10957 10957 10957 10957
kshs6 10197 10197 10197 10197 10197 10197 10197

GDB Instances

The GDB instances were introduced in:

B.L. Golden, J.S. DeArmon and E.K. Baker (1983). Computational Experiments with Algorithms for a Class of Routing Problems. Computers & Operations Research 10 (1), 47-59.

Zip file with instances as provided by José Manuel Belenguer and Enrique Benavent's website (see also format file).

  Lower Bounds Upper Bounds Integer Solutions
Instances Belenguer Benavent 2003 Longo et al. 2006 best known LB best known UB Pearn 1989 Hertz et al. 2000 Lacomme et al. 2001* Beullens et al. 2003 (modified costs) Optimal Solution Longo et al. 2006
gdb1 316 316 316 316 316 316 316 316 316 316
gdb2 339 339 339 339 345 339 339 339 339 339
gdb3 275 275 275 275 275 275 275 275 275 275
gdb4 287 287 287 287 287 287 287 287 287 287
gdb5 377 377 377 377 383 377 377 377 377 377
gdb6 298 298 298 298 315 298 298 298 298 298
gdb7 325 325 325 325 325 325 325 325 325 325
gdb8 344 348 348 348 356 352 348 348 348 348
gdb9 303 303 303 303 339 317 303 303 303 303
gdb10 275 275 275 275 275 275 275 275 275 275
gdb11 395 395 395 395 406 395 395 395 395 395
gdb12 450 458 458 458 560 458 458 456 458 458
gdb13 536 536 536 536 554 544 538 536 536 536
gdb14 100 100 100 100 100 100 100 100 100 100
gdb15 58 58 58 58 58 58 58 58 58 58
gdb16 127 127 127 127 127 127 127 127 127 127
gdb17 91 91 91 91 91 91 91 91 91 91
gdb18 164 164 164 164 164 164 164 164 164 164
gdb19 55 55 55 55 55 55 55 55 55 55
gdb20 121 121 121 121 123 121 121 121 121 121
gdb21 156 156 156 156 156 156 156 156 156 156
gdb22 200 200 200 200 200 200 200 200 200 200
gdb23 233 233 233 233 233 235 235 233 233 233

BBCM Instances a.k.a. VAL Instances

The BBCM instances were introduced in:

E. Benavent, V. Campos, A. Corberán and E. Mota (1992). The Capacitated Chinese Postman Problem: Lower Bounds. Networks 22 (7), 669-690.

Zip file with instances as provided by José Manuel Belenguer and Enrique Benavent's website (see also format file).

  Lower Bounds Upper Bounds Integer Solutions
Instances Benavent et al. 1992 Belenguer Benavent 2003 Longo et al. 2006 (LB at root node) Longo et al. 2006 Baldacci Maniezzo 2006 Bartolini et al. 2012 Bartolini et al. 2012 (end of GenRoute) Bode Irnich 2012 (LB at root node) Bode Irnich 2012 best known LB best known UB Hertz et al. 2000 Lacomme et al. 2001* Beullens et al. 2003 (modified costs) Lacomme et al. 2004 Polacek et al. 2008 Brandao Eglese 2008 Offset Optimal Solution Longo et al. 2006 Baldacci Maniezzo 2006 Bartolini et al. 2012 Bode Irnich 2012
1A 247 247 247     247 247 247 247 247 247 173 173 173 173 173 173 74 247     247 247
1B 247 247 247     247 247 247 247 247 247 173 173 173 173 173 173 74 247     247 247
1C   309 312 319 319 314 314 314 319 319 319 245 245 245 245 245 245 74 319 319 319 319 319
2A 297 298 298     298 298 298 298 298 298 227 227 227 227 227 227 71 298     298 298
2B 318 330 329 330   330 330 329 330 330 330 260 259 259 259 259 259 71 330 330   330 330
2C   526 528 528 528 528 528 528 528 528 528 457 457 457 457 457 457 71 528 528 528 528 528
3A 103 105 105     105 105 105 105 105 105 81 81 81 81 81 81 24 105     105 105
3B 108 111 111     111 111 111 111 111 111 87 87 87 87 87 87 24 111     111 111
3C   161 161 162 162 162 162 161 162 162 162 138 138 138 138 138 138 24 162 162 162 162 162
4A 516 522 522     522 522 522 522 522 522 400 400 400 400 400 400 122 522     522 522
4B 522 534 534     534 534 534 534 534 534 412 412 412 412 412 412 122 534     534 534
4C 528 550 550     550 550 550 550 550 550 430 428 428 428 428 428 122 550     550 550
4D   644 648     649 649 647 650 650 652 546 530 530 530 530 530 122 650       650
5A 562 566 566     566 566 566 566 566 566 423 423 423 423 423 423 143 566     566 566
5B 580 589 588     588 588 587 589 589 589 446 446 446 446 446 446 143 589       589
5C 598 612 613     613 613 613 617 617 617 474 474 474 474 474 474 143 617       617
5D   714 716     717 718 715 718 718 718 593 581 583 581 575 577 143 718     718 718
6A 330 330 330     330 330 330 330 330 330 223 223 223 223 223 223 107 330     330 330
6B 336 338 337   340 337 337 336 340 340 340 241 233 233 233 233 233 107 340   340   340
6C   418 420   424 421 424 418 424 424 424 317 317 317 317 317 317 107 424   424 424 424
7A 382 382 382     382 382 382 382 382 382 279 279 279 279 279 279 103 382     382  
7B 382 386 386     386 386 386 386 386 386 283 283 283 283 283 283 103 386     386 386
7C   436 436 437 437 437 437 432 434 437 437 334 334 334 334 334 334 103 437 437 437 437  
8A 522 522 522     522 522 522 522 522 522 386 386 386 386 386 386 136 522     522 522
8B 531 531 531     531 531 531 531 531 531 395 395 395 395 395 395 136 531     531 531
8C   653 654     655 657 653 657 657 657 528 527 523 527 521 521 136 657     657 657
9A 450 450 450     450 450 450 450 450 450 323 323 323 323 323 2323 127 450     450 450
9B 453 453 453     453 453 453 453 453 453 326 326 326 326 326 326 127 453     453 453
9C 459 459 459     459 459 459 459 459 459 332 332 332 332 332 332 127 459     459 459
9D   509 512     512 512 510 515 515 516 399 391 391 391 389 391 127 515       515
10A 637 637 637     637 637 637 637 637 637 428 428 428 428 428 428 209 637     637 637
10B 645 645 645     645 645 645 645 645 645 436 436 436 436 436 436 209 645     645 645
10C 653 655 655     655 655 655 655 655 655 451 446 446 446 446 446 209 655     655 655
10D   732 734     734 734 734 734 734 734 536 530 529 528 525 528 209 734     734 734

EGL Instances

The EGL instances were introduced in:

L.Y.O. Li (1992). Vehicle Routeing for Winter Gritting. Ph.D. Thesis, Dept. of Management Science, Lancaster University. 

L.Y.O. Li and R.W. Eglese (1996). An Interactive Algorithm for Vehicle Routeing for Winter-Gritting. Journal of the Operational Research Society 47, 217-228.

Zip file with instances as provided by the José Manuel Belenguer and Enrique Benavent's website (see also format file).

  Lower Bounds Upper Bounds Integer Solutions
Instances Belenguer Benavent 2003 Ahr 2004 Longo et al. 2006 (LB at root node) Longo et al. 2006 Baldacci Maniezzo 2006 Martinelli et al. 2011a Bartolini et al. 2012 Bartolini et al. 2012 (end of GenRoute) Bode Irnich 2012 (LB at root node) Bode Irnich 2012 Bode Irnich 2013 Bode Irnich 2012b
(revised)
best known LB best known UB Lacomme et al. 2001* Lacomme et al. 2004 Polacek et al. 2008 Brandao Eglese 2008 Tang et al. 2009 Mei et al. 2009 Santos et al. 2010 Fu et al. 2010 Bartolini et al. 2012 (best known from literature or own ub) Bode Irnich 2012b
(revised)
Optimal Solution Longo et al. 2006 Baldacci Maniezzo 2006 Bartolini et al. 2012 Bode Irnich 2012 Bode Irnich 2012b (revised)
egl-e1-a 3515 3516 3548 3548   3548 3548 3548 3545 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548 3548   3548 3548 3548
egl-e1-b 4436 4436 4468   4498 4487 4487 4498 4464 4498 4498 4498 4498 4498 4498 4498 4498 4498 4498 4498 4498 4498 4498 4498 4498   4498 4498 4498 4498
egl-e1-c 5453 5481 5542     5537 5580 5595 5523 5545 5555 5573 5595 5595 5595 5595 5595 5595 5595 5595 5595 5595 5595   5595     5595    
egl-e2-a 4994 4963 5011   5018 5012 5012 5012 4996 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018   5018   5018 5018
egl-e2-b 6249 6271 6280     6291 6284 6284 6273 6301 6306 6317 6317 6317 6340 6340 6317 6317 6317 6317 6317 6317 6317 6317           6317
egl-e2-c 8114 8155 8234     8274 8319 8335 8202 8244 8303 8319 8335 8335 8415 8395 8335 8335 8335 8335 8335 8335 8335   8335     8335    
egl-e3-a 5869 5866 5898 5898   5898 5898 5898 4894 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898 5898   5898 5898 5898
egl-e3-b 7646 7649 7697     7715 7711 7711 7684 7728 7735 7744 7744 7775 7822 7816 7775 7777 7775 7787 7775 7775 7775              
egl-e3-c 10019 10119 10163     10207 10244 10244 10145 10191 10226 10236 10244 10292 10433 10369 10292 10305 10292 10305 10292 10292 10292              
egl-e4-a 6372 6378 6395     6395 6395 6395 6389 6408 6408 6408 6408 6444 6461 6461 6446 6456 6456 6461 6444 6444 6444              
egl-e4-b 8809 8839 8884     8893 8935 8935 8852 8892 8900 8919 8935 8961 9021 9021 8996 9000 8998 9026 8983 8962 8961              
egl-e4-c 11276 11376 11427     11471 11493 11493 11411 11457 11502 11512 11512 11550 11779 11779 11618 11601 11561 11598 11596 11550 11562 11529            
egl-s1-a 4992   5014   5018 5014 5018 5018 5011 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018 5018   5018 5018 5018 5018
egl-s1-b 6201   6379     6388 6388 6388 6370 6388 6388 6388 6388 6388 6435 6435 6388 6388 6388 6394 6388 6388 6388 6388 6388     6388   6388
egl-s1-c 8310   8480     8494 8517 8518 8418 8441 8500 8509 8518 8518 8518 8518 8518 8518 8518 8518 8518 8518 8518   8518     8518    
egl-s2-a 9780   9824     9807 9825 9825 9791 9803 9806 9812 9825 9884 9995 9995 9895 9956 9895 9970 9884 9889 9884              
egl-s2-b 12286   12968     12970 13017 13017 12949 12970 12982 12994 13017 13100 13174 13174 13100 13165 13147 13345 13115 13101 13100              
egl-s2-c 16221   16353     16357 16407 16425 16314 16352 16380 16393 16425 16425 16795 16715 16425 16505 16430 16600 16429 16430 16425   16425     16425    
egl-s3-a 10025   10143     10146 10145 10145 10143 10160 10160 10165 10165 10220 10296 10296 10221 10260 10257 10284 10220 10227 10220              
egl-s3-b 13554   13616     13623 13648 13648 13598 13631 13630 13644 13648 13682 14053 14028 13682 13807 13749 13857 13707 13695 13682              
egl-s3-c 16969   17100     17115 17163 17188 17058 17097 17125 17143 17188 17188 17297 17297 17259 17234 17207 17316 17230 17194 17188   17188     17188    
egl-s4-a 12027   12143     12140 12141 12141 12126 12149 12149 12153 12153 12268 12442 12442 12292 12341 12341 12348 12268 12297 12268              
egl-s4-b 15933   16093     16082 16098 16098 16066 16105 16106 16113 16113 16283 16531 16531 16321 16442 16337 16442 16336 16283 16321              
egl-s4-c 20179   20375     20380 20430 20430 20340 20376 20406 20423 20430 20481 20832 20832 20582 20591 20538 20821 20517 20521 20481              

EGL-Large Instances

The EGL-Large instances were introduced in:

Brandão, J., R. Eglese. (2008). A deterministic tabu search algorithm for the capacitated arc routing problem. Computers & Operations Research 35 (4) 1112-1126.

Zip file with instances as provided by Marcus Poggi de Aragão. We have transformed the instances into the standard format (see also format file).

  Lower Bounds Upper Bounds Integer Solutions
Instances Martinelli et al. 2011b Bode Irnich 2012b best known LB best known UB Brandao Eglese 2008 Mei et al. 2009 Martinelli et al. 2011a Optimal Solution
egl-g1-a 970495 976907 976907 1004864 1049708 1025765 1004864  
egl-g1-b 1085097 1093884 1093884 1129937 1140692 1135873 1129937  
egl-g1-c 1201030 1212151 1212151 1262888 1282270 1271894 1262888  
egl-g1-d 1325317 1341918 1341918 1398958 1420126 1402433 1398958  
egl-g1-e 1461469 1482176 1482176 1543804 1583133 1558548 1543804  
egl-g2-a 1061103 1069536 1069536 1115339 1129229 1125602 1115339  
egl-g2-b 1173286 1185221 1185221 1226645 1255907 1242542 1226645  
egl-g2-c 1295036 1311339 1311339 1371004 1418145 1401583 1371004  
egl-g2-d 1430267 1446680 1446680 1509990 1516103 1516072 1509990  
egl-g2-e 1557159 1581459 1581459 1659217 1701681 1668348 1659217  

BMCV Instances

The BMCV instances were introduced in:

Beullens, P., L. Muyldermans, D. Cattrysse, D. Van Oudheusden. (2003). A guided local search heuristic for the capacitated arc routing problem. European Journal of Operations Research 147(3) 629-643.

Zip file with instances as provided by Luc Muyldermans. We have transformed the instances into the standard format (see also format file).

  Lower Bounds Upper Bounds Integer Solutions
Instances Beullens et al. 2003 (modified costs) Bartolini et al. 2012 Bartolini et al. 2012 (end of GenRoute) Bartolini et al. 2012 (end of GenRoute) round to multiple of 5 Bode Irnich 2013 Bode Irnich 2012b (revised) Bode Irnich 2012b (rev.) round to multiple of 5 best known LB best known UB Beullens et al. 2003 Brandao Eglese 2008 Tang et al. 2009 Mei et al. 2009 Santos et al. 2010 Bartolini et al. 2012 (best known from literature or own ub) Offset Optimal Solution Bartolini et al. 2012 Bode Irnich 2013 Bode Irnich 2012b
(revised)
C1 4080 4105 4105 4105 4144 4145 4145 4145 4150 1660 1660 1660 1660 1660 4150 2490 4150     4150
C2 3135 3135 3135 3135 3135 3135 3135 3135 3135 1095 1095 1095 1095 1095 3135 2040 3135 3135 3135 3135
C3 2525 2567 2575 2575 2575 2575 2575 2575 2575 925 925 925 925 925 2575 1650 2575 2575 2575 2575
C4 3455 3478 3478 3480 3510 3510 3510 3510 3510 1340 1340 1340 1340 1340 3510 2170 3510   3510 3510
C5 5305 5365 5365 5365 5365 5365 5365 5365 5365 2475 2470 2470 2470 2470 5365 2895 5365 5365 5365 5365
C6 2495 2532 2535 2535 2535 2535 2535 2535 2535 895 895 895 895 895 2535 1640 2535 2535 2535 2535
C7 4015 4063 4075 4075 4075 4075 4075 4075 4075 1795 1795 1795 1795 1795 4075 2280 4075 4075 4075 4075
C8 4000 4083 4090 4090 4090 4090 4090 4090 4090 1730 1730 1730 1730 1730 4090 2360 4090 4090 4090 4090
C9 5215 5233 5233 5235 5244 5245 5245 5245 5260 1825 1820 1820 1830 1830 5260 3440        
C10 4620 4660 4700 4700 4700 4700 4700 4700 4700 2290 2270 2270 2270 2270 4700 2430 4700 4700 4700 4700
C11 4550 4583 4583 4585 4608 4617 4620 4615 4630 1815 1815 1815 1805 1810 4635 2825        
C12 4140 4209 4209 4210 4234 4239 4240 4235 4240 1610 1610 1610 1610 1610 4240 2630 4240     4240
C13 2895 2940 2955 2955 2955 2955 2955 2955 2955 1110 1110 1110 1110 1110 2955 1845 2955 2955 2955 2955
C14 3970 4030 4030 4030 4024 4030 4030 4030 4030 1680 1680 1680 1680 1680 4030 2350 4030 4030   4030
C15 4845 4912 4912 4915 4918 4923 4925 4920 4940 1860 1860 1860 1860 1860 4940 3080        
C16 1470 1475 1475 1475 1475 1475 1475 1475 1475 585 585 585 585 585 1475 890 1475 1475 1475 1475
C17 3535 3555 3555 3555 3555 3555 3555 3555 3555 1610 1610 1610 1610 1610 3555 1945 3555 3555 3555 3555
C18 5550 5577 5577 5580 5570 5570 5570 5580 5620 2410 2410 2390 2425 2385 5620 3235        
C19 3065 3096 3096 3100 3115 3115 3115 3115 3115 1395 1395 1395 1395 1395 3115 1720 3115   3115 3115
C20 2120 2120 2120 2120 2120 2120 2120 2120 2120 665 665 665 665 665 2120 1455 2120 2120 2120 2120
C21 3950 3960 3960 3960 3970 3970 3970 3970 3970 1725 1725 1725 1725 1725 3970 2245 3970   3970 3970
C22 2245 2245 2245 2245 2245 2245 2245 2245 2245 1070 1070 1070 1070 1070 2245 1175 2245 2245 2245 2245
C23 4015 4032 4032 4035 4073 4078 4080 4075 4085 1690 1700 1690 1700 1690 4085 2395        
C24 3370 3384 3384 3385 3400 3400 3400 3400 3400 1360 1360 1360 1360 1360 3400 2040 3400   3400 3400
C25 2310 2310 2310 2310 2310 2310 2310 2310 2310 905 905 905 905 905 2310 1405 2310 2310 2310 2310
D1 3215 3215 3215 3215 3215 3215 3215 3215 3215 725 740 745 740 725 3215 2490 3215 3215 3215 3215
D2 2520 2520 2520 2520 2520 2520 2520 2520 2520 480 480 480 480 480 2520 2040 2520 2520 2520 2520
D3 2065 2065 2065 2065 2065 2065 2065 2065 2065 415 415 415 415 415 2065 1650 2065 2065 2065 2065
D4 2785 2785 2785 2785 2785 2785 2785 2785 2785 615 615 615 615 615 2785 2170 2785 2785 2785 2785
D5 3935 3935 3935 3935 3935 3935 3935 3935 3935 1040 1040 1040 1040 1040 3935 2895 3935 3935 3935 3935
D6 2125 2125 2125 2125 2125 2125 2125 2125 2125 485 485 485 485 485 2125 1640 2125 2125 2125 2125
D7 3015 3078 3115 3115 3108 3108 3110 3115 3115 835 835 835 835 845 3115 2280 3115 3115    
D8 2975 2995 2995 2995 3045 3045 3045 3045 3045 685 685 685 685 685 3045 2360 3045   3045 3045
D9 4120 4120 4120 4120 4120 4120 4120 4120 4120 680 680 680 680 680 4120 3440 4120 4120 4120 4120
D10 3330 3335 3340 3340 3340 3340 3340 3340 3340 910 910 910 910 910 3340 2430 3340 3340 3340 3340
D11 3745 3745 3745 3745 3745 3745 3745 3745 3745 930 940 920 930 920 3745 2825 3745 3745 3745 3745
D12 3310 3310 3310 3310 3310 3310 3310 3310 3310 680 680 680 680 680 3310 2630 3310 3310 3310 3310
D13 2535 2535 2535 2535 2535 2535 2535 2535 2535 690 690 690 690 690 2535 1845 2535 2535 2535 2535
D14 3270 3272 3272 3275 3280 3280 3280 3280 3280 930 930 930 930 930 3280 2350 3280   3280 3280
D15 3990 3990 3990 3990 3990 3990 3990 3990 3990 910 950 910 920 910 3990 3080 3990 3990 3990 3990
D16 1060 1060 1060 1060 1060 1060 1060 1060 1060 170 170 170 170 170 1060 890 1060 1060 1060 1060
D17 2620 2620 2620 2620 2620 2620 2620 2620 2620 675 675 675 675 675 2620 1945 2620 2620 2620 2620
D18 4165 4165 4165 4165 4165 4165 4165 4165 4165 930 930 930 950 930 4165 3235 4165 4165 4165 4165
D19 2370 2393 2393 2395 2400 2400 2400 2400 2400 680 680 680 680 680 2400 1720 2400   2400 2400
D20 1870 1870 1870 1870 1870 1870 1870 1870 1870 415 415 415 415 415 1870 1455 1870 1870 1870 1870
D21 2940 2985 2985 2985 3005 3011 3015 3005 3050 805 815 810 810 805 3050 2245        
D22 1865 1865 1865 1865 1865 1865 1865 1865 1865 690 690 690 690 690 1865 1175 1865 1865 1865 1865
D23 3110 3114 3114 3115 3126 3126 3130 3130 3130 735 735 735 735 735 3130 2395        
D24 2660 2676 2676 2680 2704 2710 2710 2705 2710 670 670 670 670 670 2710 2040 2710     2710
D25 1815 1815 1815 1815 1815 1815 1815 1815 1815 410 410 410 410 410 1815 1405 1815 1815 1815 1815
E1 4830 4885 4885 4885 4898 4903 4905 4900 4910 1940 1935 1935 1935 1935 4910 2975        
E2 3960 3978 3990 3990 3990 3990 3990 3990 3990 1610 1610 1610 1610 1610 3990 2380 3990 3990 3990 3990
E3 2015 2015 2015 2015 2015 2015 2015 2015 2015 750 750 750 750 750 2015 1265 2015 2015 2015 2015
E4 4125 4154 4155 4155 4155 4155 4155 4155 4155 1610 1615 1610 1610 1610 4155 2545 4155 4155 4155 4155
E5 4555 4585 4585 4585 4585 4585 4585 4585 4585 2170 2160 2160 2185 2170 4585 2425 4585 4585 4585 4585
E6 2055 2055 2055 2055 2055 2055 2055 2055 2055 670 670 670 670 670 2055 1385 2055 2055 2055 2055
E7 4035 4133 4155 4155 4155 4155 4155 4155 4155 1900 1900 1900 1900 1900 4155 2255 4155 4155 4155 4155
E8 4640 4702 4710 4710 4710 4710 4710 4710 4710 2150 2150 2150 2150 2150 4710 2560 4710 4710 4710 4710
E9 5745 5780 5780 5780 5802 5809 5810 5805 5820 2250 2295 2235 2285 2235 5820 3585        
E10 3605 3605 3605 3605 3605 3605 3605 3605 3605 1690 1690 1690 1690 1690 3605 1915 3605 3605 3605 3605
E11 4630 4637 4637 4640 4650 4650 4650 4650 4650 1850 1840 1850 1850 1835 4655 2820 4650   4650 4650
E12 4065 4161 4180 4180 4170 4179 4180 4180 4180 1710 1705 1710 1715 1710 4180 2485 4180 4180    
E13 3320 3337 3345 3345 3345 3345 3345 3345 3345 1325 1325 1325 1325 1325 3345 2020 3345 3345 3345 3345
E14 4085 4115 4115 4115 4115 4115 4115 4115 4115 1810 1810 1810 1810 1810 4115 2305 4115 4115 4115 4115
E15 4170 4189 4189 4190 4199 4202 4205 4200 4205 1610 1610 1595 1610 1590 4205 2615 4205     4205
E16 3735 3755 3755 3755 3775 3775 3775 3775 3775 1825 1825 1825 1825 1825 3775 1950 3775   3775 3775
E17 2740 2740 2740 2740 2740 2740 2740 2740 2740 1290 1290 1290 1290 1290 2740 1450 2740 2740 2740 2740
E18 3825 3825 3825 3825 3825 3832 3835 3835 3835 1610 1610 1610 1610 1610 3835 2225        
E19 3200 3222 3222 3225 3235 3235 3235 3235 3235 1435 1435 1435 1435 1435 3235 1800 3235   3235 3235
E20 2785 2802 2802 2805 2825 2825 2825 2825 2825 990 990 990 990 990 2825 1835 2825   2825 2825
E21 3725 3728 3728 3730 3730 3730 3730 3730 3730 1705 1705 1705 1705 1705 3730 2025 3730     3730
E22 2440 2470 2470 2470 2470 2470 2470 2470 2470 1185 1185 1185 1185 1185 2470 1285 2470 2470 2470 2470
E23 3675 3686 3686 3690 3704 3707 3710 3710 3710 1430 1435 1435 1430 1430 3710 2280        
E24 3930 4001 4001 4005 4020 4020 4020 4020 4020 1785 1785 1785 1785 1785 4020 2235 4020   4020 4020
E25 1615 1615 1615 1615 1615 1615 1615 1615 1615 655 655 655 655 655 1615 960 1615 1615 1615 1615
F1 4040 4040 4040 4040 4040 4040 4040 4040 4040 1065 1070 1065 1065 1065 4040 2975 4040 4040 4040 4040
F2 3300 3300 3300 3300 3300 3300 3300 3300 3300 920 920 920 920 920 3300 2380 3300 3300 3300 3300
F3 1665 1665 1665 1665 1665 1665 1665 1665 1665 400 400 400 400 400 1665 1265 1665 1665 1665 1665
F4 3475 3476 3476 3480 3485 3485 3485 3485 3485 940 945 940 950 940 3485 2545 3485   3485 3485
F5 3605 3605 3605 3605 3605 3605 3605 3605 3605 1180 1180 1180 1180 1180 3605 2425 3605 3605 3605 3605
F6 1875 1875 1875 1875 1875 1875 1875 1875 1875 490 490 490 490 490 1875 1385 1875 1875 1875 1875
F7 3335 3335 3335 3335 3335 3335 3335 3335 3335 1080 1080 1080 1080 1080 3335 2255 3335 3335 3335 3335
F8 3695 3690 3690 3690 3705 3705 3705 3705 3705 1145 1145 1145 1145 1145 3705 2560 3705   3705 3705
F9 4730 4730 4730 4730 4730 4730 4730 4730 4730 1145 1155 1145 1145 1145 4730 3585 4730 4730 4730 4730
F10 2925 2925 2925 2925 2925 2925 2925 2925 2925 1010 1010 1010 1010 1010 2925 1915 2925 2925 2925 2925
F11 3835 3835 3835 3835 3835 3835 3835 3835 3835 1015 1015 1015 1015 1015 3835 2820 3835 3835 3835 3835
F12 3385 3390 3390 3390 3395 3395 3395 3395 3395 910 910 910 910 910 3395 2485 3395   3395 3395
F13 2855 2855 2855 2855 2855 2855 2855 2855 2855 835 835 835 835 835 2855 2020 2855 2855 2855 2855
F14 3330 3330 3330 3330 3330 3330 3330 3330 3330 1025 1035 1025 1035 1025 3330 2305 3330 3330 3330 3330
F15 3560 3560 3560 3560 3560 3560 3560 3560 3560 945 965 945 945 945 3560 2615 3560 3560 3560 3560
F16 2725 2725 2725 2725 2725 2725 2725 2725 2725 775 775 775 775 775 2725 1950 2725 2725 2725 2725
F17 2055 2005 2055 2055 2055 2055 2055 2055 2055 605 605 605 605 605 2055 1450 2055 2055 2055 2055
F18 3060 3063 3063 3065 3065 3065 3065 3065 3075 850 850 850 850 850 3075 2225        
F19 2485 2500 2500 2500 2515 2515 2515 2515 2525 725 725 725 725 725 2525 1800        
F20 2445 2445 2445 2445 2445 2445 2445 2445 2445 610 610 610 610 610 2445 1835 2445 2445 2445 2445
F21 2930 2930 2930 2930 2930 2930 2930 2930 2930 905 905 905 905 905 2930 2025 2930 2930 2930 2930
F22 2075 2075 2075 2075 2075 2075 2075 2075 2075 790 790 790 790 790 2075 1285 2075 2075 2075 2075
F23 2982 2994 2994 2995 3003 3003 3005 3005 3005 725 730 725 725 725 3005 2280        
F24 3210 3210 3210 3210 3210 3210 3210 3210 3210 975 1010 975 1005 975 3210 2235 3210 3210 3210 3210
F25 1390 1390 1390 1390 1390 1390 1390 1390 1390 430 430 430 430 430 1390 960 1390 1390 1390 1390

Pearn 1989: Pearn, W.L. (1989). Approximate solutions for the capacitated arc routing problem. Computers & Operations Research 16 (6) 579-600.

Benavent et al. 1992: Benavent E, Campos V, Corberán A, Mota E (1992). The capacitated arc routing problem: lower bounds. Networks 22 669-669.

Hertz et al. 2000: Hertz, A., G. Laporte, M. Mittaz. (2000). A Tabu Search Heuristic for the Capacitated Arc Routing Problem. Operations Research 48 (1) 129-135.

Lacomme et al. 2001*: Lacomme, P., C. Prins, W. Ramdane-Chérif. (2001). A genetic algorithm for the capacitated arc routing problem and its extensions. Egbert J.W. Boers, S. Cagnoni, J. Gottlieb, E. Hart, P. Luca Lanzi, G. Raidl, R. E. Smith, H. Tijink, eds., Applications of Evolutionary Computing. EvoWorkshops2001: EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM. Proceedings , LNCS , vol. 2037. Springer-Verlag, Como, Italy, 473–483.

Belenguer Benavent 2003: Belenguer, J.M., E. Benavent. (2003). A cutting plane algorithm for the capacitated arc routing problem. Computers & Operations Research 30 (5) 705-728.

Beullens et al. 2003: Beullens, P., L. Muyldermans, D. Cattrysse, D. Van Oudheusden. (2003). A guided local search heuristic for the capacitated arc routing problem. European Journal of Operations Research 147 (3) 629-643.

Lacomme et al. 2004: Lacomme, P., C. Prins, W. Ramdane-Cherif. (2004). Competitive memetic algorithms for arc routing problems. Annals of Operations Research 131 (1) 159-185.

Ahr 2005: Ahr, D. (2004). Contributions to Multiple Postmen Problems. PhD Thesis, Ruprecht-Karls-Universität, Heidelberg, Germany.

Longo et al. 2006: Longo, H., M.P. de Aragão, E. Uchoa. (2006). Solving Capacitated Arc Routing Probelms using a transformation to the CVRP. Computers & Operations Research 33 (6) 1823-1837.

Baldacci Maniezzo 2006: Baldacci, R., V. Maniezzo. (2006). Exact methods based on node-routing formulations for undirected arc-routing problems. Networks 47 (1) 52-60.

Polacek et al. 2008: Polacek, M., K.F. Doerner, R.F. Hartl, V. Maniezzo. (2008). A variable neighborhood search for the capacitated arc routing problem with intermediate facilities. Journal of Heuristics 14 (5) 405–423.

Brandão Eglese 2008: Brandão, J., R. Eglese. (2008). A deterministic tabu search algorithm for the capacitated arc routing problem. Computers & Operations Research 35 (4) 1112-1126.

Mei et al. 2009: Mei Y., K. Tang, X. Yao. (2009). A Global Repair Operator for Capacitated Arc Routing Problem. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics 39(3):723-734.

Tang et al. 2009: Tang, K., Y. Mei, X. Yao. (2009). Memetic Algorithm with Extended NeighborhoodSearch for Capacitated Arc Routing Problems. IEEE Transactions on Evelutionary Computation 13(5):1151-1166.

Santos et al. 2010: Santos, L., J. Coutinho-Rodrigues, J.R. Current. (2010). An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportations Research Part B 44(2):246–266.

Fu et al. 2010: Fu, H. Y. Mei, K. Tang, Y. Zhu. (2010). Memetic algorithm with heuristic candidate list strategy for capacitated arc routing problem. In: 2010 IEEE Congress on Evolutionary Computation (CEC), 1-8.

Martinelli et al. 2011a: Martinelli, R., D. Pecin, M. Poggi, H. Longo. (2011). A Branch-Cut-and-Price Algorithm for the Capacitated Arc Routing Problem. Annals of Operations Research – Experimental Algorithms, vol 6630, 315–326.

Martinelli et al. 2011b: Martinelli, R., M. Poggi, A. Subramanian. (2011). Improved Bounds for Large Scale Capacitated Arc Routing Problem, Rio de Janeiro, RJ 22453-900, Brazil.

Bartolini et al. 2012: Bartolini, E., J.-F. Cordeau, G. Laporte. (2011). Improved lower bounds and exact algorithm for the capacitated arc routing problem. Mathematical Programming:1-44.

Bode Irnich 2012: Bode, C., S. Irnich (2012). Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem. Operations Research 60 (5) 1167-1182.

Bode Irnich 2012b (revised): Bode, C., S. Irnich (2012b). Technical Report LM-2012-06, Chair of Logistics Management, Johannes Gutenberg University, Mainz, 2012.

Bode Irnich 2013: Bode, C., S. Irnich (2013). Technical Report LM-2013-01, Chair of Logistics Management, Johannes Gutenberg University, Mainz, 2013.  

* Computational Results for Egl instances presented in Belenguer Benavent 2003.