Vehicle routing optimization algorithm based on time windows and dynamic demand

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.

Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management

Technological advancements in unmanned aerial vehicles(UAVs)have revolutionized various industries,enabling the widespread adoption of UAV-based solutions.In engineering management,UAV-based inspection has emerged as a highly efficient method for identifying hidden risks in high-risk construction environments,surpassing traditional inspection techniques.Building on this foundation,this paper delves into the optimization of UAV inspection routing and scheduling,addressing the complexity introduced by factors such as no-fly zones,monitoring-interval time windows,and multiple monitoring rounds.To tackle this challenging problem,we propose a mixed-integer linear programming(MILP)model that optimizes inspection task assignments,monitoring sequence schedules,and charging decisions.The comprehensive consideration of these factors differentiates our problem from conventional vehicle routing problem(VRP),leading to a mathematically intractable model for commercial solvers in the case of large-scale instances.To overcome this limitation,we design a tailored variable neighborhood search(VNS)metaheuristic,customizing the algorithm to efficiently solve our model.Extensive numerical experiments are conducted to validate the efficacy of our proposed algorithm,demonstrating its scalability for both large-scale and real-scale instances.Sensitivity experiments and a case study based on an actual engineering project are also conducted,providing valuable insights for engineering managers to enhance inspection work efficiency.

The evolution of the cold chain logistics vehicle routing problem:a bibliometric and visualization revie

This paper uses the bibliometric analysis software CiteSpace to examine the current status and evolution of cold-chain logistics vehicle routing problems(CCVRP).7381 relevant articles published in the Web of Science core collection from 2008 to 2024 were analyzed,an in-depth understanding of the publication trends and category distribution were gained.Subsequently,CiteSpace was used to create a scientific knowledge graph and perform visualization analysis.The analysis includes collaboration among authors,countries,and institutions;co-citation analysis of authors,journals,and references;citation burst detection of keywords;and co-citation cluster analysis of references.Based on a deep understanding of current research hotspots,an in-depth discussion of existing research was conducted from three perspectives:optimization objectives,distribution scenarios,and solution algorithms.The results show that CCVRP involves complex factors such as temperature requirements,time window constraints,and multi-objective optimization.These intricate constraints are causing research to become increasingly interdisciplinary and comprehensive.The evolution of hot topics shows that the research directions span multiple fields,from algorithm design to logistics management.This review helps researchers better understand the history,current status,and future development directions of CCVRP research,and provides valuable references and inspiration for academia and practice.

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.

Coati Optimization-Based Energy Efficient Routing Protocol for Unmanned Aerial Vehicle Communication

With the flexible deployment and high mobility of Unmanned Aerial Vehicles(UAVs)in an open environment,they have generated con-siderable attention in military and civil applications intending to enable ubiquitous connectivity and foster agile communications.The difficulty stems from features other than mobile ad-hoc network(MANET),namely aerial mobility in three-dimensional space and often changing topology.In the UAV network,a single node serves as a forwarding,transmitting,and receiving node at the same time.Typically,the communication path is multi-hop,and routing significantly affects the network’s performance.A lot of effort should be invested in performance analysis for selecting the optimum routing system.With this motivation,this study modelled a new Coati Optimization Algorithm-based Energy-Efficient Routing Process for Unmanned Aerial Vehicle Communication(COAER-UAVC)technique.The presented COAER-UAVC technique establishes effective routes for communication between the UAVs.It is primarily based on the coati characteristics in nature:if attacking and hunting iguanas and escaping from predators.Besides,the presented COAER-UAVC technique concentrates on the design of fitness functions to minimize energy utilization and communication delay.A varied group of simulations was performed to depict the optimum performance of the COAER-UAVC system.The experimental results verified that the COAER-UAVC technique had assured improved performance over other approaches.

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.

Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows

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.

Joint mission and route planning of unmanned air vehicles via a learning-based heuristic

Unmanned air vehicles(UAVs) have been regularly employed in modern wars to conduct different missions. Instead of addressing mission planning and route planning separately,this study investigates the issue of joint mission and route planning for a fleet of UAVs. The mission planning determines the configuration of weapons in UAVs and the weapons to attack targets, while the route planning determines the UAV’s visiting sequence for the targets. The problem is formulated as an integer linear programming model. Due to the inefficiency of CPLEX on large scale optimization problems, an effective learningbased heuristic, namely, population based adaptive large neighborhood search(P-ALNS), is proposed to solve the model. In P-ALNS, seven neighborhood structures are designed and adaptively utilized in terms of their historical performance. The effectiveness and superiority of the proposed model and algorithm are demonstrated on test instances of small, medium and large sizes. In particular, P-ALNS achieves comparable solutions or as good as those of CPLEX on small-size(20 targets)instances in much shorter time.

Application Research of an Intelligent Detection Algorithm for Vehicle Trajectory Route Deviation

In the vehicle trajectory application system, it is often necessary to detect whether the vehicle deviates from the specified route. Trajectory planning in the traditional route deviation detection is defined by the driver through the mobile phone navigation software, which plays a more auxiliary driving role. This paper presents a method of vehicle trajectory deviation detection. Firstly, the manager customizes the trajectory planning and then uses big data technologies to match the deviation between the trajectory planning and the vehicle trajectory. Finally, it achieves the supervisory function of the manager on the vehicle track route in real-time. The results show that this method could detect the vehicle trajectory deviation quickly and accurately, and has practical application value.

