Automatic vehicle identification (AVI) data provides information about vehicles’ identity and location, which enables accurate vehicle trajectory extraction. However, collecting complete and continuous long-term trajectory data is challenging due to limitations in coverage rate and identification accuracy. To recover the incomplete trajectory, current research mainly focuses on coarse-grained trajectory reconstruction. While these methods are adept at reconstructing the road segments traversed by vehicles, they cannot restore the spatial–temporal details of vehicle journeys and capture individual variability. To address these limitations, we propose a Multi-node Joint Optimization (MNJO) model, which utilizes AVI data and individual appearance features to achieve fine-grained vehicle trajectory reconstruction. The MNJO comprises two stages: local instance association and global trajectory reconstruction. In the local instance association stage, we design an inter-vehicle bidirectional optimization mechanism, which integrates the competitive and associative interactions among vehicles to improve their association across different nodes. In the global trajectory reconstruction stage, we propose a trajectory optimization network for trajectory scoring based on the spatial–temporal characteristics and the local association results of all nodes along the trajectory. Due to the lack of related datasets, we construct the Regional Vehicle Information (RVI) dataset, the first for fine-grained trajectory reconstruction, collected from real-world AVI systems. Extensive experiments on the RVI show that the MNJO can achieve significant enhancement in reconstruction accuracy compared to other methods, demonstrating the effectiveness and superiority of the proposed method. To the best of our knowledge, this is the first study on fine-grained vehicle trajectory reconstruction.