Benchmarks

Exact Solution of the Vehicle Routing Problem with Drones

The working paper

J. Schmidt, C. Tilk, S. Irnich (2023). Exact Solution of the Vehicle Routing Problem with Drones LM-2023-03, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.

uses the following instances.

Zip file with instances.

Exact Solution of the Single Picker Routing Problem with Scattered Storage

The results reported in the working paper

K. Heßler, S. Irnich (2023). Exact Solution of the Single Picker Routing Problem with Scattered Storage LM-2023-02, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.

are available at GitHub.

The Single Picker Routing Problem with Scattered Storage: Modeling and Evaluation of Routing and Storage Policies

The working paper

L. Korbacher, K. Heßler, S. Irnich (2023). The Single Picker Routing Problem with Scattered Storage: Modeling and Evaluation of Routing and Storage Policies LM-2023-01, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.

uses the following instances.

Zip file with instances.

A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows

The working paper

Dorian Dumez, Christian Tilk, Stefan Irnich, Katharina Olkis, Fabien Lehuédé, and Olivier Péton
HAL archives ouvertes.fr, hal-03384261

uses the following instances.

Zip file with instances.

Modeling and Exact Solution of Picker Routing and Order Batching Problems

The working paper

K. Heßler, S. Irnich (2022). Modeling and Exact Solution of Picker Routing and Order Batching Problems LM-2022-03, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.

uses the following instances.

Zip file with instances.

Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem

The working paper

K. Heßler, S. Irnich (2021). Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem LM-2021-02, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.
Forthcoming in: INFORMS Journal on Computing.

uses the following instances.

Zip file with instances.

Using Public Transport in a 2-Echelon Last-Mile Delivery Network

The working paper

J. Schmidt, C. Tilk, S. Irnich (2022). Using Public Transport in a 2-Echelon Last-Mile Delivery Network, Technical Report LM-2022-01, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.

uses the following instances.

Zip file with instances.

Exact Algorithms for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes

The working paper

Katrin Heßler (2020). Exact Algorithms for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes, Technical Report LM-2020-04, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.

uses the following instances.

Zip file with instances.

The Last-mile Vehicle Routing Problem with Delivery Options

The working paper

Christian Tilk, Katharina Olkis, Stefan Irnich (2020). The Last-mile Vehicle Routing Problem with Delivery Options, Technical Report LM-2020-06, Chair of Logistics Management, Johannes Gutenberg University, Mainz, Germany.

uses the following instances.

Zip file with instances.

Lexicographic Bin-Packing Optimization for Loading Trucks in a Direct-Shipping System

The working paper

K. Heßler, S. Irnich, T. Kreiter, U. Pferschy (2020). Lexicographic Bin-Packing Optimization for Loading Trucks in a Direct-Shipping System. Technical Report LM-2020-05, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Germany.

uses 110 new benchmark instances.

Zip file with instances.

Multi-Depot Vehicle Routing Problem

The working paper

JB. Gauthier, S. Irnich (2020). Inter-Depot Moves and Dynamic-Radius Search for Multi-Depot Vehicle Routing Problems. Technical Report LM-2020-03, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Germany.

uses the following benchmark instances.

Zip file and file with instances.

Soft-Clustered Vehicle Routing Problem

The working paper

K. Heßler, S. Irnich (2020). A Branch-and-Cut Algorithm for the Soft-Clustered Vehicle Routing Problem. Technical Report LM-2020-01, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Germany.

uses 90 new benchmark instances.

Zip files with instances.

Soft-Clustered Capacitated Arc-Routing Problem (SoftCluCARP)

The working paper

T. Hintsch, S. Irnich, L. Kiilerich (2019). Branch-Price-and-Cut for the Soft-Clustered Capacitated Arc-Routing Problem. Technical Report LM-2019-02, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Germany.

uses 644 new benchmark instances.

Zip file with instances (for the format see below at the CARP instances).

Direct Delivery Scheduling Problem in a Network

The working paper

T. Gschwind, S. Irnich, C. Tilk, S. Emde (2018). Branch-Cut-and-Price for Scheduling Deliveries with Time Windows in a Direct Shipping Network. Technical Report LM-2018-03, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Mainz, Germany.

uses 120 new benchmark instances.

Zip file with instances.

Commodity-Constrained Split Delivery Vehicle Routing Problem

The working paper

T. Gschwind, N. Bianchessi, S. Irnich (2018). Stabilized Branch-Price-and-Cut for the Commodity-Constrained Split Delivery Vehicle Routing Problem. Technical report LM-2018-06, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Mainz, Germany.

uses new benchmark instances with a larger number of commodities (4, 5, and 6) that are otherwise generated in the same way as the instances introduced in

Archetti, C., Campbell, A. M., Speranza, M. G. (2016). Multicommodity vs. single-commodity routing. Transportation Science, 50(2), 461–472.

Zip file with instances including the original benchmark instances from Archetti et al.

Vector Packing Problem

The working paper

K. Heßler, T. Gschwind, S. Irnich (2017). Stabilized Branch-and-Price Algorithms for Vector Packing Problems. Technical report LM-2017-04, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Mainz, Germany.

uses 440 new benchmark instances that add larger demand to the 2-dimensional instances of

Caprara, A. and Toth, P. (2001). Lower bounds and algorithms for the 2-dimensional vector packing problem. Discrete Applied Mathematics, 111(3), 231–262.

and the 20-dimensional instances of

Brandao, F. and Pedroso, J. P. (2016). Bin packing and related problems: general arc-flow formulation with graph compression. Computers & Operations Research, 69, 56–67.

Zip file with instances.

Zip file with optimal values.

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.

Cutting Stock Problem

The GI instances were introduced in:

Gschwind, T. and Irnich, S. Dual inequalities for stabilized column generation revisited. INFORMS Journal on Computing, 28(1), 175–194, 2016, doi: 10.1287/ijoc.2015.0670

Zip file and 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.