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.

Genetic Crossover Operators for the Capacitated Vehicle Routing Problem

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

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

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

On Vehicle Routing Problems (VRP) with a Focus on Multiple Priorities

This paper discusses the concept of priorities based on Time and Quantity, which arise on the occasion of vehicle routing. It explains the interconnectivity between the priorities based on Time and Quantity and formulates a dynamic that shows the fusion of Time and Quantity into the Vehicle Routing Problem’s objective function. The paper focuses on the development of an expanded VRP objective function in which the priorities based on Time and Quantities are imbedded thus opens a vista of knowledge, aggregating and modelling the priorities as a mean to reduce transportation costs that lead to an organized and more timely deliveries of goods employing various of today’s proposed logistic systems coupled with widely used positioning systems.

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.

多策略改进的粒子群算法在VRPTW问题中的应用

该文研究带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),这是一个典型的NP-Hard问题。针对传统粒子群算法求解带时间窗约束的车辆路径问题容易陷入局部最优的缺陷,提出了一种基于多策略方法改进的粒子群算法(Multi-Strategy improved particle Swarm Optimization Algorithm,MSPSO)来解决该问题。该算法采用惯性权重递减策略,使得算法在前期的全局搜索和后期的局部搜索都能够有良好的表现,通过引入随机选择策略更新粒子最优位置,可以增加解空间的多样性,有效避免算法陷入局部最优。最后通过测试Solomon Benchmark算例的结果,在25个客户的C103数据集上MSPSO算法对比RWPSO算法的行驶距离降低了38.29,对比S-PSO算法在C103、R103这两个数据集与最优解误差分别降低了1.76%和3.99%。在50个客户C1系列数据集上MSPSO算法对比PSO算法行驶距离分别减少了14.26、45.66、67.7,与数据集的最优解误差基本能保持在1%以内。从实验结果可以证明MSPSO算法在求解VRPTW问题方面具有优越性和有效性。

DCS算法求解带软时间窗的送取货一体化VRP

为求解带软时间窗的送取货一体化车辆路径问题,提出一种离散布谷鸟(DCS)搜索算法。该算法在基本布谷鸟搜索算法基础之上,对莱维飞行获取新鸟巢和以一定概率抛弃鸟巢的迭代公式进行重新定义;同时设计客户序列和车辆序列双倍体鸟巢,并对客户序列采用交换、逆序、插入操作和对每辆车的访问路线采用2-Opt操作。通过5个算例的仿真实验和相关文献比较,结果表明所提DCS算法行之有效。

求解有服务顺序限制的MDMOVRPTW的IHHO算法

针对有服务顺序限制的带时间窗的多需求多目标车辆路径问题(multi-demand and multi-objective vehicle routing problem with time window,MDMOVRPTW),在考虑多种需求由不同车辆按顺序服务等约束条件的同时,构建了最小化配送成本和最大化客户满意度的多目标模型。根据模型的特点设计了改进的哈里斯鹰优化(improved Harris hawks optimization,IHHO)算法,随机地将种群中部分支配解作为父代解,用临时组合算子和4种交叉算子搜索新解。最后,算例测试结果表明,相较于传统的哈里斯鹰优化算法,IHHO算法的求解性能得到了有效改善,各操作算子中交叉算子2的求解效果最好。将IHHO算法用于实例中,求解结果得到了改善,充分验证了IHHO算法的有效性。

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.

混合多目标灰狼算法求解多目标VRPTW问题

针对带时间窗的多目标车辆路径规划问题,建立了最小化总成本和均衡度的多目标车辆路径优化模型,并提出了一种混合多目标灰狼算法进行求解。主要设计3点策略:(1)设计新的编码解码方式实现连续灰狼位置向量向离散客户序列的转化。(2)采用收敛性指标和分布性指标来进行决策个体的选择。(3)设计了多种删除、插入算子实施局部路径优化。为说明算法的有效性,以Solomon中的部分算例为例,将该算法与MOIGA和改进的ACO算法进行实验对比。实验结果表明,所提出的混合多目标灰狼算法能找到更好的Pareto解,并且性能优于其他进化算法。

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.

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

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.

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

Efficient Network Selection Using Multi-Depot Routing Problem for Smart Cities

Smart cities make use of a variety of smart technology to improve societies in better ways.Such intelligent technologies,on the other hand,pose sig-nificant concerns in terms of power usage and emission of carbons.The suggested study is focused on technological networks for big data-driven systems.With the support of software-defined technologies,a transportation-aided multicast routing system is suggested.By using public transportation as another communication platform in a smart city,network communication is enhanced.The primary objec-tive is to use as little energy as possible while delivering as much data as possible.The Attribute Decision Making with Capacitated Vehicle(CV)Routing Problem(RP)and Half Open Multi-Depot Heterogeneous Vehicle Routing Problem is used in the proposed research.For the optimum network selection,a Multi-Attribute Decision Making(MADM)method is utilized.For the sake of reducing energy usage,the Capacitated Vehicle Routing Problem(CVRP)is employed.To reduce the transportation cost and risk,Half Open Multi-Depot Heterogeneous Vehicle Routing Problem is used.Moreover,a mixed-integer programming approach is used to deal with the problem.To produce Pareto optimal solutions,an intelligent algorithm based on the epsilon constraint approach and genetic algorithm is cre-ated.A scenario of Auckland Transport is being used to validate the concept of offloading the information onto the buses for energy-efficient and delay-tolerant data transfer.Therefore the experiments have demonstrated that the buses may be used effectively to carry out the data by customer requests while using 30%of less energy than the other systems.