Route Optimization in E-commerce Using Metaheuristics and Graphs: A VRP Approach

ROUTE OPTIMIZATION IN E-COMMERCE USING METAHEURISTICS AND GRAPHS: A VRP APPROACH DATA SCIENCE AND MATHEMATICS ENGINEERING | ITESM TEAM INFORMATION A00517244 | Camila Navarro Llaven A00831568 | Ana Daniela López Dávila A00828513 | Alejandro José Murcia Alfaro A00831197 | Paola Guadalupe Machorro Ortiz A01197857 | César Guillermo Vázquez Álvarez ABSTRACT This study addresses the Vehicle Routing Problem (VRP) in logistics using the Guided Local Search metaheuristic. Delivery routes are optimized to minimize distance, cost, and carbon footprint. The proposed model generates 5 efficient routes, with a total distance of 203.73 km and a fuel cost of $558.22. The routes are visualized using VeroViz and Cesium, demonstrating the effectiveness of the approach in improving efficiency and sustainability in logistics. Keywords: Deterministic Optimization, Guided Local Search, Vehicle Routing PROBLEM STATEMENT The objective of this research is to create an algorithm that enables a Mexican company to generate and assign transportation routes for goods in the Monterrey Metropolitan Area, such that these routes optimize customer delivery times, reduce costs involved in delivery logistics, and generate the smallest possible amount of pollutants by reducing transit and delivery times. REFERENCES INTRODUCTION This research focuses on outsourced logistics operations, which involve handling goods from their reception at the distribution center to their delivery to the final customer. The logistics component is of major importance for companies in Mexico; according to the Latin American Logistics Association, transportation logistics costs in Mexico are significantly higher than the Latin American average (BeeTrack, 2021). RESULTS A total of 5 routes were created, which are described below: Figure 1: Comparative table of the routes created. Figure 2: Number of customers covered per route. Figure 3: Visualization in a geospatial data visualization tool. Figure 4: Simulation. METHODOLOGY To address the Vehicle Routing Problem (VRP) for last-mile deliveries in Monterrey, we represent the distribution system as a weighted graph G= (N, E), where Nincludes all customers and the depot (CEDI), and Econtains feasible connections between locations. Each edge (i, j)is assigned a cost cij derived from a distance matrix (km). As preprocessing, delivery records were filtered to a representative working day and the complete pairwise distance matrix was constructed to enable consistent route evaluation. The baseline objective is to minimize the total distance traveled across all routes: min X (i,j)∈E cij ·xij where xij ∈ {0,1}indicates whether the connection (i, j)is used. Operational cost can be approximated by scaling cij with a truck efficiency factor (km/L) and fuel price. We impose standard VRP feasibility constraints. First, flow conservation enforces route continuity (balanced in/out degree per visited node), which prevents disconnected subtours: n X j=1 xij − n X j=1 xji = 0 ∀i∈N Second, capacity constraints ensure each vehicle respects volumetric demand limits. Let qibe the demand at customer iand Qkthe capacity of vehicle k: X (i,j)∈E qi·xij ≤Qk∀k∈K Finally, we bound the maximum route length to reflect dispatch feasibility: X (i,j)∈E cij ·xij ≤Dmax In implementation, we compute an initial feasible solution using constructive greedy heuristics (e.g., “cheapest arc”) via Google OR-Tools, then improve it with Guided Local Search (GLS), which augments the objective with adaptive penalties: f′(s) = f(s)+λ·h(s) where f(s)is the original distance-based objective, λcontrols the penalty weight, and h(s)accumulates penalties over repeatedly selected or costly edges. The final output is a set of routes that reduces total distance while respecting capacity and maximum-distance constraints. CONCLUSIONS Results show that applying graph techniques and the Guided Local Search (GLS) metaheuristic to the Vehicle Routing Problem (VRP) achieved a 23.09% reduction in both total traveled distance and fuel cost compared to the typical costs and distances without optimization.