## 3 Problem Formulation
### Mathematical Model  
Sales route optimization can be formally expressed as a variant of the _Traveling Salesman Problem_ (TSP), where the goal is to determine the most efficient route that visits each customer exactly once and returns to the starting point. Given a set of \(N\) customers, each associated with geographical coordinates, the route must minimize both the physical distance and the expected travel time under real-time conditions. Let \(\mathcal{C}=\{c_{1},c_{2},\ldots,c_{N}\}\) denote the set of customers, where each \(c_{i}\) corresponds to a location defined by latitude and longitude coordinates. The physical distance between two customers \(c_{i}\) and \(c_{j}\) is calculated using the Haversine formula, a well-established method derived from spherical trigonometry for computing great-circle distances over the Earth's surface [2]. This formula is not empirical; it is a theoretically grounded expression obtained from geometry on the surface of a sphere, and is widely used in geospatial systems and navigation tools. It accounts for the curvature of the Earth and is appropriate for urban and regional scales, despite minor inaccuracies in dense metropolitan areas due to road network constraints. The distance function is defined as follows:  
\[d(i,j)=2R\cdot\arcsin\left(\sqrt{\sin^{2}\left(\frac{\Delta\phi}{2}\right)+ \cos(\phi_{i})\cos(\phi_{j})\sin^{2}\left(\frac{\Delta\lambda}{2}\right)}\right) \tag{1}\]  
where \(R=6371\) km is the Earth's radius, \(\phi_{i}\) and \(\phi_{j}\) are the latitudes in radians, \(\lambda_{i}\) and \(\lambda_{j}\) the longitudes in radians, and \(\Delta\phi=\phi_{j}-\phi_{i}\), \(\Delta\lambda=\lambda_{j}-\lambda_{i}\). It is important to note that the Haversine formula provides an approximation of the great-circle distance between two points on a spherical surface, assuming direct travel along a straight arc. While this assumption is suitable for regional or inter-city route estimation, it presents limitations in dense urban environments where actual travel paths are constrained by the road network topology, one-way streets, and traffic regulations. In such cases, the Euclidean or spherical distance may significantly underestimate the true travel distance or time. To address this limitation, our model incorporates a learned travel time predictor based on an LSTM architecture, which adjusts route evaluation dynamically using real-world historical traffic data. This hybridization enables the system to combine the computational simplicity of the Haversine-based distance matrix with the contextual realism of learned travel times. To model time-dependent conditions, we define a dynamic travel time function \(T(i,j,t)\), which estimates the duration required to traverse from \(c_{i}\) to \(c_{j}\) at time \(t\). This value is predicted using a trained LSTM model based on historical traffic patterns and contextual data such as hour of day and day of the week. The total cost function to be minimized integrates both spatial and temporal components:  
\[\min\sum_{i=1}^{N-1}d(c_{i},c_{i+1})+d(c_{N},c_{1})+\gamma\sum_{i=1}^{N-1}T(c_ {i},c_{i+1},t_{i}) \tag{2}\]  
Here, the first summation computes the total geographic distance for the full route, while the second term introduces the predicted travel time at each leg \((c_{i},c_{i+1})\), with \(t_{i}\) representing the estimated departure time from location \(c_{i}\). The parameter \(\gamma\in[0,1]\) acts as a trade-off coefficient that balances the influence of physical distance and estimated travel time in the total route cost. A value of \(\gamma=0\) leads the algorithm to prioritize only the minimization of geographic distance, while \(\gamma=1\) makes the optimization entirely time-driven. In practice, \(\gamma\) is treated as a tunable hyperparameter, and its optimal value is determined empirically through cross-validation.