In recent years, machine-learning-based approaches have been used to solve a variety of different problems in the domain of combinatorial optimization. In our research, we aim to develop methods to make autonomous vehicles behave in efficient ways by platooning (i.e., by grouping autonomous vehicles and making them share information) and routing (deciding which way vehicles should travel). Traditionally, both domains have been dominated by “hand-crafted” algorithms. However, in recent years, deep-learning-based approaches have emerged as a powerful, data-driven alternative to tackle these complex problems. In the case of routing problems, where “simple” (nevertheless NP-hard problems) like the Travelling Salesman Problem have successfully been solved using deep-learning techniques, we want to focus on multi-objective and multi-graph problems where several cost functions and trade-offs between them shall be optimized at once (e.g., the travelled distance, consumed energy and spent time). Such problems are of high practical relevance; however, they have only been of comparably little interest in the research community so far. In the case of platooning, we aim to integrate deep reinforcement learning with heuristic searches. Traditional sorting strategies for vehicle coordination rely on hand-crafted cost functions and deterministic search algorithms, which often lack adaptability and scalability in dynamic traffic scenarios. Therefore, similar to how it has been done for routing problems and other combinatorial optimization problems, we propose to train a deep neural network to approximate the cost-to-go function from any given vehicle arrangement to a corresponding set of feasible target configurations. The idea is to use the outputs of the trained models to guide search algorithms such as A* and combine them with Integer Linear Programming for parallel vehicle movements. We expect this to reduce the number of sorting steps and computation times, and therefore to enhance real-time decision-making in autonomous traffic systems.