Genetic Crossover Operators for the Capacitated Vehicle Routing Problem

We study the capacitated vehicle routing problem(CVRP)which is a well-known NP-hard combinatorial optimization problem(COP).The aim of the problem is to serve different customers by a convoy of vehicles starting from a depot so that sum of the routing costs under their capacity constraints is minimized.Since the problem is very complicated,solving the problem using exact methods is almost impossible.So,one has to go for the heuristic/metaheuristic methods and genetic algorithm(GA)is broadly applied metaheuristic method to obtain near optimal solution to such COPs.So,this paper studies GAs to find solution to the problem.Generally,to solve a COP,GAs start with a chromosome set named initial population,and then mainly three operators-selection,crossover andmutation,are applied.Among these three operators,crossover is very crucial in designing and implementing GAs,and hence,numerous crossover operators were developed and applied to different COPs.There are two major kinds of crossover operators-blind crossovers and distance-based crossovers.We intend to compare the performance of four blind crossover and four distance-based crossover operators to test the suitability of the operators to solve the CVRP.These operators were originally proposed for the standard travelling salesman problem(TSP).First,these eight crossovers are illustrated using same parent chromosomes for building offspring(s).Then eight GAs using these eight crossover operators without any mutation operator and another eight GAs using these eight crossover operators with a mutation operator are developed.These GAs are experimented on some benchmark asymmetric and symmetric instances of numerous sizes and various number of vehicles.Our study revealed that the distance-based crossovers are much superior to the blind crossovers.Further,we observed that the sequential constructive crossover with and without mutation operator is the best one for theCVRP.This estimation is validated by Student’s t-test at 95%confidence level.We further determined a comparative rank of the eight crossovers for the CVRP.

New Hybrid Algorithm Based on BicriterionAnt for Solving Multiobjective Green Vehicle Routing Problem

The main objective of this paper is to propose a new hybrid algorithm for solving the Bi objective green vehicle routing problem (BGVRP) from the BicriterionAnt metaheuristic. The methodology used is subdivided as follows: first, we introduce data from the GVRP or instances from the literature. Second, we use the first cluster route second technique using the k-means algorithm, then we apply the BicriterionAntAPE (BicriterionAnt Adjacent Pairwise Exchange) algorithm to each cluster obtained. And finally, we make a comparative analysis of the results obtained by the case study as well as instances from the literature with some existing metaheuristics NSGA, SPEA, BicriterionAnt in order to see the performance of the new hybrid algorithm. The results show that the routes which minimize the total distance traveled by the vehicles are different from those which minimize the CO2 pollution, which can be understood by the fact that the objectives are conflicting. In this study, we also find that the optimal route reduces product CO2 by almost 7.2% compared to the worst route.

An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem

The multi-compartment electric vehicle routing problem(EVRP)with soft time window and multiple charging types(MCEVRP-STW&MCT)is studied,in which electric multi-compartment vehicles that are environmentally friendly but need to be recharged in course of transport process,are employed.A mathematical model for this optimization problem is established with the objective of minimizing the function composed of vehicle cost,distribution cost,time window penalty cost and charging service cost.To solve the problem,an estimation of the distribution algorithm based on Lévy flight(EDA-LF)is proposed to perform a local search at each iteration to prevent the algorithm from falling into local optimum.Experimental results demonstrate that the EDA-LF algorithm can find better solutions and has stronger robustness than the basic EDA algorithm.In addition,when comparing with existing algorithms,the result shows that the EDA-LF can often get better solutions in a relatively short time when solving medium and large-scale instances.Further experiments show that using electric multi-compartment vehicles to deliver incompatible products can produce better results than using traditional fuel vehicles.

Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows

