Abstract
The Vehicle Routing Problem (VRP) is one of important combinatorial problems, which holds a central place in logistics management. One of the most widely studied problems in the VRP family is the Multi-Depot Vehicle Routing Problem (MDVRP), where more than one depot is considered. In this chapter, the authors focus on a new extension of the MDVRP in which goods loaded by the vehicle are restricted due to limited stocks available at warehouses. More specifically, this extension consists in determining a least cost routing plan that can satisfy all the customs demands by delivering available stocks. Indeed, this problem is often encountered when goods are shortage in some warehouses. To deal with the problem efficiently, a memetic algorithm is proposed in this chapter. The authors study this approach on a set of modified benchmark instances and compare its performance to a pure genetic algorithm.
TopIntroduction
The success of optimization techniques has been impacted on the economic system. Their applications help decision-makers to operate in many area, including industrial, economics, business and financial systems (Dieu & Ongsakul, 2012; Vasant, 2012; Cebi, Kahraman, & Kaya, 2012; Sadrnia, Nezamabadi-Pour, Nikbakht, & Ismail, 2013; Purnomo & Wee, 2013; Vo & Schegner, 2013; Dostál, 2013; Senvar, Turanoglu, & Kahraman, 2013; Vasant, 2013; Zelinka, Vasant, & Barsoum, 2013).
How to find efficient vehicle routes is not only an academic problem, but also has immense value in practice due to its high impact on cost and customer satisfaction. This problem, referred to the Vehicle Routing Problem (VRP), consists in finding a set of routes satisfying all the constraints while minimize the overall cost. Although the VRP has been studied for several decades, the field of this problem is still active as witnessed by a large number of recent papers appeared in the literature. That might be due to its applications in various real-world situations, resulting in different version of the VRP. Often, the VRP is often defined on a graph 
where 
is the customer set, 
is the depot set and 
is the edge set. Generally, each customer must be assigned to exactly one of the vehicles. The total demand for customers on any routes must not exceed the vehicle capacity. By optimizing this problem, companies can save money and increase customer satisfaction. Hence, it plays an important role in the fields of transportation, distribution and logistics. Realizing this importance role, a lot of efforts have been made in finding efficient way to solve this issue since Dantzig and Ramser (1959) first introduced this problem. In essence, the elementary version of the VRP, called the capacitated vehicle routing problem (CVRP), can be stated as follows: a set of customers with known demand are to be serviced by a homogenous fleet of vehicles with limited capacity. The VRP consists of designing a set of vehicle routes satisfying the following constrains:
- 1.
Each customer is visited exactly once by a vehicle,
- 2.
Each vehicle route begins and ends at the depot,
- 3.
The total demand serviced of any rout does not exceed the limited capacity of vehicle. Obviously, the main objective of the VRP is that the total cost of all vehicle routes is minimized.
Key Terms in this Chapter
Genetic Algorithm: The basic idea behind genetic algorithm is to apply the principles of Darwin’s evolution theory. Briefly speaking, the algorithm is often done by the following procedure: 1) encoding of an initial population of chromosomes, i.e., representing solutions; 2) defining a fineness function; 3) evaluating the population by using genetic operations resulting in a new population; 4) decoding the result to obtain the solution of problem.
Local Search: Given a set of solutions S , every solution has an associated set of neighbors, expressed by , each of them is called the neighborhood of s . All the neighborhood of s , namely , can be reached directly from s by one move (or transition) to . Local search is performed in such a way to find a local optimal solution. It should be noted that this search is achieved by defining a neighborhood structure.
Vehicle Routing Problem: A set of customers with known demand are to be serviced by a homogenous fleet of vehicles with limited capacity.
Limited Stocks: As it implicates, this term is used to indicate that there are limited goods at depots.
Evolutionary Algorithm: The algorithm uses mechanisms inspired by biological evolution, including genetic algorithm (GA), ant colony optimization (ACO) and differential evolution (DA).
Multi-Depot: This term is often used in variants of the vehicle routing problem. It means more than one depot is considered.
Artificial Intelligent Algorithm: Roughly speaking, artificial intelligence (AI) refers to an intelligent system that simulates a certain form of human reasoning, knowledge, and expertise for solving one (or several) given problem(s). Therefore, any algorithm based on this concept can be referred as artificial intelligent algorithm.