This is an updated version of the original table by M. M. Solomon found here.
Updated September 2007 by Simon Spoorendonk.

Optimal Solutions for R1 and R2 problems
 
 
 

Problem

NV

Distance

Authors

Problem

NV

Distance

Authors

R101.25

8

617.1

KDMSS

R201.25 

  

463.3

CR+KLM

R101.50

12

1044.0

KDMSS

R201.50 

   6

791.9

CR+KLM

R101.100

20

1637.7

KDMSS

R201.100

   8

  1143.2

KLM

R102.25

7

547.1

KDMSS

R202.25 

   4

410.5

CR+KLM

R102.50

11

909

KDMSS

R202.50 

   5

698.5

CR+KLM

R102.100

18

1466.6

KDMSS

R202.100

8

1029.6

JPSP

R103.25

5

454.6

KDMSS

R203.25 

   3

391.4

CR+KLM

R103.50

9

772.9

KDMSS

R203.50

   5

    605.3

IV+C

R103.100

14

1208.7

CR+L

R203.100

6

870.8

JPSP

R104.25

4

416.9

KDMSS

R204.25

   2

    355.0

IV+C

R104.50

6

625.4

KDMSS

R204.50

   2

    506.4

 IV

R104.100 

 11

 971.5

 IV

R204.100

 

 

 

R105.25

6

530.5

KDMSS

R205.25 

   3

393.0

CR+KLM

R105.50

9

899.3

KDMSS

R205.50

   4

    690.1

IV+C

R105.100

15

1355.3

KDMSS

R205.100

5

949.8

DLH

R106.25

3

465.4

KDMSS

R206.25 

   3

374.4

CR+KLM

R106.50

5

793

KDMSS

R206.50

   4

    632.4

IV+C

R106.100

13

1234.6

CR+KLM

R206.100

5

875.9

DLH

R107.25

4

424.3

KDMSS

R207.25

   3

    361.6

KLM

R107.50

7

711.1

KDMSS

R207.50

3

575.5

JPSP

R107.100

11

1064.6

CR+KLM

R207.100

4

794.0

DLH

R108.25

4

397.3

KDMSS

R208.25

   1

    328.2

IV+C

R108.50

6

617.7

CR+KLM

R208.50

2

487.7

KBM

R108.100 

10

932.1

JPSP

R208.100

 

 

 

R109.25

5

441.3

KDMSS

R209.25

   2

    370.7

KLM

R109.50

8

786.8

KDMSS

R209.50

   4

    600.6

IV+C

R109.100

13

1146.9

CR+KLM

R209.100

9

854.8

JPSP

R110.25

4

444.1

KDMSS

R210.25 

   3

404.6

CR+KLM

R110.50

7

697.0

KDMSS

R210.50

   4

    645.6

IV+C

R110.100

12

1068

CR+KLM

R210.100

6

900.5

DLH

R111.25

5

428.8

KDMSS

R211.25

   2

   350.9 

KLM 

R111.50

7

707.2

CR+KLM

R211.50

   3

   535.5

 IV+DLP

R111.100

12

1048.7

CR+KLM

R211.100

 

 

 

R112.25

4

393

KDMSS

 

 

 

 

R112.50

6

630.2

CR+KLM

 

 

 

 

R112.100

10

948.6

JPSP

 

 

 

 

Legend:

C - A. Chabrier, “Vehicle Routing Problem with Elementary Shortest Path based Column Generation”, Computers and Operations Research, Vol. 33 (10), 2972 - 2990 (2006).

CR - W. Cook and J. L. Rich,  "A parallel cutting plane algorithm for the vehicle routing problem with time windows", Working Paper, Computational and Applied Mathematics, Rice University, Houston, TX, 1999.

DLH - G. Desaulniers, F. Lessard and A. Hadjar,"Tabu search, generalized kpath inequalities, and partial elementarity for the vehicle routing problem with time windows", Technical Report G-2006-45, GERAD and Department de mathematiques et de genie industriel Ecole Polytechnique de Montreal (2006).

DLP - E. Danna and C. Le Pape, “Accelerating branch-and-price with local search: A case study on the vehicle routing problem with time windows”, In: Column Generation, G. Desaulniers, J. Desrosiers, and M. M. Solomon (eds.), 99-130, Kluwer Academic Publishers (2005).

IV -  S. Irnich and D. Villeneuve, “The shortest path problem with k-cycle elimination (k ≥ 3)”, INFORMS Journal on Computing, Vol. 18 (3), 391-406 (2006).

JPSP - M. Jepsen, B. Petersen, S. Spoorendonk and D. Pisinger,"Subset-Row Inequalities applied to the Vehicle Routing Problem with Time Windows", Forthcoming in: Operations Research, (2006).

KBM - B. Kallehauge, N. Boland and O.B.G. Madsen,"Vehicle Routing Problem with Elementary Shortest Path based Column Generatio.", Networks, Vol. 49 (4), 273-293 (2007).

KDMSS - N. Kohl, J. Desrosiers, O. B. G. Madsen, M. M. Solomon, and F. Soumis,  "2-Path Cuts for the Vehicle Routing Problem with Time Windows", Transportation Science, Vol. 33 (1), 101-116 (1999).

KLM - B. Kallehauge, J. Larsen, and O.B.G. Madsen.  "Lagrangean duality and non-differentiable optimization applied on routing with time windows - experimental results", Internal report IMM-REP-2000-8, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 2000.

L - J. Larsen.  "Parallelization of the vehicle routing problem with time windows", Ph.D. Thesis IMM-PHD-1999-62, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 1999.

S - M. Salani.  "Branch-and-Price Algorithms for Vehicle Routing Problems", Università degli studi di Milano, Facolta di Scienza Matematiche, Fisuche e Naturali Dipartimento di Technologie dell'Informazione, Milano, Italy Ph.D. Thesis, 2006.

C1 & 2

RC1 & 2

Back