The time dependent vehicle routing problem with time windows（TDVRPTW） is considered. A multi-type ant system（MTAS） algorithm hybridized with the ant colony system（ACS）and the max-min ant system（MMAS） algorithms is proposed. This combination absorbs the merits of the two algorithms in solutions construction and optimization separately. In order to improve the efficiency of the insertion procedure, a nearest neighbor selection（NNS） mechanism, an insertion local search procedure and a local optimization procedure are specified in detail. And in order to find a balance between good scouting performance and fast convergence rate, an adaptive pheromone updating strategy is proposed in the MTAS. Computational results confirm the MTAS algorithm＇s good performance with all these strategies on classic vehicle routing problem with time windows（VRPTW） benchmark instances and the TDVRPTW instances, and some better results especially for the number of vehicles and travel times of the best solutions are obtained in comparison with the previous research.

GREEDY NON-DOMINATED SORTING IN GENETIC ALGORITHM-ⅡFOR VEHICLE ROUTING PROBLEM IN DISTRIBUTION

Vehicle routing problem in distribution （VRPD） is a widely used type of vehicle routing problem （VRP）, which has been proved as NP-Hard, and it is usually modeled as single objective optimization problem when modeling. For multi-objective optimization model, most researches consider two objectives. A multi-objective mathematical model for VRP is proposed, which considers the number of vehicles used, the length of route and the time arrived at each client. Genetic algorithm is one of the most widely used algorithms to solve VRP. As a type of genetic algorithm （GA）, non-dominated sorting in genetic algorithm-Ⅱ （NSGA-Ⅱ） also suffers from premature convergence and enclosure competition. In order to avoid these kinds of shortage, a greedy NSGA-Ⅱ （GNSGA-Ⅱ） is proposed for VRP problem. Greedy algorithm is implemented in generating the initial population, cross-over and mutation. All these procedures ensure that NSGA-Ⅱ is prevented from premature convergence and refine the performance of NSGA-Ⅱ at each step. In the distribution problem of a distribution center in Michigan, US, the GNSGA-Ⅱ is compared with NSGA-Ⅱ. As a result, the GNSGA-Ⅱ is the most efficient one and can get the most optimized solution to VRP problem. Also, in GNSGA-Ⅱ, premature convergence is better avoided and search efficiency has been improved sharply.

An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem

The vehicle routing problem(VRP)is a typical discrete combinatorial optimization problem,and many models and algorithms have been proposed to solve the VRP and its variants.Although existing approaches have contributed significantly to the development of this field,these approaches either are limited in problem size or need manual intervention in choosing parameters.To solve these difficulties,many studies have considered learning-based optimization(LBO)algorithms to solve the VRP.This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.We performed a statistical analysis of the reviewed articles from various aspects and designed three experiments to evaluate the performance of four representative LBO algorithms.Finally,we conclude the applicable types of problems for different LBO algorithms and suggest directions in which researchers can improve LBO algorithms.

Research on Vehicle Routing Problem with Soft Time Windows Based on Hybrid Tabu Search and Scatter Search Algorithm

With the expansion of the application scope of social computing problems,many path problems in real life have evolved from pure path optimization problems to social computing problems that take into account various social attributes,cultures,and the emotional needs of customers.The actual soft time window vehicle routing problem,speeding up the response of customer needs,improving distribution efficiency,and reducing operating costs is the focus of current social computing problems.Therefore,designing fast and effective algorithms to solve this problem has certain theoretical and practical significance.In this paper,considering the time delay problem of customer demand,the compensation problem is given,and the mathematical model of vehicle path problem with soft time window is given.This paper proposes a hybrid tabu search(TS)&scatter search(SS)algorithm for vehicle routing problem with soft time windows(VRPSTW),which mainly embeds the TS dynamic tabu mechanism into the SS algorithm framework.TS uses the scattering of SS to avoid the dependence on the quality of the initial solution,and SS uses the climbing ability of TS improves the ability of optimizing,so that the quality of search for the optimal solution can be significantly improved.The hybrid algorithm is still based on the basic framework of SS.In particular,TS is mainly used for solution improvement and combination to generate new solutions.In the solution process,both the quality and the dispersion of the solution are considered.A simulation experiments verify the influence of the number of vehicles and maximum value of tabu length on solution,parameters’control over the degree of convergence,and the influence of the number of diverse solutions on algorithm performance.Based on the determined parameters,simulation experiment is carried out in this paper to further prove the algorithm feasibility and effectiveness.The results of this paper provide further ideas for solving vehicle routing problems with time windows and improving the efficiency of vehicle routing problems and have strong applicability.

