Smart logistics is an indispensable building block in smart cities development that requires solving the challenge of efficiently serving the demands of geographically distributed customers by a fleet of vehicles. It consists of a very well-known NP-hard complex optimization problem, which is known as the capacitated vehicle routing problem (CVRP). The CVRP has widespread real-life applications such as delivery in smart logistics, the pharmaceutical distribution of vacancies, disaster relief efforts, and others. In this work, a novel giant tour best cost crossover (GTBCX) operator is proposed which works stochastically to search for the optimal solutions of the CVRP. An NSGA-II-based routing algorithm employing GTBCX is also proposed to solve the CVRP to minimize the total distance traveled as well as to minimize the longest route length. The simulated study is performed on 88 benchmark CVRP instances to validate the success of our proposed GTBCX operator against the nearest neighbor crossover (NNX) and edge assembly crossover (EAX) operators. The rigorous simulation study shows that the GTBCX is a powerful operator and helps to find results that are superior in terms of the overall distance traveled, length of the longest route, quality, and number of Pareto solutions. This work employs a multi-objective optimization algorithm to solve the capacitated vehicle routing problem (CVRP), where the CVRP is represented in the form of a two-dimensional graph. To compute the values’ objective functions, the distance between two nodes in the graph is considered symmetric. This indicates that the genetic algorithm complex optimization algorithm is employed to solve CVRP, which is a symmetry distance-based graph.