Solving Multiobjective Vehicle Routing Problem With Stochastic Demand Via Learnable Evolution Model

Vehicle Routing Problem(VRP)is a classic combinatorial optimization problem in the field of computer science and operations research,which has been widely applied in the field of logistics.In a classic vehicle routing problem,a vehicle starts from a warehouse,carries a certain amount of goods,and then travels to a customer in a different location to deliver the goods.The goal of the problem is usually to determine a route planning solution that meets all the constraints and at the lowest cost.However,the multi-objective vehicle routing problem with stochastic demand(i.e.,multiobjective VRPSD)is more difficult to tackle than other traditional vehicle routing problems,due to the uncertainty in customer demands and conflict objectives.Each customer’s actual demand before the arrival of the actual vehicle customer location is not available,and the vehicle routing planning is determined in advance,so when the position of the vehicle to a customer,found the actual needs of customers more than its quantity of the goods carried by,this kind of situation is inevitable,which creates a "route failure" phenomenon.Although some multi-objective evolutionary algorithms have been proposed to solve this problem,the semi-blind and random optimizing operators usually mislead search process and increase computation time.In this paper,we present an improved learnable evolution model to solve multi-objective VRPSD.In particularly,a machine learning algorithm,i.e.,decision trees,helps to find and guide the desirable directions of evolution process.In order to apply the learning evolution model to solve the VRP problem,how to reasonably encode the candidate solutions and convert it into a chromosome that can be used as the input of machine learning algorithm is a crucial link,and this coding scheme can influence the success of the evolutionary model of learning.A new chromosome representation based on priority with bubbles is specifically designed to cope with the “route failure” issue caused by stochastic customer demands.An efficient nondominated sort using a sequential search strategy(ENS-SS)is adopted to handle the multi-objective property of the problem in conjunction with some heuristic operations.Due to the random nature of VRPSD problems,there is no standard benchmark data set to test the algorithm for such problems,so scholars usually use self-generated data test set to test the algorithm.Our algorithm is experimented on the instances of modified Solomon’s VRP benchmark.The results show that our algorithm is capable to find the pareto front of the solutions for the multiobjective VRPSD and competitive against other evolutionary algorithms.It also demonstrated that the learning-guided mechanism can improve the quality of the solution and efficiency of the computation of the evolutionary algorithm.