A Three-Stage Approach for the Multi-Depot VRP with Priority Requests

Field-service operations for utility companies require routing technicians across multiple depots while guaranteeing same-day response to critical infrastructure customers, a constraint that standard multi-depot routing methods cannot structurally enforce. We introduce the MDVRP with Priority Requests (MDVRP-PR), formalised as a lexicographic optimisation problem that guarantees service to priority customers before maximising coverage and minimising route duration. A three-stage pipeline is proposed: hybrid DBSCAN-Hierarchical clustering for topology-aware depot assignment, an Enhanced Max-Min Ant System (MMAS) with priority-driven construction, lexicographic solution selection, and repair, and a Boundary Relocate post-optimisation stage with global cross-depot recovery. The approach is evaluated on a real-world applied case study from Algérie Télécom (Guelma, Algeria), comprising a single four-depot field-service instance scaled to three sizes (55, 90, and 150 customers) and assessed over 2135 controlled runs. On this case study, the proposed clustering method outperforms the MDVRP-adapted Sweep baseline by 22.9 percentage points on the largest instance (n = 150; Friedman p < 0.001). The priority mechanisms sustain 100% feasibility across all configurations, compared to complete collapse without them (0/10 seeds at ≥40% priority), at a route-time overhead below 5%. Relative to the company’s current manual practice, the framework improves customer coverage by 16.1 percentage points within 28 s, confirming its practical utility for daily deployment in this capacity-constrained, priority-sensitive routing context.