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.

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

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

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

An evolutionary algorithm approach for the constrained multi-depot vehicle routing problem

Purpose-The purpose of this paper is to explore a real world vehicle routing problem(VRP)that has multi-depot subcontractors with a heterogeneous fleet of vehicles that are available to pickup/deliver jobs with varying time windows and locations.Both the overall job completion time and number of drivers utilized are analyzed for the automated job allocations and manual job assignments from transportation field experts.Design/methodology/approach-A nested genetic algorithm(GA)is used to automate the job allocation process and minimize the overall time to deliver all jobs,while utilizing the fewest number of drivers-as a secondary objective.Findings-Three different real world data sets were used to compare the results of the GA vs transportation field experts’manual assignments.The job assignments from the GA improved the overall job completion time in 100 percent(30/30)of the cases and maintained the same or fewer drivers as BS Logistics(BSL)in 47 percent(14/30)of the cases.Originality/value-This paperprovidesa novel approach to solving a real world VRPthathasmultiple variants.While there have been numerous models to capture a select number of these variants,the value of this nested GA lies in its ability to incorporate multiple depots,a heterogeneous fleet of vehicles as well as varying pickup times,pickup locations,delivery times and delivery locations for each job into a single model.Existing research does not provide models to collectively address all of these variants.