Deep reinforcement learning (DRL)-based frameworks, featuring Transformer-style policy networks, have demonstrated their efficacy across various vehicle routing problem (VRP) variants. However, the application of these methods to the multi-trip time-dependent vehicle routing problem (MTTDVRP) with maximum working hours constraints -- a pivotal element of urban logistics -- remains largely unexplored. This paper introduces a DRL-based method called the Simultaneous Encoder and Dual Decoder Attention Model (SED2AM), tailored for the MTTDVRP with maximum working hours constraints. The proposed method introduces a temporal locality inductive bias to the encoding module of the policy networks, enabling it to effectively account for the time-dependency in travel distance or time. The decoding module of SED2AM includes a vehicle selection decoder that selects a vehicle from the fleet, effectively associating trips with vehicles for functional multi-trip routing. Additionally, this decoding module is equipped with a trip construction decoder leveraged for constructing trips for the vehicles. This policy model is equipped with two classes of state representations, fleet state and routing state, providing the information needed for effective route construction in the presence of maximum working hours constraints. Experimental results using real-world datasets from two major Canadian cities not only show that SED2AM outperforms the current state-of-the-art DRL-based and metaheuristic-based baselines but also demonstrate its generalizability to solve larger-scale problems.

Graph structures are effectively capable of describing the complex relationship between the objects, i.e. nodes, through edges. Besides, Graph-based representation is an effective method for feature dimensionality reduction [4, 5]. GNNs, as powerful tools for representational learning on graph-structured data, have attracted increasing attention in recent years. GNNs are used for effective deep representational learning to perform graph analysis for tasks such as node classification, link prediction, and clustering in Euclidean and non-Euclidean domains [6]. Among the proposed methods for learning representations on graphs, GCNs proposed by Kipf et al. [7] proved to be a simple and effective GNN model. This model is able to learn hidden representations comprising both node features and local graph structure while scaling linearly relative to the number of edges in the given graph. Most classification algorithms, in GNNs, tend to minimize the average loss over all training examples which produces reasonable outcomes for class-balanced datasets.

This trend is particularly evident in the logistics sector, where companies are actively integrating EVs into their transportation fleets. At the heart of this transition is the electric vehicle routing problem (EVRP), an optimization problem central to the operations of these logistics companies, focusing on dealing with the complexities of deploying EVs instead of internal combustion engine vehicles. This article addresses a practical routing problem for EVs, named heterogeneous electric vehicle routing problem with time-window constraints (HEVRPTW). It considers both vehicle attributes, such as varying cargo and battery capacities [4] and customer preferences regarding delivery times [5]. These factors create a more realistic and applicable model for contemporary logistics challenges. HEVRPTW, recognized as an NP-hard optimization problem, seeks to determine a set of routes with minimal cost, total traveling time, or total traveling distance, for a fleet of Heterogeneous EVs to serve each geographically dispersed customer's demands within a specified time-window. Traditional methods, including exact and heuristics solvers, are conventionally employed to solve various vehicle routing problem (VRP) variants. Due to the NP-Hard nature of HEVRPTW, and VRPs in general, exact methods, such as branch-and-price [6] and branchand-price-and-cut [7], consume prohibitively long time for solving practical-size problems [8].