A memetic NSGA-II for bi-objective mixed capacitated general routing problem

Abstract

The Mixed Capacitated General Routing Problem (MCGRP) is concerned with the determination of the optimal vehicle routes to service a set of customers located at nodes and along edges/arcs on a mixed weighted graph representing a complete distribution network. Although using nodes, edges and arcs simultaneously yields better models for many real-life vehicle routing problems such as newspaper delivery and urban waste collection, very few research works have been dedicated since the MCGRP was defined. Furthermore, most of the studies have focused on the optimization of just one objective, that is, cost minimization. Keeping in mind the requirements of industries nowadays, MCGRP has been addressed in this thesis to concurrently optimize two crucial objectives, namely, minimization of routing cost and route balance (the difference between the largest route and the smallest route with respect to duration). To solve this bi-objective form of the MCGRP, a multi-objective evolutionary algorithm (MOEA), coined as Memetic NSGA-II, has been designed. It is a hybrid of non-dominated sorting genetic algorithm-II (NSGA-II), a dominance based local search procedure (DBLSP) and a clone management principle (CMP). The DBLSP and CMP have been incorporated into the framework of NSGA-II with a view to empowering its capability to converge at/or near the true Pareto front and boosting diversity among the trade-off solutions. In addition, the algorithm also contains a set of three well-known crossover operators (X-set) that are employed to explore different parts of the search space. It was tested on twenty three instances simulating real-life situations and of varying complexity. The computational experiments verify the effectiveness of the Memetic NSGA-II and also show the energetic effects of using DBLSP, CMP and X-set together while finding the set of potentially Pareto optimal solutions.