Cuckoo search and enhanced artificial bee colony heuristic methods for vehicle routing problem with backhaul and time window constraints

Abstract

The vehicle routing problem with backhauls and time windows (VRPBTW) aims to find a feasible vehicle route that minimizes the total traveling distance while imposing capacity, backhaul, and time-window constraints. In this dissertation, a mathematical model of VRPBTW is introduced to obtain an optimal solution. The heuristics, namely the nearest urgent candidate (NUC), which applies the urgency priority and candidate techniques, and the nearest neighbor with roulette wheel selection (NNRW) which is a combination of a roulette wheel selection method and the improved nearest neighbor heuristic, are also presented to solve this problem. Moreover, two metaheuristic methods are presented to obtain the optimal or near optimal solutions. The first is a cuckoo search (CS) algorithm, which is applied to this problem for the first time. The second is the enhanced artificial bee colony (EABC) algorithm which uses a forbidden list, the sequential search for onlookers, and the combination of neighborhood search techniques. The computational results indicate that proposed algorithms yield good performance in terms of solution quality, especially EABC. It obtained 33 ties or new best known solutions out of 45 instances comparing with the best known solutions found in the literature. Hence, the proposed algorithms are the effective ways to solve the VRPBTW.