Institute of Transportation, MOTC

　　This study proposes a new meta-heuristic approach for solving the vehicle routing problem with backhauls (VRPB). The new approach is a modified backtracking adaptive threshold accepting (MBATA) solution scheme which combines the relaxed backtracking adaptive threshold accepting (RBATA) method and flip-flop heuristics (FF).The benchmark problems described by Goetschalckx and Jacobs-Blecha (1989) were selected for performance evaluation. Results showed that our proposed MBATA yielded 37 best-known solutions among 62 test instances, and the average deviation is merely 0.13%.