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 ...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.展开更多
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 fol...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 CO<sub>2</sub> 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 CO<sub>2</sub> by almost 7.2% compared to the worst route.展开更多
Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a ...Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a mathematical model for multi-depot heterogeneous vehicle routing problem with soft time windows （MDHVRPSTW） is established. An improved ant colony optimization （IACO） is proposed for solving this model. First, MDHVRPSTW is transferred into different groups according to the nearest principle, and then the initial route is constructed by the scanning algorithm （SA）. Secondly, genetic operators are introduced, and crossover probability and mutation probability are adaptively adjusted in order to improve the global search ability of the algorithm. Moreover, the smooth mechanism is used to improve the performance of the ant colony optimization （ACO）. Finally, the 3-opt strategy is used to improve the local search ability. The proposed IACO was tested on three new instances that were generated randomly. The experimental results show that IACO is superior to the other three existing algorithms in terms of convergence speed and solution quality. Thus, the proposed method is effective and feasible, and the proposed model is meaningful.展开更多
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 friendl...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.展开更多
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） algorithm...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.展开更多
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 contribute...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.展开更多
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 mode...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.展开更多
As a new variant of vehicle routing problem( VRP),a finished vehicle routing problem with time windows in finished vehicle logistics( FVRPTW) is modeled and solved. An optimization model for FVRPTW is presented with t...As a new variant of vehicle routing problem( VRP),a finished vehicle routing problem with time windows in finished vehicle logistics( FVRPTW) is modeled and solved. An optimization model for FVRPTW is presented with the objective of scheduling multiple transport routes considering loading constraints along with time penalty function to minimize the total cost. Then a genetic algorithm( GA) is developed. The specific encoding and genetic operators for FVRPTW are devised.Especially,in order to accelerate its convergence,an improved termination condition is given. Finally,a case study is used to evaluate the effectiveness of the proposed algorithm and a series of experiments are conducted over a set of finished vehicle routing problems. The results demonstrate that the proposed approach has superior performance and satisfies users in practice. Contributions of the study are the modeling and solving of a complex FVRPTW in logistics industry.展开更多
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 so...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.展开更多
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 ...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 ( 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 pr...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 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 cl...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 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 vehic...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.展开更多
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 ...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.展开更多
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 a...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.展开更多
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...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.展开更多
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 ...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 (OF<sub>1</sub>;minimization of CO<sub>2</sub> emissions) and consequently the same percentage for the minimization of total distance, and 87.5% for Objective Function 2 (OF<sub>2</sub>;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.展开更多
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 ...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.展开更多
To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,...To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.展开更多
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 poi...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.展开更多
基金the Deanship of Scientific Research at Imam Mohammad Ibn Saud Islamic University for funding thiswork through Research Group No.RG-21-09-17.
文摘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.
文摘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 CO<sub>2</sub> 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 CO<sub>2</sub> by almost 7.2% compared to the worst route.
基金The National Natural Science Foundation of China(No.61074147)the Natural Science Foundation of Guangdong Province(No.S2011010005059)+2 种基金the Foundation of Enterprise-University-Research Institute Cooperation from Guangdong Province and Ministry of Education of China(No.2012B091000171,2011B090400460)the Science and Technology Program of Guangdong Province(No.2012B050600028)the Science and Technology Program of Huadu District,Guangzhou(No.HD14ZD001)
文摘Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a mathematical model for multi-depot heterogeneous vehicle routing problem with soft time windows （MDHVRPSTW） is established. An improved ant colony optimization （IACO） is proposed for solving this model. First, MDHVRPSTW is transferred into different groups according to the nearest principle, and then the initial route is constructed by the scanning algorithm （SA）. Secondly, genetic operators are introduced, and crossover probability and mutation probability are adaptively adjusted in order to improve the global search ability of the algorithm. Moreover, the smooth mechanism is used to improve the performance of the ant colony optimization （ACO）. Finally, the 3-opt strategy is used to improve the local search ability. The proposed IACO was tested on three new instances that were generated randomly. The experimental results show that IACO is superior to the other three existing algorithms in terms of convergence speed and solution quality. Thus, the proposed method is effective and feasible, and the proposed model is meaningful.
基金supported by the National Natural Science Foundation of China(71571076)the National Key R&D Program for the 13th-Five-Year-Plan of China(2018YFF0300301).
文摘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.
文摘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.
文摘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.
基金supported by National Natural Science Foundation of China (No.60474059)Hi-tech Research and Development Program of China (863 Program,No.2006AA04Z160).
文摘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.
基金Supported by the National Natural Science Foundation of China(No.51565036)
文摘As a new variant of vehicle routing problem( VRP),a finished vehicle routing problem with time windows in finished vehicle logistics( FVRPTW) is modeled and solved. An optimization model for FVRPTW is presented with the objective of scheduling multiple transport routes considering loading constraints along with time penalty function to minimize the total cost. Then a genetic algorithm( GA) is developed. The specific encoding and genetic operators for FVRPTW are devised.Especially,in order to accelerate its convergence,an improved termination condition is given. Finally,a case study is used to evaluate the effectiveness of the proposed algorithm and a series of experiments are conducted over a set of finished vehicle routing problems. The results demonstrate that the proposed approach has superior performance and satisfies users in practice. Contributions of the study are the modeling and solving of a complex FVRPTW in logistics industry.
基金This work was supported by the National Natural Science Foundation of China(61772196,61472136)the Hunan Provincial Focus Social Science Fund(2016ZDB006)Thanks to Professor Weijin Jiang for his guidance and suggestions on this research.Funding Statement。
文摘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.
文摘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 ( 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 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 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.
文摘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.
基金The National Natural Science Founda-tion of China ( No.70471039)the National Social Science Foundation of China (No.07BJY038)the Program for New Century Excellent Talents in University (No.NCET-04-0886)
文摘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.
基金Supported by the National Natural Science Fundation of China( No. 70071028 and 79700019).
文摘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.
文摘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 (OF<sub>1</sub>;minimization of CO<sub>2</sub> emissions) and consequently the same percentage for the minimization of total distance, and 87.5% for Objective Function 2 (OF<sub>2</sub>;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.
基金This paper is supported by High-Tech Research and Development Program of China (Grant No. 2003AA001048) Young Teacher Foundation of School of Electronics and Information Engineering of Xi'an Jiaotong Univeristy.
文摘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.
基金supported by Natural Science Foundation Project of Gansu Provincial Science and Technology Department(No.1506RJZA084)Gansu Provincial Education Department Scientific Research Fund Grant Project(No.1204-13).
文摘To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.
基金Project supported by the National Science and Technology Innovation 2030 Major Project of the Ministry of Science and Technology of China(No.2018AAA0101200)。
文摘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.
