TB4 - Tournées de véhicule / Vehicle Routing 3

This study addresses the optimization of urban snow removal operations through graph-based modeling combined with metaheuristic optimization techniques. The problem is formulated as a capacitated arc routing problem with additional operational constraints, including service priorities, route continuity, and resource limitations. In this context, road segments represent required services, while vehicles must traverse the network efficiently to ensure full coverage with minimal operational cost. Due to the NP-hard nature of such routing problems, exact optimization methods become computationally infeasible for large-scale urban networks, particularly when realistic constraints are considered. This motivates the adoption of metaheuristic approaches capable of exploring large solution spaces and producing high-quality solutions within reasonable computational time.The proposed approach incorporates key operational constraints that reflect real-world conditions, such as vehicle capacity limits, priority levels associated with critical road segments, and service requirements that influence the sequencing of operations. Graph theory plays a central role in representing the road network, enabling the modeling of nodes and arcs as well as ensuring spatial consistency and route connectivity. Additional considerations are made to guarantee that generated routes are feasible, continuous, and practically applicable in a real operational setting.The optimization process focuses on minimizing the total travel distance while simultaneously improving the structure and coherence of the routes. Particular attention is given to reducing redundant movements, avoiding unnecessary traversals, and ensuring that priority areas are serviced in an efficient and timely manner. Furthermore, the approach promotes a balanced distribution of workload among vehicles, which contributes to better resource utilization and operational stability.The results demonstrate that the proposed methodology significantly improves route organization, enhances the coverage of priority segments, and reduces overall operational inefficiencies compared to traditional planning approaches. The generated solutions exhibit strong feasibility and robustness, making them suitable for practical implementation. Overall, this work highlights the effectiveness of combining graph-based modeling with metaheuristic optimization techniques to address complex urban routing problems and to improve the performance, efficiency, and sustainability of snow removal operations.

This paper addresses the Stochastic Vehicle Routing Problem with Driver Scheduling (SVRPDS), which combines vehicle routing and driver shift scheduling under uncertainty. Customer requests arise at various locations with uncertain occurrence, each with a demand, time window, and service duration. The problem is modelled as a two-stage stochastic program: the first stage assigns shifts to drivers based on their availability preferences, while the second stage constructs delivery routes for realized requests. To solve this problem, we develop five heuristics: Branch-and-Regret (B&R), Progressive Hedging Heuristic (PHH), Consensus-based Scenario Sampling (CSS), Quantile-based Shift Approach (QSA), and the Largest Duration Approach (LDA). Additional contributions include a novel branching scheme that, unlike traditional branching on binary variables, branches on a continuous variable, and a tailored node selection mechanism. Computational experiments on random instances show that B&R provides the best solution quality, while QSA offers the best balance between cost and runtime.

This study investigates the Split Visit Team Orienteering Problem with Varying Profit (SV-TOP-VP) for drone-enabled infrastructure inspection. Site profits follow a concave function of service time, balancing inspection detail and operational efficiency. To achieve cost savings, split visits are allowed. We propose compact MINLP formulations and a tailored branch-and-cut algorithm.

We considered the Roll-on/Roll-off Vehicle Routing Problem in a reverse logistics context, where vehicles handle detachable containers for waste collection and recycling. We propose a unified model that optimizes service, vehicle states, and treatment-facility assignment, while supporting split deliveries, multi-container operations, and encompassing several RRVRP variants within a single framework.