A 2-phase constructive algorithm for cumulative vehicle routing problems with limited duration

•Heuristics for cumulative vehicle routing problem with time limit are developed.•Clarke & Wright Algorithm is enhanced by considering load flow.•Proposed version improves significantly solution quality at some expense of CPU time.•A new hybrid constructive heuristic including clustering is proposed.•Hybrid algorithm improves CPU time significantly and obtains fairly good solutions.

The Clarke & Wright (C&W) algorithm is one of the most widely used classical heuristics in capacitated Vehicle Routing Problems (VRPs) in which a linear function of distance is considered as the objective function. The C&W algorithm is very simple and easy to implement, and produces fairly good solutions very fast. In this study, the C&W algorithm is adopted for the cumulative VRP with limited duration (CumVRP-LD) where load is also considered in the objective function as well as distance. The most common applications of cumulative VRPs are the determination of routing policies that minimize total fuel consumption. A 2-phase constructive heuristic approach including the K-means clustering algorithm is proposed to improve the computational performance of the modified C&W algorithm for CumVRP-LD. The main contribution of this study is the definition of a new extended formulation that captures truck-load and travel distance by considering the unique characteristics of the problem and to develop a fast and easy implemented constructive algorithm for CumVRP-LD. Such approaches are necessary for the development of systems that respond fast, possibly online, to changes in the real problem situations.