有取货点选择的电动车集送货团队定向问题研究

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 attention 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.Logistics 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 orienteering 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 variable 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 literature 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 algorithm 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 solutions 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.