HEURISTIC APPROACHES TO VEHICLE-ROUTING WITH BACKHAULS AND TIME WINDOWS

The vehicle routing problem with backhauls and time windows (VRPBTW) i nvolves the pickup and delivery of goods at different customer locatio ns, with earliest and latest time deadlines, and varying demands. The demands are serviced using capacitated vehicles with limited route tim e. Moreover, all deliveries (linehauls) must be done before the pickup s (backhauls). The objective of the problem is to service all customer s while minimizing the number of vehicles and distance traveled. In do ing so, the capacity and route time constraints of the vehicles and th e time window constraint at each customer should not be violated. In t his paper, we describe a route construction heuristic for the VRPBTW, as well as different local search heuristics to improve the initial so lutions. The heuristics were tested on 45 problems of size 25, 50 and 100, previously reported in the literature and whose optimum is known in most cases. In addition, the heuristic was tested on 24 newly creat ed problems of size 250 and 500. The solutions produced by the heurist ics are within 2.5% of the known optimal solutions on average. Copyrig ht (C) 1996 Elsevier Science Ltd