### Abstract

This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX.

Original language | English |
---|---|

Journal | Transportation Science |

Volume | 50 |

Issue number | 2 |

Pages (from-to) | 694–707 |

ISSN | 0041-1655 |

DOIs | |

Publication status | Published - 2016 |

### Keywords

- VRPTW
- Branch cut and price
- Multigraphs

### Cite this

*Transportation Science*,

*50*(2), 694–707. https://doi.org/10.1287/trsc.2015.0620

}

*Transportation Science*, vol. 50, no. 2, pp. 694–707. https://doi.org/10.1287/trsc.2015.0620

**The Edge Set Cost of the Vehicle Routing Problem with Time Windows.** / Reinhardt, Line Blander; Jepsen, Mads Kehlet; Pisinger, David.

Research output: Contribution to journal › Journal article › Research › peer-review

TY - JOUR

T1 - The Edge Set Cost of the Vehicle Routing Problem with Time Windows

AU - Reinhardt, Line Blander

AU - Jepsen, Mads Kehlet

AU - Pisinger, David

PY - 2016

Y1 - 2016

N2 - We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications, and other costly investments. The certifications and investments impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company.This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX.

AB - We consider an important generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for accessing a set of edges. This fixed cost could reflect payment for toll roads, investment in new facilities, the need for certifications, and other costly investments. The certifications and investments impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company.This violates the traditional assumption that the path between two destinations is well defined and independent of other choices. Different versions for defining the edge sets are discussed and formulated. Both the multigraph case and the direct path case are described, and mixed-integer-programming formulations of the problem are presented for both cases. A solution method based on branch-price-and-cut is applied to the direct path case. The computational results show that instances with up to 40 customers can be solved in a reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX.

KW - VRPTW

KW - Branch cut and price

KW - Multigraphs

U2 - 10.1287/trsc.2015.0620

DO - 10.1287/trsc.2015.0620

M3 - Journal article

VL - 50

SP - 694

EP - 707

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 2

ER -