You Can Charge over the Road: Optimizing Charging Tour in Urban Area

摘要

Wireless energy transfer has provided a promising technology to extend the lifetime of wireless rechargeable sensor network. Most of previous studies focus on scheduling chargers or deploying stationary charging stations to replenish energy for rechargeable sensors. These methods could not be applicable when real deployment is concerned, because the roadway needs to be fully respected for mobile chargers in typical urban area. In dealing with this difficulty, we investigate the problem of scheduling mobile chargers with mobility constraints in the scenario of a city graph. First of all, we aim at optimizing the traveling path for chargers to minimize the traveling cost. Consequently, we convert our scheduling problem into edge coverage problem, which is quite different from the point coverage problem. Then classical problem CARP (Capacitated Arc Routing Problem), which has been proved NP-hard, is applied to solve aforementioned problem. To this end, a simple but efficient genetic algorithm cooperated with decoding algorithm Split is proposed. Finally, we evaluate the impacts of different parameters on our algorithm and get the near optimal solution.