A Memetic Algorithm With Competition for the Capacitated Green Vehicle Routing Problem

In this paper, a memetic algorithm with competition(MAC) is proposed to solve the capacitated green vehicle routing problem(CGVRP). Firstly, the permutation array called traveling salesman problem(TSP) route is used to encode the solution, and an effective decoding method to construct the CGVRP route is presented accordingly. Secondly, the k-nearest neighbor(k NN) based initialization is presented to take use of the location information of the customers. Thirdly, according to the characteristics of the CGVRP, the search operators in the variable neighborhood search(VNS) framework and the simulated annealing(SA) strategy are executed on the TSP route for all solutions. Moreover, the customer adjustment operator and the alternative fuel station(AFS) adjustment operator on the CGVRP route are executed for the elite solutions after competition. In addition, the crossover operator is employed to share information among different solutions. The effect of parameter setting is investigated using the Taguchi method of design-ofexperiment to suggest suitable values. Via numerical tests, it demonstrates the effectiveness of both the competitive search and the decoding method. Moreover, extensive comparative results show that the proposed algorithm is more effective and efficient than the existing methods in solving the CGVRP.

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.

A Survey on the Vehicle Routing Problem and Its Variants

In this paper, we have conducted a literature review on the recent developments and publications involving the vehicle routing problem and its variants, namely vehicle routing problem with time windows (VRPTW) and the capacitated vehicle routing problem (CVRP) and also their variants. The VRP is classified as an NP-hard problem. Hence, the use of exact optimization methods may be difficult to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. The vehicle routing problem comes under combinatorial problem. Hence, to get solutions in determining routes which are realistic and very close to the optimal solution, we use heuristics and meta-heuristics. In this paper we discuss the various exact methods and the heuristics and meta-heuristics used to solve the VRP and its variants.

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 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.

A Genetic Algorithm for the Split Delivery Vehicle Routing Problem

The Split Delivery Vehicle Routing Problem (SDVRP) allows customers to be assigned to multiple routes. Two hybrid genetic algorithms are developed for the SDVRP and computational results are given for thirty-two data sets from previous literature. With respect to the total travel distance and computer time, the genetic algorithm compares favorably versus a column generation method and a two-phase method.

A Construction Heuristic for the Split Delivery Vehicle Routing Problem

The Split Delivery Vehicle Routing Problem (SDVRP) is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) where customers may be assigned to multiple routes. A new construction heuristic is developed for the SDVRP and computational results are given for thirty-two data sets from previous literature. With respect to the total travel distance, the construction heuristic compares favorably versus a column generation method and a two-phase method. In addition, the construction heuristic is computationally faster than both previous methods. This construction heuristic could be useful in developing initial solutions, very quickly, for a heuristic, algorithm, or exact procedure.

A GA approach to vehicle routing problem with time windows considering loading constraints

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.

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.

Development of an Efficient Genetic Algorithm for the Time Dependent Vehicle Routing Problem with Time Windows

This research considers the time-dependent vehicle routing problem (TDVRP). The time-dependent VRP does not assume constant speeds of the vehicles. The speeds of the vehicles vary during the various times of the day, based on the traffic conditions. During the periods of peak traffic hours, the vehicles travel at low speeds and during non-peak hours, the vehicles travel at higher speeds. A survey by TCI and IIM-C (2014) found that stoppage delay as percentage of journey time varied between five percent and 25 percent, and was very much dependent on the characteristics of routes. Costs of delay were also estimated and found not to affect margins by significant amounts. This study aims to overcome such problems arising out of traffic congestions that lead to unnecessary delays and hence, loss in customers and thereby valuable revenues to a company. This study suggests alternative routes to minimize travel times and travel distance, assuming a congestion in traffic situation. In this study, an efficient GA-based algorithm has been developed for the TDVRP, to minimize the total distance travelled, minimize the total number of vehicles utilized and also suggest alternative routes for congestion avoidance. This study will help to overcome and minimize the negative effects due to heavy traffic congestions and delays in customer service. The proposed algorithm has been shown to be superior to another existing algorithm in terms of the total distance travelled and also the number of vehicles utilized. Also the performance of the proposed algorithm is as good as the mathematical model for small size problems.

A Time-Dependent Vehicle Routing Problem with Time Windows for E-Commerce Supplier Site Pickups Using Genetic Algorithm

The VRP is classified as an NP-hard problem. Hence exact optimization methods may be difficult to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. To get solutions in determining routes which are realistic and very close to the actual solution, we use heuristics and metaheuristics which are of the combinatorial optimization type. A literature review of VRPTW, TDVRP, and a metaheuristic such as the genetic algorithm was conducted. In this paper, the implementation of the VRPTW and its extension, the time-dependent VRPTW (TDVRPTW) has been carried out using the model as well as metaheuristics such as the genetic algorithm (GA). The algorithms were implemented, using Matlab and HeuristicLab optimization software. A plugin was developed using Visual C# and DOT NET framework 4.5. Results were tested using Solomon’s 56 benchmark instances classified into groups such as C1, C2, R1, R2, RC1, RC2, with 100 customer nodes, 25 vehicles and each vehicle capacity of 200. The results were comparable to the earlier algorithms developed and in some cases the current algorithm yielded better results in terms of total distance travelled and the average number of vehicles used.