A memetic algorithm for a vehicle routing problem with backhauls

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...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2006-10, Vol.181 (2), p.1049-1060
Main Authors: Tavakkoli-Moghaddam, R., Saremi, A.R., Ziaee, M.S.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Local search
Memetic algorithm
Operational research and scientific management
Operational research. Management science
Optimization. Search problems
Theoretical computing
Vehicle Routing Problem with Backhauls
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2006.01.059