CS Paper Radar

Routes planning in a condominium company using mathematical optimization

Lara Rocha, Pedro Martins

cs.DM math.OC ·submitted 2026-10-14 12:20 UTC · v1

Abstract

This work focuses on planning daily routes for a group of employees of a condominium company. Given a set of employees and a set of customers with pre-scheduled visits, we want to build doubly-open routes to guarantee visits to all customers, ensuring that each customer is visited by an employee with the appropriate skills to carry out the required activity. The travel times between customers and the service time in each customer are known. The problem includes time windows for visiting customers, each employee has a maximum working time, and the daily working period is between 9 AM and 6:30 PM. The routes respect the lunch break period if they extend from morning to afternoon, which means that lunch break can be avoided if the route is fully completed in the morning or in the afternoon. The aim is to minimize the distance covered by all routes with a penalty for including lunch breaks. The distances and times between customers are collected via an API to Microsoft Azure; and the solutions are then displayed on Bing Maps. The results obtained show the operational advantages of an efficient and effective vehicle routing planning in a specific condominium management company. The model can be extended to other service provider companies.

Comment
29 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in fixed dimension

cs.DS math.CO ·2026-11-11 ·Daniel Skachkov, Yuriy Dorn
similarity 0.58
Abstract

In the Traveling Salesman Problem, a route must visit all customers and return to its starting point while minimizing its total length. The Minimum Latency Problem, also known as the Traveling Repairman Problem, instead minimizes the sum of the times at which customers are first visited. We give a deterministic polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in every fixed dimension, with arbitrary nonnegative customer weights. Our proof restricts the form of a solution in three steps, each with a controlled increase in cost. First, a decomposition based on Sitters' method assigns customers to phases that start and end at the root. Second, within each phase, we divide the route into a constant number of blocks and charge each customer at the end of its assigned block. The resulting objective is a nonnegative linear combination of block lengths. Third, we add an auxiliary dimension and use a fixed Minkowski norm to close each block path into a tour. Arora's closed-tour estimate then gives paths that cross the boundaries of a common dissection only at designated portals and a bounded number of times per face. A dynamic program optimizes the restricted objective, and projecting its paths back to the original space gives the final route. Rounding weights and coordinates keeps the state space polynomial.

0.30

Time-Aware Urban Flood Routing with Sticky Edge Closure on Forecast Depth: A Hanoi Case Study

cs.DC cs.CY ·2026-11-02 ·Mai Anh Tran, Vy Nguyen, Vova Nguyen, Minh Hoa Bui
similarity 0.57
Abstract

During urban flash floods, commuters and guiding agencies require awareness towards which roads remain passable when a vehicle actually arrives, rather than relying solely on which links appear open at initial departure. Most existing flood-routing tools apply a single static snapshot to each route; meaning that corridors that appear clear initially can become flooded before arrival. This paper presents a routing engine that ingests a two-hour water forecast, renewed every 15 minutes, and plans each journey around roads that the forecast closes for that specific vehicle class. Under this formulation, any road that closes mid-trip remains closed for that query, which keeps route calculation fast enough for live requests while operating inside a production GraphHopper routing server. Testing on a recorded storm in western Hanoi revealed that a router checking only departure conditions sent 7.8% of routes into roads flooded upon arrival. In comparable trips, the proposed rule produced longer routes in 3.95% of cases, requiring a median of only 9.2 s of additional travel time. Agencies and navigation platforms can employ this engine to schedule trips by vehicle type, allowing operators to establish depth limits and lookahead margins as policy parameters. However, several limitations must be noted, as the water depths originate from a hydrodynamic simulation that was not verified against measured water levels, the rainfall was replayed rather than forecast live, and depth cutoffs reflect policy settings rather than measured physical thresholds. Keywords: flood routing, time-dependent shortest path, sticky edge closure, forecast water depth, vehicle depth limit, Hanoi

0.19

KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version

cs.MS math.OC ·2026-09-01 ·Florian Rascoussier, Romain Billot, Lina Fahed, Christine Solnon
theorycode/data similarity 0.56
Abstract · v3: 93 pages, 4 figures, 12 tables. Updated authorship, affiliations, ORCID identifiers, acknowledgements and references. No new experiments…

The Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW) captures a central difficulty of urban logistics: travel times vary with the time of day, so the cost of a route depends on when it is driven. This paper introduces KAYROS, an open-source solver for the duration-minimization TDVRPTW that is both anytime and exact. It returns improving valid solutions throughout its time budget and can close instances with conditional computational optimality certificates through an integrated branch-price-and-cut component. We extend the composition of continuous arrival-time functions from the literature, previously described only at proof or proposition level, to the left-continuous functions that stepwise benchmarks require. We prove that the composition routine shipped in the checker computes that operation exactly. We analyze when its evaluation and breakpoint normalization are exact in IEEE-754 double-precision arithmetic, and argue that a canonical, epsilon-free checker must define the objective. The anytime layer combines greedy construction, granular time-dependent local search over balanced route trees, and iterated local search, with a fleet-aware descent for a fleet-cost objective. We further propose an anytime evaluation methodology based on a normalized signed primal integral under a pre-committed statistical design. On 212 instances from five families at a one-hour single-threaded budget, KAYROS achieves a pooled anytime score 63.3% lower than the strongest of three available contenders (Timefold, Hexaly, jsprit). All three contrasts are significant under Holm correction. KAYROS improves all 30 high-effort references of Blauth et al. and 10 literature best-known solutions, and publishes 704 such certificates. The solver, benchmarks and campaign data are openly released.

0.32

Adaptive and Cost-Efficient Joint Scheduling of UAV Routes and Analytics with Transit-Borne Fog

cs.DC ·2026-09-21 ·Suman Raj, Arindam Khanda, Gagana M D, Yogesh Simmhan, Sajal K. Das
similarity 0.55
Abstract · 17 pages, 11 figures, 5 tables

Unmanned Aerial Vehicles (UAVs) performing deadline-bound analytics over large rural areas cannot reliably offload workloads to sparse cellular base stations. We propose an approach that uses scheduled public buses as \textit{mobile fogs}: a UAV hands off data to a bus during a halt, and the bus carries it until its route enters cellular coverage. Because a public bus follows a fixed route and timetable, a handover depends on \textit{where} and \textit{when} the bus next reaches a cellular zone, rather than how near the stop is. We formulate a Mission Scheduling Problem over this model, co-scheduling UAV routes with the placement of each analytics task on the UAV edge, a stationary fog, or a bus, under deadline, energy, and cost constraints. Our \textit{Divide and Assign} (DA) heuristic selects the cheapest halt that still meets a task's deadline. Across 36 workload configurations in a rural region, derived from real cellular and transit data, DA achieves up to 20\% higher utility than the strongest heuristic and up to 41\% higher utility than the strongest adapted-prior scheduler, while incurring the lowest aggregate cost. The transit tier handles up to 71\% of drop-offs, raises task completion to 100\%, and reduces recharging cycles by up to 31\%. Finally, in the presence of traffic variability, the adaptive variant recovers 93\% of the utility the delays cost and maintains completion rates above 97\%.

0.20

Improved Approximations for Vehicle Routing with Nonuniform Speeds

cs.DS ·2026-10-08 ·Hong Li
similarity 0.55
Abstract · 21 pages, no figures

We study vehicle routing with vehicles of different speeds on a complete undirected graph whose vertex set consists of a depot and a set of clients, where the distances satisfy the triangle inequality. Each vehicle has a specified speed, and if the total length traveled by a vehicle of speed $s$ is $L$, its completion time is $L/s$. In the heterogeneous traveling salesman problem (HetTSP), each vehicle executes one tour starting and ending at the depot, and the tours collectively visit all clients. The objective is to minimize the maximum completion time among the vehicles. We give a $6$-approximation algorithm for HetTSP, improving the previous $90(1+δ)$-approximation for any fixed $δ>0$. We also consider two versions of the heterogeneous capacitated vehicle routing problem (HetCVRP). Each client has a demand, and the vehicles have identical capacities. A vehicle may execute several tours, each starting and ending at the depot, and reload at the depot between consecutive tours; the total demand delivered on each tour cannot exceed the vehicle capacity. In the split-delivery version of HetCVRP, the demand of a client may be divided among multiple visits, possibly by different vehicles. We give a $\frac92+2\sqrt3<7.965$-approximation algorithm for this problem. In the unsplit-delivery version of HetCVRP, the entire demand of each client must be delivered in a single visit. We give a $\frac{11}{2}+3\sqrt2<9.743$-approximation algorithm, improving the previous $450(1+δ)$-approximation for any fixed $δ>0$.

0.18

GREAT-ESDD: Graph Edge Attention Network for Effectively Steered Delivery Decisions

cs.AI ·2026-10-10 ·Attila Lischka, Ze Zhou, Xuegang, Ban, Balázs Kulcsár
similarity 0.53
Abstract · 28 pages, 12 figures

