Driven by global efforts to curb greenhouse gas emissions, there has been significant investment in electric vehicle (EV) technology in recent years, resulting in a substantial increase in EV market share. Concurrently, the demand for mobile robots, such as unmanned aerial vehicles (UAVs) and land-based robots, has also experienced rapid growth, encouraged by recent advances in the autonomy and capabilities of these systems. Common to both of these technologies is the use of electric motors for propulsion and batteries for mobile energy storage. Techniques for the coordination of electric vehicle fleets, whether human-operated or autonomous, must address a variety of unique challenges, including sparse recharging infrastructure, significant recharge durations, and limited battery capacities.

The central thesis of this dissertation is that constraint programming (CP) can be an effective and flexible paradigm for modeling and solving routing problems involving electric vehicles. While efforts on the development of mixed-integer linear programming (MILP) approaches to electric vehicle routing problems within the vehicle routing literature are expansive and consistently growing, the exploration of CP for approaching these increasingly pervasive problems has been, thus far, limited.

Throughout this dissertation, we address this thesis by developing novel CP formulations for both existing and new electric vehicle routing problem domains, leveraging modeling strategies from the MILP literature. Specifically, we propose novel CP models based on recharging path multigraphs as well as introduce a novel single resource modeling strategy that exploits symmetry in vehicle fleets for CP models involving interval, sequence, and cumulative function expression variables. These methodological contributions are then applied to four problem domains, where applicable. The first two problem domains involve electric vehicle routing with traditional logistics fleets. The third domain requires the synchronization of heterogeneous fleets involving UAVs and ground-based vehicles in a large-scale surveillance setting. Finally, the last problem domain involves the routing of social robots in a retirement home setting under complex real-world constraints, including synchronization and optional task precedence. For each of these domains, we empirically demonstrate the effectiveness of our CP approaches.