Team Orienteering Pickup and Delivery Problem with Electric Vehicles and Pickup-point Selection
Electric vehicles are widely used in logistics distribution as the government pays more and more atten-tion to green logistics.Offline physical chain stores expand online channels to reach more consumers.Consumers place orders online and stores conduct offline delivery of goods.Under the consumption model of integrating online e-commerce and offline stores,the logistics delivery providers need to select a pickup point from several stores to pick up the goods and then deliver them to the customers.And in actual logistics distribution,there are often situations where delivery resources are insufficient or delivery to certain customers is uneconomical.Logis-tics delivery providers can only provide services for some delivery requests to obtain maximum profits.If there are resource constraints,which customers should be selected to join the delivery route is exactly what the team orien-teering problem is studying.Therefore,focusing on the situation that each request has multiple selectable pickup points and distribution resources are insufficient,this paper studies a team orienteering pickup and delivery problem with electric vehicles and pickup-point selection(TOPDP-EVPS).A mixed integer programming model is formulated for the first time for the problem in which a decision varia-ble is used to model the pickup point selection.In this model,it is not necessary to satisfy all delivery requests and the objective is maximizing the total amount of profit collected by the electric vehicles while not exceeding a predefined number of vehicles and the maximum time limit on each vehicle.Since this model combines the formulation of the pickup and delivery problem and team orienteering problem and add the decision variable of pickup point selection,it becomes hard for exact algorithm to solve it within an acceptable time range.Due to the complexity of this model,an improved adaptive large neighborhood search algorithm(IALNS)is designed to solve this problem.This algorithm combines taboo strategy and the ideal of simulated annealing to avoid getting stuck in local optimal solution too early,and at the same time multiple destroy operators and repair operators are designed for charging stations and request nodes which combines some classical operators proposed in the litera-ture and two new operators especially designed for the first time,namely,a greedy random repair operator and a minimum spanning tree destroy operator,to improve the performance of the algorithm.In order to demonstrate the correctness of the TOPDP-EVPS model and the effectiveness of the IALNS algo-rithm in solving this problem,a number of numerical experiments are conducted.The test instances are generated based on the existing instances of pickup and delivery problem with electric vehicles,adding several pickup points on the basis of the original pickup point at each delivery point to form their corresponding collection of pickup points.At the same time,resource constraints are added on the number of vehicles and the maximum path time for each instance.After comparing the experimental result of 36 small-scale instances of TOPDP-EVPS problem gotten by CPLEX solver and IALNS algorithm,we find that the profit of solutions of 13 instances obtained by IALNS algorithm are better than that sought by CPLEX.For the remaining 23 instances,the solu-tions obtained by IALNS algorithm are the same as CPLEX,while in terms of solving time,IALNS is much lower than CPLEX,which indicates that IALNS can ensure both solution quality and solution speed at the same time.Furthermore,the influence of pickup-point selection on the total profit is analyzed by comparative experiments.The experimental result of large-scale instances shows that IALNS algorithm can stably and effectively solve instances of three distribution types.And the average total profit of the obtained solutions of the instances with pickup point selection increases by 11.28%,14.75%,and 14.47%compared to those without pickup point selection,respectively.At last,we evaluate the effectiveness of these two new operators proposed in the algorithm.Through comparative experiment,we find that with the contribution of new operators,the average total profit of the obtained solution of the three kinds of large-scale instance increases by 0.97%,0.97%and 1.03%,respectively.In the future,on the basis of this problem,further research can be carried out by considering the condition that the distribution requests have time windows,as well as the nonlinear charging and power consumption of electric vehicles,in order to solve the logistics and distribution problems that are more relevant to the real world.
electric vehiclepickup-point selectionpickup and delivery problemteam orienteering problemadaptive large neighbourhood search algorithm
万方数据
维普
