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

Line Blander Reinhardt (), Mads Kehlet Jepsen () and David Pisinger ()
Additional contact information
Line Blander Reinhardt: Department of Management Engineering, Technical University of Denmark, DK-2800 Kgs. Lyngby, Denmark
Mads Kehlet Jepsen: Department of Management Engineering, Technical University of Denmark, DK-2800 Kgs. Lyngby, Denmark
David Pisinger: Department of Management Engineering, Technical University of Denmark, DK-2800 Kgs. Lyngby, Denmark

Transportation Science, 2016, vol. 50, issue 2, 694-707

Abstract: 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.

Keywords: VRPTW; branch cut and price; multigraphs (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2015.0620 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:50:y:2016:i:2:p:694-707

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().