A visual interactive approach to classical and mixed vehicle routing problems with backhauls

Abstract

In this paper a new visual interactive approach for the classical vehicle routing problem with backhauls (VRPB) and its extensions is presented. The classical VRPB is the problem of designing minimum cost routes from a single depot to two type customers that are known as Backhaul (pickup) and Linehaul (delivery) customers where deliveries after pickups are not allowed. The mixed VRPB is an extension of the classical VRPB where deliveries after pickups are allowed. A decision support system (DSS) is developed in order to solve the classical VRPB, mixed VRPB and the restricted VRPB, which is a compromise problem between the classical VRPB, and the mixed VRPB. And a new criterion, which considers the remaining capacity of the vehicles, is proposed for producing solutions for mixed and restricted VRPB. The visual interactive approach that is based on Greedy Randomised Adaptive Memory Programming Search (GRAMPS) is described, and experimental results for the VRPB benchmark test problems are presented and analysed. The computational results on VRPB benchmark test problems indicated that the new criterion and the proposed visual interactive approach are effective towards finding a compromise between the mixed or restricted and the classical VRPB problems. The developed DSS is used by 18 students and reported to be capable of producing high quality solutions for the VRPB. (C) 2006 Elsevier Ltd. All rights reserved.