Heuristic approaches to vehicle routing with backhauls and time windows

Heuristic approaches to vehicle routing with backhauls and time windows

0.00 Avg rating0 Votes
Article ID: iaor19971886
Country: United Kingdom
Volume: 23
Issue: 11
Start Page Number: 1043
End Page Number: 1057
Publication Date: Nov 1996
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

The vehicle routing problem with backhauls and time windows (VRPBTW) involves the pickup and delivery of goods at different customer locations, with earliest and latest time deadlines, and varying demands. The demands are serviced using capacitated vehicles with limited route time. Moreover, all deliveries (linehauls) must be done before the pickups (backhauls). The objective of the problem is to service all customers while minimizing the number of vehicles and distance traveled. In doing so, the capacity and route time constraints of the vehicles and the time window constraint at each customer should not be violated. In this paper, the authors describe a route construction heuristic for the VRPBTW, as well as different local search heuristics to improve the initial solutions. 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 created problems of size 250 and 500. The solutions produced by the heuristics are within 2.5% of the known optimal solutions on average.

Reviews

Required fields are marked *. Your email address will not be published.