The vehicle routing problem with edge set costs

Line Blander Reinhardt, Mads Kehlet Jepsen, David Pisinger

    Research output: Book/ReportReportResearch

    230 Downloads (Pure)


    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 contributions impose a cost for the company while they also give unlimited usage of a set of roads to all vehicles belonging to the company. Different versions for defining the edge sets are discussed and formulated. A MIP-formulation of the problem is presented, and a solution method based on branch-and-price-and-cut is applied to the problem. The computational results show that instances with up to 50 customers can be solved in reasonable time, and that the branch-cut-and-price algorithm generally outperforms CPLEX. It also seems that instances get more difficult when the penalized edge sets form a spanning tree, compared to when they are randomly scattered.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages15
    Publication statusPublished - 2011
    SeriesDTU Management 2011

    Fingerprint Dive into the research topics of 'The vehicle routing problem with edge set costs'. Together they form a unique fingerprint.

    Cite this