A memetic algorithm for a vehicle routing problem with backhauls

作者：Tavakkoli Moghadam R^*; Saremi A R; Ziaee M S

来源：Applied Mathematics and Computation, 2006, 181(2): 1049-1060.

DOI：10.1016/j.amc.2006.01.059

• vehicle routing problem with backhauls
• memetic algorithm
• local search

This paper considers an extension of a vehicle routing problem with backhauls (VRPB). In this problem, a set of costumers are divided in two subsets consisting of linehaul and backhaul costumers. Each linehaul costumer requires delivering its demands from the depot. In addition, a specified quantity of products should be picked up from the backhaul nodes to the depot. The VRPB is a well-known NP-hard problem in strong sense and a number of algorithms are proposed for approximate solutions of such a hard problem. In this paper, a memetic algorithm (MA) is proposed which uses different local search algorithms to solve the VRPB. Exploiting power of memetic algorithm, inter and intra-route node exchanges are used as a part of this evolutionary algorithm. Extensive computational tests on some instances taken from the literature reveal the effectiveness of the proposed algorithm.

• 出版日期2006-10-15