Abstract
This chapter addresses the family of problems known in the literature as Capacitated Vehicle Routing Problems (CVRP). A procedure is introduced for the optimization of a version of the generic CVRP. It generates feasible clusters and, in a first step, yields a coding of their ordering. The next stage provides this information to a genetic algorithm for its optimization. A selective pressure process is added in order to improve the selection and subsistence of the best candidates. This arrangement allows improving the performance of the algorithm. We test it using Van Breedam and Taillard's problems, yielding similar results as other algorithms in the literature. Besides, we test the algorithm on real-world problems, corresponding to an Argentinean company distributing fresh fruit. Four instances, with 50, 100, 150 and 200 clients were examined, giving better results than the current plans of the company.
TopAdditional Readings
As mentioned above, different extensions to the basic VRP have been developed in the last decade. So for instance, time windows for client attention were added to the basic problem yielding the VRPTW (Vehicle Routing Problem with Time Windows) (Wang, 2012; Desrochers et al., 2002; Khebbache-Hadji et al., 2013). Another way in which VRP has been enlarged is with multiple depots (MDVRP, Multi-Depot Vehicle Routing Problem) (Escobar et al., 2014). Other extensions involve the possibility of returning some delivered goods to the deposit (VRPPD, Vehicle Routing Problem with Pick-Up and Delivering) (Çatay, 2009; Thangiah et al., 2007), or that different vehicles can deliver to a single client (SDVRP, Split Delivery Vehicle Routing Problem) (Aleman & Hill, 2010; Aleman et al., 2010; Belenguer et al., 2010; Derigs et al., 2009; Nagao & Nagamochi, 2007; Moreno et al., 2010; Bolduc et al., 2010). Another addition is that some values (number of clients, their demands, servicing time or in-route time) can be random (SVRP, Stochastic Vehicle Routing Problem) (Zhang et al., 2013) and that some deliveries can be performed in certain dates (PVRP, Periodic Vehicle Routing Problem) (Kurz & Zäpfel, 2013). Finally, some problems combine some of these operational conditions (Belfiore & Yoshizaki, 2009; Nowak et al., 2009).
Key Terms in this Chapter
Crossover Operator: A genetic operator that generates diversity by combining fragments of the chromosomes of possible solutions yielding a new candidate.
Optimization: The process of finding the maxima or minima of either a single (mono-objective) or of several (multi-objective) functions over a set of a constrained set of alternatives.
Meta-Heuristics: A search procedure intended to solve computational problems, by seeking appropriate solution methods by adjusting parameters and specifications.
Genetic Algorithm: A series of steps to allow the evolution of solutions to specific problems. It is inspired in biological evolution and particularly its genetic-molecular basis.
Selection process: Procedure to choose some individuals out from a population in order to apply genetic operators to them and so generating a new population.
Genetic operator: A function applied in a genetic algorithm in order to ensure the diversity of a population.
Vehicle Routing Problem: A class of transportation optimization problem. It seeks to find the minimal length routes of provision to different clients.
Mutation Operator: A genetic operator that generates diversity by changing the chromosome of a candidate solution yielding an alternative candidate.
Decision-Making: The process of choosing an alternative among a class of them, with the aim of solving a given problem.