The performance of fleets of electric automated guided vehicles (AGVs) in intralogistics systems depends on good recharge strategies when making dispatching decisions. For fleets of electric delivery robots for urban areas this is even more the case as the distances to travel are longer and the loading infrastructure is sparser. For benchmarking recharging strategies, good or even exact solutions for the static problem variant, in which all orders are known in advance, are valuable.

In this talk, we propose a column generation (CG) based approach for solving the EVRPTW minimizing the tardiness of the jobs served by a fleet of electric delivery robots with a capacity of one. The objective value corresponds to the goal of dispatching approaches of serving jobs as early as possible to be available for future unknown demand. As in literature, the CG pricing problem is modelled as a variant of the elementary shortest-path problem with resource constraints and solved by dynamic programming using a labelling algorithm. To incorporate the minimum tardiness objective as well as multiple and partial recharging options per route, we propose tailored resource extension functions to compute efficiently minimum and maximum costs of (partial) paths. Based on solutions for different scenarios for urban delivery robots we identify patterns for successful recharging strategies, applicable to central or decentral dispatching strategies.