A tabu search for the edge set vehicle routing problem with time windows with and without waiting

To reduce emissions, traffic congestion, and noise pollution, municipalities and governments are imposing fees and toll schemes to logistic companies for accessing specific roads. Because such measures increase delivery costs, transportation companies have to consider them when planning routes. In this paper, we address the edge set vehicle routing problem with time windows (ESVRPTW), a generalization of the vehicle routing problem with time windows in which a fixed cost must be paid for making a set of edges accessible. We propose an improved compact formulation for the ESVRPTW, and new variable fixing techniques and valid inequalities. Moreover, we introduce a new ESVRPTW variant called ESVRPTW-noWait to represent urban contexts in which waiting at customer locations is prohibited. To solve these problems, we present a heuristic algorithm called TS-ESVRPTW, that consists of a tabu search framework augmented by an additional diversification component. On benchmark instances from the literature, TS-ESVRPTW achieves high-quality solutions faster than a commercial optimization solver and finds new best-known solutions. The results also show that the additional diversification component of TS-ESVRPTW is fundamental to achieve algorithmic robustness and high-quality solutions for the ESVRPTW and ESVRPTW-noWait. Through an extensive computational study, we derive insights into how allowing waiting at customer locations and how the distribution of the infrastructures requiring the payment of a fixed cost affect the edge-set activation and routing decisions.