A heuristic algorithm for the Load-dependent Capacitated Vehicle Routing Problem with Time Windows

In this paper we introduce an extension of the vehicle routing problem with time windows (VRPTW) called the Load-dependent Capacitated Vehicle Routing Problem with Time Windows (LDVRPTW). This problem differs from the classical VRP and VRPTW on the transportation costs, which are calculated not only on the travel distance, but also the loads on the arcs. We propose a metaheuristic to address this LDVRPTW problem. The proposed algorithm is tested on benchmark instances on special case problems of LDVRPTW. Numerical results show that on some LDVRPTW variants our metaheuristic outperforms the available state-of-the-art exact and heuristic methods.