An Alternative Algorithm for Vehicle Routing Problem with Time Windows for Daily Deliveries

This study attempts to solve vehicle routing problem with time window (VRPTW). The study first identifies the real problems and suggests some recommendations on the issues. The technique used in this study is Genetic Algorithm (GA) and initialization applied is random population method. The objective of the study is to assign a number of vehicles to routes that connect customers and depot such that the overall distance travelled is minimized and the delivery operations are completed within the time windows requested by the customers. The analysis reveals that the problems experienced in vehicle routing with time window can be solved by GA and retrieved for optimal solutions. After a thorough study on VRPTW, it is highly recommended that a company should implement the optimal routes derived from the study to increase the efficiency and accuracy of delivery with time insertion.

Vehicle routing problem with time-varying speed

Vehicle routing problem with time-varying speed ( VRPTS) is a generalization of vehicle routing problem in which the travel speed between two locations depends on the passing areas and the time of a day. This paper proposes a simple model for estimating time-varying travel speeds in VRPTS that relieves much burden to the data-related problems. The study further presents three heuristics ( saving technique,proximity priority searching technique,and insertion technique) for VRPTS,developed by extending and modifying the existing heuristics for conventional VRP. The results of computational experiments demonstrate that the proposed estimation model performs well and the saving technique is the best among the three heuristics.

A novel genetic algorithm for vehicle routing problem with time windows

A novel genetic algorithm with multiple species in dynamic region is proposed,each of which occupies a dynamic region determined by the weight vector of a fuzzy adaptive Hamming neural network. Through learning and classification of genetic individuals in the evolutionary procedure,the neural network distributes multiple species into different regions of the search space. Furthermore,the neural network dynamically expands each search region or establishes new region for good offspring individuals to continuously keep the diversification of the genetic population. As a result,the premature problem inherent in genetic algorithm is alleviated and better tradeoff between the ability of exploration and exploitation can be obtained. The experimental results on the vehicle routing problem with time windows also show the good performance of the proposed genetic algorithm.

A Hybrid TCNN Optimization Approach for the Capacity Vehicle Routing Problem

A novel approximation algorithm was proposed for the problem of finding the minimum total cost of all routes in Capacity Vehicle Routing Problem (CVRP). CVRP can be partitioned into three parts: the selection of vehicles among the available vehicles, the initial routing of the selected fleet and the routing optimization. Fuzzy C-means (FCM) can group the customers with close Euclidean distance into the same vehicle according to the principle of similar feature partition. Transiently chaotic neural network (TCNN) combines local search and global search, possessing high search efficiency. It will solve the routes to near optimality. A simple tabu search (TS) procedure can improve the routes to more optimality. The computations on benchmark problems and comparisons with other results in literatures show that the proposed algorithm is a viable and effective approach for CVRP.

An Effective Hybrid Optimization Algorithm for Capacitated Vehicle Routing Problem

Capacitated vehicle routing problem (CVRP) is an important combinatorial optimization problem. However, it is quite difficult to achieve an optimal solution with the traditional optimization methods owing to the high computational complexity. A hybrid algorithm was developed to solve the problem, in which an artificial immune clonal algorithm (AICA) makes use of the global search ability to search the optimal results and simulated annealing (SA) algorithm employs certain probability to avoid becoming trapped in a local optimum. The results obtained from the computational study show that the proposed algorithm is a feasible and effective method for capacitated vehicle routing problem.

Intelligent Iterated Local Search Methods for Solving Vehicle Routing Problem with Different Fleets

