Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows(EVRPTW+PR)

(1)当前方法：

• In this paper, we relax the full recharge restriction and allow partial recharging (EVRPTW-PR) which is more practical in the real world due to shorter recharging duration
• We formulate this problem as 0-1 mixed integer linear program and develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it efficiently.

(2)前人方法：

ALNS is based on the destroy-and-repair framework where at each iteration the existing feasible solution is destroyed by removing some customers and recharging stations from their routes and then repaired by inserting the removed customers to the solution along with stations when recharging is necessary.

Several removal and insertion algorithms are applied by selecting them dynamically and adaptively based on their past performances. The new solution is accepted according to the Simulated Annealing criterion.

Our approach combines the removal and insertion mechanisms presented in Ropke and Pisinger (2006a, 2006b), Pisinger and Ropke (2007) and Demir et al. (2012) with some new mechanisms designed specifically for EVRPTW and EVRPTW-PR.

(3)方法细节：

问题描述：

• Unlike EVRPTW where the vehicle departs from the depot/station with full battery and arrives at the depot/station with any state of charge, in EVRPTW-PR the vehicle departs from the depot/station at any state of charge and arrives at the depot/station with an empty battery.
• Since a recharging station may be visited more than once depending on the route structure, we create F′ which is the set of dummy vertices generated to permit several visits to each vertex in the set .

Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows(EVRPTW+PR)

原文：https://www.cnblogs.com/ezreal-/p/11605464.html