Reinhardt, Line Blander2; Jepsen, Mads Kehlet2; Pisinger, David2
1 Operations Research, Department of Management Engineering, Technical University of Denmark2 Department of Management Engineering, Technical University of Denmark
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.