Grant: Discovery Launch Supplement

Vehicle routing, such as picking up entities like goods, packages, or passengers from origin locations and delivering them to their destination locations, is a classic problem that has been well-studied in Operations Research and in various areas of Artificial Intelligence, including planning, scheduling, robotics, multi-agent systems, pathfinding, and intelligent transportation. Constrained vehicle routing problems are those subject to specific constraints. For example, in a green vehicle routing problem, vehicles face constraints such as limited fuel (battery) capacity, resulting in a shorter traveling range, and limited availability of refueling (battery charging) infrastructure that provides wide area coverage for these vehicles. While it is assumed that these problems are computationally intractable, necessitating foundational justifications, various algorithmic techniques have been developed over the past decades to solve them. However, it has been observed that these algorithms are often incomplete, relying on approximations or heuristics, such as evolutionary algorithms, genetic algorithms, and simulated annealing, or are only applicable to specific cases. The proposed research aims to gain a comprehensive understanding of the underlying computational challenges associated with representative constrained vehicle routing subproblems. Specifically, we plan to focus on domains where multiple vehicles are routing towards their destinations, which could lead to the possibility of vehicle collisions that must be avoided. Our complexity analysis and subsequent algorithm design will concentrate on two crucial categories of boundary cases. First, we will consider various optimization versions of these problems, where the optimization criteria may include: Finding the minimum maximal distance of any vehicle or the minimal total distance for all vehicles in a given problem instance (i.e., optimizing vehicle traveling distances). Finding the minimal makespan. Second, we will work on restricted graphs, which serve as abstractions for the tasks the vehicles need to fulfill. The restrictions may involve: The in/out degrees of graph nodes. The graph cyclicity. The planarity of graphs. The strongly/weakly connectedness of vertices. The availability of these results is particularly important in guiding the future practice of algorithm design and development in real-world vehicle routing applications. The proposed research is of immediate relevance to the transportation and logistics industry, environmental organizations, academic research, and government agencies. It will benefit the research field by advancing algorithmic techniques and have real-world applications in sustainable, efficient, and competitive transportation systems. Further, it will aid in crafting eco-friendly transportation policies, reduces operational costs for logistics companies, advances specific academic fields, and contributes to environmental conservation.