论文标题
电动汽车旅行推销员问题与固定时间充满电政策有关
Electric Vehicle Traveling Salesman Problem with Drone with Fixed-time-full-charge Policy
论文作者
论文摘要
在过去几年中，部署电动汽车和无人驾驶汽车（也称为无人机）的想法引起了越来越多的关注。在本文中，我们提出了无人机（EVTSPD）的电动汽车旅行人员问题，其中电动汽车（EV）和无人机协调执行送货任务，而电动汽车可能需要偶尔访问充电站以充电。我们进一步假设电动汽车在充电站的固定时间内可以将其能量刷新为全电池容量。因此，提出的问题称为EVTSPD-FF。在本文中，为EVTSPD-FF提出了基于ARC的混合智能编程模型。开发了一种确切的分支机构（BP）算法和可变的邻里搜索启发式，以解决一分钟内最多25个客户的实例。数值实验表明，使用ILOG CPLEX求解器和BP算法求解基于ARC的模型的启发式效率要高得多。还对奥斯汀网络进行了真实的案例研究以及对不同参数的灵敏度分析。结果表明，与EV的驾驶范围相比，无人机速度对交付时间具有更大的影响。
The idea of deploying electric vehicles and unmanned aerial vehicles (UAVs), also known as drones, to perform "last-mile" delivery in logistics operations has attracted increasing attention in the past few years. In this paper, we propose the electric vehicle traveling salesman problem with drone (EVTSPD), in which the electric vehicle (EV) and the drone perform delivery tasks coordinately while the electric vehicle may need to visit charging stations occasionally to recharge. We further assume that the EV can refresh its energy to full battery capacity with fixed time at charging stations. Thus, the proposed problem is termed EVTSPD-FF. In this paper, an arc-based mixed-integer programming model defined in a multigraph is presented for EVTSPD-FF. An exact branch-and-price (BP) algorithm and a variable neighborhood search heuristic are developed to solve instances with up to 25 customers in one minute. Numerical experiments show that the heuristic is much more efficient than solving the arc-based model using the ILOG CPLEX solver and BP algorithm. A real-world case study on the Austin network and the sensitivity analysis of different parameters are also conducted and presented. The results indicate that drone speed has a more significant effect on delivery time than the EV's driving range.
