Uncertainty and Dynamicity in Real-World Vehicle Routing Václav Sobotka Faculty of Informatics, Masaryk University Brno, Czech Republic Vehicle Routing Problem Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 2 Vehicle Routing Problem Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 3 Real-World Vehicle Routing Problem and data provided by company Pickup-Delivery VRP Time windows Capacities Multiple depots Route duration limit Heterogenous fleet . . . Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 4 Existing solver Original version from the thesis of Vojtěch Sassmann Adaptive large neighborhood search Remove part of existing solution Repair the solution Accept/reject as a new solution Repeat for many iterations Return the best solution Challenge: efficient implementation Bottleneck: finding the best position for a customer within a route Constraint checking Currently: all constraints are checked in O(1) Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 5 Issues in practice Existing solver already used in production Assistive tool helping dispatchers plan routes Limitation: solutions not always applicable in practice The input provided to the solver is subject to uncertainty The input is incomplete Inspiration by human dispatchers Intuitively understand risky routing patterns Assess plans with incoming changes in mind Current solver Lacks any notion of risks (capacities, time) Completely blind to incoming changes Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 6 Motivation Goal: solver producing solutions that the dispatchers like Risk-awareness Planning with input incompleteness in mind Requirements: Natural extension to the existing solver Minimal/no performance overhead Minimum assumptions about the data on uncertainties Intuitive modeling Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 7 Uncertainties Sources of uncertainty in real-world problems Capacities vs. demands Regular customers: require service every day, but demand highly varies Freight loading: 1 + 1 ̸= 2 Balancing truck axles 3D Tetris Times Travel times: traffic Service times: freight (un)loading Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 9 Sad pallets and angry drivers Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 10 Sad pallets and angry drivers Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 10 Sad pallets and angry drivers Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 10 Sad pallets and angry drivers Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 10 Sad pallets and angry drivers Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 10 Sad pallets and angry drivers Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 10 Sad pallets and angry drivers Source: https://www.matthewsauctioneers.com/auctions/26398/lot/76606-pallet-of-c-grade-read-description Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 11 Uncertainties and risks Risky route Safe route Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 12 Generic approaches to uncertainties Incorporate the knowledge about the uncertainties by either 1 Inflating the demands 2 Deflating the resource 3 Quantify and penalize/forbid the risk Capacities 1 Plan with larger loads 2 Plan with smaller vehicles 3 Penalize/forbid routes risking vehicle capacity overflow Times 1 Plan with larger travel/service times 2 Plan with smaller time windows 3 Penalize/forbid routes risking late arrival to customers Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 13 Generic approaches to uncertainties – examples Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 14 Generic approaches to uncertainties – examples Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 14 Generic approaches to uncertainties – examples Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 14 Generic approaches to uncertainties – examples Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 14 Generic approaches to uncertainties – examples Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 14 Generic approaches to uncertainties – examples Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 14 Generic approaches to uncertainties – examples Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 14 Modeling and implementation Inputs about uncertainty: E(X), Var(X) Minimum information to express reasoning about uncertainties Minimum assumptions on the data Approachable level of abstraction for the end users Minimum performance overhead Capacities: all additional computations in O(1) Times: same as capacities with the exception of risk penalties Simple integration of all three methods: Demand inflation: data manipulation Resource deflation: data manipulation Risk penalty/constraints: implementation similar to existing constraints Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 15 Method comparison Preliminary experiments with capacities Comparable results may be achieved with all three methods Parameter choice is crucial Parameters strongly correlated with routing plan fail rates (ρ ≈ 0.75) Theoretically, methods have different properties (and weaknesses) Vehicle deflation: large uncertainties, heterogeneous fleet Load inflation: adversarial instances Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 16 Dynamicity Sources of dynamicity in real-world problems Dynamic customers Some customers call on the day of delivery These customers are not known at the time of route planning The information is revealed during the execution of our routing plan Adjustments to our routing plan are needed Realization of random variables Previously uncertain values (demands, times) are revealed during the day We may update our risk-related calculations We may adjust our routing based on the new information Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 18 Anticipation of potential changes Goal: build the routing plan with potential changes in mind Introduce dummy requests Optional service for reward Spatiotemporal coverage Space: locations of past customers Time??? Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 19 End-to-end vehicle routing Routing algorithm capable of assisting dispatchers with the daily operations 1 Initial routing plan (day before) Proactively prepare for potential dynamic events and uncertainties The final routing should largely overlap with the initial plan 2 (Preferably) small adjustments during the day of execution Ideally stick to the initial plan as much as possible Continually use the revealed information to improve the plan and reasoning about it Ultimate objective: optimization of the result at the end of the day Václav Sobotka Uncertainty and Dynamicity in Real-World Vehicle Routing SitSem 2023 20