Time-dependent vehicle routing problem with backhaul with FIFO assumption: Variable neighborhood search and mat-heuristic variable neighborhood search algorithms

Abstract

This paper presents a mathematical model for a single depot, time-dependent vehicle routing problem with backhaul considering the first in first out (FIFO) assumption. As the nature of the problem is NP-hard, variable neighborhood search (VNS) meta-heuristic and mat-heuristic algorithms have been designed. For test problems with large scales, obtained results highlight the superior performance of the mat-heuristic algorithm compared with that of the other algorithm. Finally a case study at the post office of Khomeini-Shahr town, Iran, was considered. Study results show a reduction of roughly 19% (almost 45 min) in the travel time of the vehicle.