Scheduling electric vehicles making milk-runs for just-in-time delivery

Battery-operated electric vehicles are frequently used in in-plant logistics systems to feed parts from a central depot to workcells on the shop floor. These vehicles, often called tow trains, make many milk-run trips during a typical day, with the delivery timetable depending on the production schedule. To operate such a milk-run delivery system efficiently, not only do the timetabled trips need to be assigned to vehicles, it is also important to take the limited battery capacity into consideration. Moreover, since most tow trains in use today are still operated by human drivers, fairness aspects with respect to the division of the workload also need to be considered. In this context, we tackle the following problem we encountered at a large manufacturer of engines for trucks and busses in Germany. Given a fixed schedule of milk-runs (round trips) to be performed during a planning horizon, and a fleet of homogeneous electric vehicles stationed at a depot, which vehicle should set out on which milk-run and when should recharging breaks be scheduled, such that all runs can be completed with the minimum number of vehicles and all vehicles are about equally busy? We investigate the computational complexity of this problem and develop suitable heuristics, which are shown to solve instances of realistic size to near-optimality in a matter of a few minutes. We also offer some insight into how battery technology influences vehicle utilization.