To solve vehicle routing problem with different fleets, two methodologies are developed. The first methodology adopts twophase strategy. In the first phase, the improved savings method is used to assign customers to appropriate vehicles. In the second phase, the iterated dynasearch algorithm is adopted to route each selected vehicle with the assigned customers. The iterated dynasearch algorithm combines dynasearch algorithm with iterated local search algorithm based on random kicks. The second methodplogy adopts the idea of cyclic transfer which is performed by using dynamic programming algorithm, and the iterated dynasearch algorithm is also embedded in it. The test results show that both methodologies generate better solutions than the traditional method, and the second methodology is superior to the first one.

Overview of Stochastic Vehicle Routing Problems

Stochastic vehicle routing problems ( VRPs) play important roles in logistics, though they have not been studied systematically yet. The paper summaries the definition, properties and classification of stochastic VRPs, makes further discussion about two strategies in stochastic VRPs, and at last overviews dynamic and stochastic VRPs.

A Bi-Objective Green Vehicle Routing Problem: A New Hybrid Optimization Algorithm Applied to a Newspaper Distribution

The purpose of this work is to present a methodology to provide a solution to a Bi-objective Green Vehicle Routing Problem (BGVRP). The methodology, illustrated using a case study (newspaper distribution problem) and literature Instances, was divided into three stages: Stage 1, data treatment;Stage 2, “metaheuristic approaches” (hybrid or non-hybrid), used comparatively, more specifically: NSGA-II (Non-dominated Sorting Genetic Algorithm II), MOPSO (Multi-Objective Particle Swarm Optimization), which were compared with the new approaches proposed by the authors, CWNSGA-II (Clarke and Wright’s Savings with the Non-dominated Sorting Genetic Algorithm II) and CWTSNSGA-II (Clarke and Wright’s Savings, Tabu Search and Non-dominated Sorting Genetic Algorithm II);Stage 3, analysis of the results, with a comparison of the algorithms. An optimization of 19.9% was achieved for Objective Function 1 (OF1;minimization of CO2 emissions) and consequently the same percentage for the minimization of total distance, and 87.5% for Objective Function 2 (OF2;minimization of the difference in demand). Metaheuristic approaches hybrid achieved superior results for case study and instances. In this way, the procedure presented here can bring benefits to society as it considers environmental issues and also balancing work between the routes, ensuring savings and satisfaction for the users.

A Hybrid Genetic Algorithm for Vehicle Routing Problem with Complex Constraints

Most research on the Vehicle Routing Problem （VRP） is focused on standard conditions, which is not suitable for specific cases. A Hybrid Genetic Algorithm is proposed to solve a Vehicle Routing Problem （VRP） with complex side constraints. A novel coding method is designed especially for side constraints. A greedy algorithm combined with a random algorithm is introduced to enable the diversity of the initial population, as well as a local optimization algorithm employed to improve the searching efficiency. In order to evaluate the performance, this mechanism has been implemented in an oil distribution center, the experimental and executing results show that the near global optimal solution can be easily and quickly obtained by this method, and the solution is definitely satisfactory in the VRP application.

A multi-agent deep reinforcement learning approach for solving the multi-depot vehicle routing problem

The multi-depot vehicle routing problem(MDVRP)is one of the most essential and useful variants of the traditional vehicle routing problem(VRP)in supply chain management(SCM)and logistics studies.Many supply chains(SC)choose the joint distribution of multiple depots to cut transportation costs and delivery times.However,the ability to deliver quality and fast solutions for MDVRP remains a challenging task.Traditional optimization approaches in operation research(OR)may not be practical to solve MDVRP in real-time.With the latest developments in artificial intelligence(AI),it becomes feasible to apply deep reinforcement learning(DRL)for solving combinatorial routing problems.This paper proposes a new multi-agent deep reinforcement learning(MADRL)model to solve MDVRP.Extensive experiments are conducted to evaluate the performance of the proposed approach.Results show that the developed MADRL model can rapidly capture relative information embedded in graphs and effectively produce quality solutions in real-time.

