Decomposition model of vehicle routing problem and hybrid approach mixing branch-and-bound techniques and meta-heuristics

In this paper, we consider a class of pickup and delivery problems. The problem requires that any paired pickup and delivery locations have to be served by one vehicle and the pickup location has to be scheduled before the corresponding delivery location in the route. In order to find near-optimal transportation plans, we discuss a hybrid approach mixing branch-and bound techniques and meta-heuristics. The key idea is that an original problem is decomposed into a set of sub-problems, in which the number of customers assigned to each vehicle is fixed, and respective sub-problem is solved by meta-heuristics such as simulated annealing heuristics. Then, promising sub-problems are able to be found efficiently by using branch-and-bound techniques. The effectiveness and the potential of the proposed approach are evaluated by a series of computational experiments.