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

 

 

 

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

 

 

 

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

 

 

 

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

 

 

 

R107.25

4

424.3

KDMSS

R207.25

   3

    361.6

KLM

R107.50

7

711.1

KDMSS

R207.50

 

 

 

R107.100

11

1064.6

CR+KLM

R207.100

 

 

 

R108.25

4

397.3

KDMSS

R208.25

   1

    328.2

IV+C

R108.50

6

617.7

CR+KLM

R208.50

 

 

 

R108.100 

 

 

 

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

 

 

 

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

 

 

 

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

 

 

 

 

 

 

 

Legend:

C - A. Chabrier, “Vehicle Routing Problem with Elementary Shortest Path based Column Generation.” Forthcoming in: Computers and Operations Research (2005).

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.

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): Improving a branch-and-price algorithm for the VRPTW.” Forthcoming in: INFORMS Journal of Computing (2005).

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.

Back to Main Page