Tour-And-Charging Scheduler Based On (N+1) Traveling Salesman Problem Modeling
Tour-and-charging scheduling for DC chargers is modeledas (n+1) traveling salesman problem, where 1 out of m chargersis added to the set of n given destinations. To cope with the executiontime explosion according to the more deployment of chargers, thispaper designs a heuristic by which just a small set of chargersare investigated. To narrow the candidate set, our scheme sorts thedestinations according to the distance from the start point and thenpicks just a limited number of chargers closest to each destinationone by one. The restriction avoids the containment of candidateswithin a small area. The experiment result, obtained by means ofa prototype implementation on a real-life geographic distribution,reveals that the proposed scheme can find a solution comparable tothe optimal one with 5 candidates, the gap not larger than 2.7 % forthe given parameter setting.
Keywords � Electric Vehicle, DC Charger, Tour-and-Charging Schedule, Traveling Salesman Problem, Response Time.