Routing Scheduling for Valet-charging Service with Self-operating and Third-party Charging Stations

Many electric vehicle (EV) companies have begun providing energy replenishment services to EV owners. Valet-charging is one such service where valet-staff are dispatched to substitute for EV owners in charging their EVs. This paper considers a routing scheduling problem for the service. We explore the charging options available at both the service provider’s self-operating charging stations and third-party charging stations. We formulate the problem via a robust optimization framework to capture the uncertain waiting time at the third-party stations. A Partial-Branch-and-Price algorithm (PB&B) is designed to solve the problem to optimal efficiently for large scales. Specifically, we innovatively proposed acceleration methods to speed up our extended robust labelling algorithm within the PB&B. We conduct a case study to show the effect of uncertainty in detail and provide investment suggestions for the firm’s investment on whether to contract a third-party charging station. © 2004-2012 IEEE.