Spatiotemporal distance embedded hybrid ant colony algorithm for a kind of vehicle routing problem with constraints

We investigate a kind of vehicle routing problem with constraints(VRPC)in the car-sharing mobility environment,where the problem is based on user orders,and each order has a reservation time limit and two location point transitions,origin and destination.It is a typical extended vehicle routing problem(VRP)with both time and space constraints.We consider the VRPC problem characteristics and establish a vehicle scheduling model to minimize operating costs and maximize user(or passenger)experience.To solve the scheduling model more accurately,a spatiotemporal distance representation function is defined based on the temporal and spatial properties of the customer,and a spatiotemporal distance embedded hybrid ant colony algorithm(HACA-ST)is proposed.The algorithm can be divided into two stages.First,through spatiotemporal clustering,the spatiotemporal distance between users is the main measure used to classify customers in categories,which helps provide heuristic information for problem solving.Second,an improved ant colony algorithm(ACO)is proposed to optimize the solution by combining a labor division strategy and the spatiotemporal distance function to obtain the final scheduling route.Computational analysis is carried out based on existing data sets and simulated urban instances.Compared with other heuristic algorithms,HACA-ST reduces the length of the shortest route by 2%–14%in benchmark instances.In VRPC testing instances,concerning the combined cost,HACA-ST has competitive cost compared to existing VRP-related algorithms.Finally,we provide two actual urban scenarios to further verify the effectiveness of the proposed algorithm.

Solving vehicle routing problem with time windows using metaheuristic approaches

Purpose-Drugs are strategic products with essential functions in human health.An optimum design of the pharmaceutical supply chain is critical to avoid economic damage and adverse effects on human health.The vehicle-routing problem,focused on finding the lowest-cost routes with available vehicles and constraints,such as time constraints and road length,is an important aspect of this.In this paper,the vehicle routing problem(VRP)for a pharmaceutical company in Turkey is discussed.Design/methodology/approach-A mixed-integer programming(MIP)model based on the vehicle routing problem with time windows(VRPTW)is presented,aiming to minimize the total route cost with certain constraints.As the model provides an optimum solution for small problem sizes with the GUROBI®solver,for large problem sizes,metaheuristic methods that simulate annealing and adaptive large neighborhood search algorithms are proposed.A real dataset was used to analyze the effectiveness of the metaheuristic algorithms.The proposed simulated annealing(SA)and adaptive large neighborhood search(ALNS)were evaluated and compared against GUROBI®and each other through a set of real problem instances.Findings-The model is solved optimally for a small-sized dataset with exact algorithms;for solving a larger dataset,however,metaheuristic algorithms require significantly lesser time.For the problem addressed in this study,while the metaheuristic algorithms obtained the optimum solution in less than one minute,the solution in the GUROBI®solver was limited to one hour and three hours,and no solution could be obtained in this time interval.Originality/value-The VRPTW problem presented in this paper is a real-life problem.The vehicle fleet owned by the factory cannot be transported between certain suppliers,which complicates the solution of the problem.

Three-stage algorithms for the large-scale dynamic vehicle routing problem with industry 4.0 approach

Companies are eager to have a smart supply chain especially when they have adynamic system. Industry 4.0 is a concept which concentrates on mobility andreal-time integration. Thus, it can be considered as a necessary component thathas to be implemented for a dynamic vehicle routing problem. The aim of thisresearch is to solve large-scale DVRP (LSDVRP) in which the delivery vehiclesmust serve customer demands from a common depot to minimize transit costswhile not exceeding the capacity constraint of each vehicle. In LSDVRP, it isdifficult to get an exact solution and the computational time complexity growsexponentially. To find near-optimal answers for this problem, a hierarchicalapproach consisting of three stages: “clustering, route-construction, routeimprovement”is proposed. The major contribution of this paper is dealing withLSDVRP to propose the three-stage algorithm with better results. The resultsconfirmed that the proposed methodology is applicable.