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.

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.

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.

Software Defined Networking Based On-Demand Routing Protocol in Vehicle Ad-Hoc Networks

This paper comes up with a SDN Based Vehicle Ad-Hoc On-Demand Routing Protocol(SVAO),which separates the data forwarding layer and network control layer,as in software defined networking(SDN),to enhance data transmission efficiency within vehicle ad-hoc networks(VANETs).The roadside service unit plays the role of local controller and is in charge of selecting vehicles to forward packets within a road segment.All the vehicles state in the road.Correspondingly,a two-level design is used.The global level is distributed and adopts a ranked query scheme to collect vehicle information and determine the road segments along which a message should be forwarded.On the other hand,the local level is in charge of selecting forwarding vehicles in each road segment determined by the global level.We implement two routing algorithms of SVAO,and compare their performance in our simulation.We compare SVAO with popular ad-hoc network routing protocols,including Optimized Link State Routing(OLSR),Dynamic Source Routing(DSR),Destination Sequence Distance Vector(DSDV),and distance-based routing protocol(DB)via simulations.We consider the impact of vehicle density,speed on data transmission rate and average packet delay.The simulation results show that SVAO performs better than the others in large-scale networks or with high vehicle speeds.

The Information Modeling and Intelligent Optimization Method for Logistics Vehicle Routing and Scheduling with Multi-objective and Multi-constraint

The vehicle routing and scheduling (VRS) problem with multi-objective and multi-constraint is analyzed, considering the complexity of the modern logistics in city economy and daily life based on the system engineering. The objective and constraint includes loading, the dispatch and arrival time, transportation conditions,total cost,etc. An information model and a mathematical model are built,and a method based on knowledge and biologic immunity is put forward for optimizing and evaluating the programs dimensions in vehicle routing and scheduling with multi-objective and multi-constraints. The proposed model and method are illustrated in a case study concerning a transport network, and the result shows that more optimization solutions can be easily obtained and the method is efficient and feasible. Comparing with the standard GA and the standard GA without time constraint,the computational time of the algorithm is less in this paper. And the probability of gaining optimal solution is bigger and the result is better under the condition of multi-constraint.

Dynamic Routing for Emergency Vehicle by Collecting Real-Time Road Conditions

When a natural disaster such as earthquake strikes, people go away to safety areas by cars. Some roads are broken and impenetrable by buildings falling down. Furthermore, some fixed infrastructures for radio communication may be broken. In order to quickly bring ambulances and fire trucks to their destinations, it is necessary to provide real-time road conditions to these emergency vehicles via ad-hoc networks. In this paper, we propose a method to periodically reconstruct a route for an emergency vehicle by collecting real-time road conditions via vehicle ad-hoc networks. As simulation results, we confirmed that the proposed method collects 12% more road conditions than existing method. We also confirmed that the proposed method achieves 10% faster arrival than the existing method.

Vehicle Routing Problem with Non-Full Loadof Less Freight Quantity

Freight quantity is usually less than the half of vehicle capacity,and the effectiveness of transportation utilizing a single vehicle is not satisfactory enough. In this paper,a sequential heuristic algorithm is presented, whichconsists of clustering and chaining. Lastly, the method is applied to a casestudy.

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.