Institute of Transportation, MOTC

　　The vehicle routing problem with backhauls and time windows (VRPBTW), which simultaneously considers the operations of delivery and pickup, is a variant of the classical vehicle routing problem (VRP). Successful application of the VRPBTW in real-world distribution will improve the per-formance of logistics. Due to the NP-hard complexity of VRPBTW, the most so-lution methods are heuristics and meta-heuristics. This paper aims to develop a two-phase backtracking threshold accepting (TBTA) meta-heuristic approach, which combines the threshold accepting (TA) meta-strategy and the traditional local search algorithms, to solve the VRPBTW. We adopted fifteen VRPBTW benchmark instances to test and analyze the performance of the proposed TBTA meta-heuristic. The average error percentages of TBTA are 3.52% for the objec-tive of fleet size and 2.81% for the objective of traveling time. Moreover, the av-erage value of CPU running time is merely 33.69 seconds. Computational re-sults implied that the TBTA actually provides an efficient tool for VRPBTW ap-plications.