Online, same-day delivery requires operators to constantly update their routes, and the routing cost for deliveries increases with the number of customers. Out-of-home (OOH) delivery options can help companies handle increasing customer numbers while keeping delivery costs low. We develop a dynamic pricing-and-routing framework for this online ordering scenario with home and OOH delivery options. First, we develop a neural solver for the capacitated vehicle routing problem (CVRP) based on the Graph-Edge-Attention-Network (GREAT). We train it to solve CVRP with varying instance sizes and starting conditions, allowing it to reoptimize partially executed routes under changing conditions. It is fast while achieving solution quality competitive with traditional baselines. Our solver processes several CVRP instances in parallel in batches and we use it to solve the candidate routing problems that arise from an incoming customer's choice of home or OOH delivery. This provides an estimate of the delivery cost increase per option, which we use to set dynamic prices. Further, it directly provides the updated route once the customer decides. We trade off delivery fees against routing costs and steer customers toward OOH delivery when home delivery would be costly. However, effective steering requires us to know the customer preferences. To learn those online, we use Thompson sampling with a Laplace-approximated posterior. We call the resulting framework GREAT-ESDD (GREAT for Effectively Steered Delivery Decisions). Compared to a traditional routing solver, it increases profit by around 11% under a similar pricing decision time budget. Moreover, we show that we can estimate customer preferences successfully, outperforming a static pricing strategy after only 5 days of simulated operations.

0.28

A Hybrid Exact-Heuristic Solver for the Integrated Passenger and Parcel Transportation Problem

cs.AI ·2026-11-17 ·The Dung Bui, Ha Thu Nguyen
similarity 0.52
Abstract · 4 pages, 2 figures, 3 tables. Technical Report for the SOICT 2026 Student Contest

We describe the solver we submitted to the second round of the SOICT 2026 contest on the Integrated Passenger and Parcel Transportation problem, a selective pickup-and-delivery routing problem with time windows, open routes and heterogeneous taxis. The solver is a single-file, standard-library Python program that combines (i) a constant-time insertion test based on latest-arrival slack, (ii) greedy insertion, local search and an Adaptive Large Neighborhood Search (ALNS) with simulated-annealing acceptance, and (iii) an exact route-selection engine that enumerates, for every taxi, the best feasible route for each request set and then solves the resulting set-packing problem by branch-and-bound strengthened with route-based large neighborhood search, Lagrangian bounds and reduced-cost fixing. The engine is chosen automatically from the instance size, and an independent verifier and a watchdog guarantee that a valid answer is always printed. On the official evaluation (38 scored instances, 5-minute limit) the solver obtained a total benefit of 487,237, finished every run within 277 s and used at most 279 MB; 28 of the 38 instances terminated well before the limit.

0.28

CARRS: A Constraint-Aware, Real-Time Routing System for Emergency Vehicles in Urban Environments

cs.AI ·2026-10-19 ·Vincent Sello, Timothy Adeliyi, Ridewaan Hanslo
similarity 0.51
Abstract · 10 pages, 3 figures, 3 tables

Emergency vehicles such as police vehicles, fire engines, and ambulances require a stable and efficient route optimization to reach life-critical events in the shortest times possible. However, the dynamic nature of urban traffic makes this ideal scenario much more challenging, causing critical life-threatening delays. Traditional civilian navigation systems cannot account for real-time traffic changes alongside vehicle-specific constraints, creating inadequate routing scenarios. This research presents the Constraint-Aware Real-Time Routing System (CARRS), a unified software architecture tailored for emergency coordination. The CARRS architecture is engineered to fuse together classical pathfinding algorithms such as A*, Dijkstra, and Bidirectional A*, with Constraint Satisfaction Problem methodologies. The Design Science Research Methodology is the research framework, and prototyping is the iterative process. The artifact was empirically evaluated using OpenStreetMap data for major metropolitan road networks, combined with simulated dynamic traffic scenarios. Performance metrics focused on route optimality, constraint adherence, rerouting responsiveness, and the potential for future system scalability. Findings revealed the system's capability to generate optimal routes for operationally relevant subgraphs in under 35 seconds, with incremental rerouting responsiveness below 20 seconds. Furthermore, the system achieved more than 90% adherence to vehicle-specific constraints, making the CARRS architecture viable for real-time dynamic routing requirements. This study delivers a routing platform that bridges artificial intelligence-driven optimization with software engineering operational compliance, presenting a practical transformative step toward adaptive emergency vehicle coordination in dynamic urban environments.

0.28