Skip to main content

VRP solver technology description

Overview

Introduction​

The Vehicle Routing Problem (VRP) Solver technology presented in this documentation is a state-of-the-art solution designed to tackle the challenges of complex logistics and transportation operations. At its core, the VRP Solver is an optimization tool that aims to find the most efficient routes and schedules for a fleet of vehicles to serve a set of geographically dispersed customers while satisfying various constraints.

Objectives​

The primary objective of this technical documentation is to provide a detailed and scientific explanation of our VRP Solver technology, catering specifically to a knowledgeable audience of scientific reviewers. By understanding the intricacies of our VRP Solver, reviewers can appreciate the innovative features and advanced methodologies that make it stand out from conventional routing solutions.

Key Components​

Our VRP Solver technology is built upon the constraint optimization approach, which serves as the foundation for the solution. However, we have undertaken extensive customizations and enhancements to tailor the library to the unique challenges of real-world VRPs. The key components of our VRP Solver include:

Advanced Heuristics​

We have developed proprietary heuristics with special logistics-purpose intelligence. These heuristics include the Fresh Ruin & Recreate Implementation, which optimizes the Capacitated Vehicle Routing Problem by efficiently distributing trips and minimizing slack, Slack minimization heuristics.

Time-Dependent Calculations​

Our VRP Solver takes into account the time-dependent nature of transportation logistics. Time windows, traffic conditions, and varying service times are integrated into the optimization process to create practical and realistic routes.

Vehicle Efficiency Constraints​

To ensure optimal resource utilization, our technology incorporates vehicle efficiency constraints. These constraints consider both loaded and unloaded vehicle capacities, allowing for stricter or more flexible checks on capacity usage.

Parallel Execution Strategies​

To expedite the solution process, we employ parallel execution of various first solution strategies. By exploring multiple strategies simultaneously, our VRP Solver enhances the probability of finding optimal solutions within a reasonable timeframe.

Geofence Constraints​

Our VRP Solver supports the assignment of fuzzy cross-border locations to vehicles, considering multiple geofences to enhance routing accuracy and compliance with geographical restrictions.

Dynamic Break Control​

We have developed a dynamic break control mechanism to ensure drivers adhere to regulated break times, preventing excessive driving hours and enhancing safety compliance.

Advantages and Impact​

Our VRP Solver technology offers several significant advantages for logistics and transportation operations:

  • Cost Savings: By optimizing routes and schedules, our VRP Solver minimizes travel distances and reduces fuel consumption, leading to cost savings for the fleet operators.
  • Improved Efficiency: The advanced heuristics and parallel execution strategies enable our technology to find high-quality solutions rapidly, enhancing overall operational efficiency.
  • Enhanced Customer Satisfaction: By providing more accurate arrival time estimates and efficient service, our VRP Solver contributes to improved customer satisfaction and loyalty.
  • Reduced Environmental Impact: Optimized routes result in reduced emissions and a smaller carbon footprint, aligning with sustainability goals.

System Architecture​

Overview of the VRP solver set up​

In our pursuit of solving real-world Vehicle Routing Problems (VRPs) efficiently and effectively, we have undertaken extensive customizations to the constraint optimization approach and libraries. These customizations have been carefully crafted to address the unique challenges posed by complex logistics and transportation operations.

Unique Features and Heuristics​

Trip Cost Feature on a Trip Level​

To account for various costs associated with each trip, we have introduced the trip cost feature. This feature enables the consideration of diverse factors, such as vehicle-specific expenses, road tolls, and time-dependent fees, on a per-trip basis. By incorporating these costs, our VRP Solver can generate cost-efficient routes, maximizing overall savings for logistics operations.

Slack Cost Feature on a Node Level​

To optimize the delivery schedules further, we have introduced the slack cost feature at the node level. Slack refers to the flexibility in delivery or service times at each customer location. By considering slack costs, our VRP Solver can minimize idle times and waiting periods, resulting in more streamlined and time-efficient routes.

Slack Minimization Heuristics​

The incorporation of slack minimization heuristics in our VRP Solver technology ensures that deliveries are scheduled as close as possible to the customer's preferred time window. This feature not only enhances customer satisfaction by adhering to time constraints but also optimizes the utilization of vehicles' capacities and minimizes the need for additional trips.

Modified CVB Heuristics (Fresh Ruin & Recreate Implementation for CVRP and PDPTW)​

Our custom implementation of the Fresh Ruin & Recreate heuristic is designed explicitly for the Capacitated Vehicle Routing Problem (CVRP). By efficiently redistributing trips among vehicles, this heuristic improves vehicle load balance, reduces unnecessary trips, and minimizes travel distances, thereby optimizing the overall efficiency of the fleet.

Memory Optimizations for Big Matrices Processing​

To handle large-scale VRPs with numerous customer locations and time-dependent data, we have implemented memory optimizations for big matrices processing. This allows our VRP Solver to efficiently handle vast datasets without compromising performance or solution quality.

Time-Dependent Calculations​

Our VRP Solver technology incorporates time-dependent calculations to model real-world traffic conditions and varying service times accurately. This feature ensures that routes are optimized based on the specific time of day, resulting in more accurate and reliable solutions.

LIFO Heuristics​

The Last-In-First-Out (LIFO) heuristic provides an alternative loading and unloading strategy for vehicles. By considering the order of customer visits, our VRP Solver can reduce the need for reorganizing vehicle loads during delivery, resulting in improved efficiency and reduced handling times.

Mutual-Exclusive Groups Constraint​

We have introduced the mutual-exclusive groups constraint to handle situations where certain customers cannot be served together in the same trip. By respecting these constraints, our VRP Solver ensures compliance with specific business requirements or regulations.

Service Time to Enter-Exit Specific Location Feature​

Our VRP Solver technology offers the ability to define varying service times for entering and exiting specific locations. This feature is particularly useful when certain locations have different service requirements for pickups and drop-offs, allowing for more accurate representation of real-world scenarios. Situations like entry to the gate or average queue time can be modeled by using this feature.

Vehicle Efficiency Constraints​

The custom implementation of vehicle efficiency constraints allows fleet operators to control vehicle load capacities efficiently. By imposing minimum and maximum load requirements during trips, our VRP Solver optimizes resource utilization and ensures that vehicles operate at their peak efficiency.

Trip Cost Parameter​

The VRP Solver technology introduces the concept of trip cost calculation. Trip cost is a component of the overall objective function that is proportional to the duration of the “trip” for every pickup-dropoff pair.

Slack Cost Parameter​

To optimize delivery schedules and minimize idle times, our VRP Solver incorporates slack cost management. Slack refers to the flexibility in delivery or service times at each customer location, allowing for some deviation from preferred time windows. By managing slack costs, our VRP Solver can effectively prioritize deliveries within their specified time windows, resulting in improved customer satisfaction and efficient resource utilization.

Memory Optimizations for Big Matrices Processing​

Handling large-scale VRPs with a significant number of customer locations and time-dependent data requires efficient memory management. The VRP Solver technology implements memory optimizations specifically tailored for processing big matrices. This enhancement ensures that our VRP Solver can efficiently process and manipulate vast datasets without experiencing memory constraints or performance degradation.

Time-Dependent Calculations​

To accurately model real-world traffic conditions and varying service times, our VRP Solver incorporates time-dependent calculations into the optimization process. By considering the specific time of day during route planning, our VRP Solver can adapt to dynamic traffic patterns, resulting in more accurate and reliable solutions that reflect the practical realities of transportation logistics. SWAT is using self-hosted customized routing engine with great flexibility in terms of Speed Management and customizations in terms of routing behavior.

Last-In-First-Out (LIFO) Heuristics​

The LIFO heuristic is introduced as an alternative loading and unloading strategy for vehicles. By considering the order of customer visits, our VRP Solver can minimize the need for reorganizing vehicle loads during delivery, leading to improved efficiency and reduced handling times. LIFO heuristics are particularly useful in scenarios where loading sequences can significantly impact overall trip efficiency.

Mutual-Exclusive Groups Constraint​

The mutual-exclusive groups constraint is an essential feature in the VRP Solver technology, ensuring that certain customers cannot be served together in the same trip. This constraint is particularly useful in situations where specific business requirements or regulations dictate that certain deliveries must be made independently of each other. By respecting these constraints, our VRP Solver complies with industry-specific rules and ensures the integrity of the delivered goods.

Mixed Fleet Support​

The VRP Solver technology offers extensive support for mixed fleets, where vehicles can be different in terms of their characteristics and can navigate using distinct road graphs. This feature addresses the practical complexities of real-world logistics operations, where diverse vehicles with unique attributes and route options coexist within a single fleet. With mixed fleet support, fleet operators can tailor route planning based on individual vehicle capabilities and road options. This flexibility allows for better adaptation to specific delivery requirements and constraints.

Characteristics of Mixed Fleet Support​

  • Vehicle Heterogeneity: The VRP Solver allows fleet operators to incorporate a diverse range of vehicles with varying capacities, speeds, and other specific characteristics. Whether it's trucks of different sizes, vans with different load capacities, or vehicles with specialized equipment, the mixed fleet support ensures that the optimization considers the unique attributes of each vehicle type.
  • Multiple Road Graphs: Mixed fleet support enables the VRP Solver to accommodate different road networks or graphs for vehicles. This is particularly valuable when vehicles have varying accessibility to certain regions or when they must adhere to different road restrictions based on their size or weight. So, small vans and big trucks can have different road restrictions and average speeds.

Vehicle-level speed coefficients​

In order to reflect specific driver-level driving style parameters, our system provides ability to have vehicle-level speed coefficients

Speed coefficients represent a scaling factor applied to the default travel speed of each vehicle. The default travel speed is the standard speed used to calculate travel times between nodes in the absence of any customized parameters. By introducing speed coefficients at the vehicle level, the VRP Solver technology can adjust the speed of each vehicle individually, taking into account driver-level driving styles.

For example, if a driver is known to drive more cautiously, the corresponding vehicle's speed coefficient can be set to a value less than 1, reflecting slower driving speeds. Conversely, if another driver is more inclined to drive faster, their vehicle's speed coefficient can be set to a value greater than 1, representing faster travel speeds.

Optimization Strategies​

First Solution Strategies​

The first solution strategies are the initial algorithms used by the VRP Solver technology to find an initial feasible solution to the Vehicle Routing Problem (VRP). These strategies serve as the starting point for subsequent optimization techniques and play a crucial role in achieving high-quality and optimized solutions. Our VRP Solver technology offers a range of first solution strategies, including both standard options and proprietary heuristics, each designed to address specific VRP scenarios and constraints.

Automatic Strategy​

The automatic strategy is a versatile approach that allows our VRP Solver to automatically select the most suitable first solution strategy based on the characteristics of the given VRP instance. It intelligently adapts to the problem at hand, choosing the strategy that is likely to yield the best results, making it a robust and efficient choice for a wide range of VRP scenarios.

Global Cheapest Arc Strategy​

The global cheapest arc strategy aims to find the cheapest arcs between customers across the entire problem instance. It selects arcs that minimize travel costs and directly connect distant customers, forming the initial solution's routes. This strategy is well-suited for VRPs with relatively balanced distances between customers and can quickly provide feasible routes.

Local Cheapest Arc Strategy​

The local cheapest arc strategy focuses on finding the cheapest arcs in the vicinity of each customer, optimizing the connections within smaller regions of the problem instance. By emphasizing local optimization, this strategy can efficiently handle VRPs with clustered customers and intricate geographical layouts.

Path Cheapest Arc Strategy​

The path cheapest arc strategy aims to construct routes based on the cheapest paths between customers, taking into account the entire route instead of individual arcs. By considering path costs, this strategy can generate more balanced and optimized routes in VRPs with complex topologies.

Path Most Constrained Arc Strategy​

The path most constrained arc strategy prioritizes the connections between customers with the most constraints, ensuring that critical constraints are satisfied early in the solution process. This strategy is beneficial in VRPs with stringent time windows or capacity limitations, where meeting specific customer requirements is of utmost importance.

Evaluator Strategy​

The evaluator strategy is a flexible approach that allows the VRP Solver technology to evaluate and optimize a given solution using various metrics and criteria. This strategy can be tailored to focus on specific objectives, such as cost minimization, route length reduction, or adherence to time constraints, providing the necessary adaptability to handle diverse optimization goals.

All Unperformed Strategy​

The all unperformed strategy creates routes in which none of the customers are served initially. It is particularly useful when it is essential to ensure that all customers are eventually visited during the optimization process. This strategy can be a starting point for further optimizations, ensuring no customer is left unattended.

Best Insertion Strategy​

The best insertion strategy selects the best position for inserting each customer into existing routes, one at a time, considering factors such as travel costs, time windows, and vehicle capacities. This approach incrementally builds routes, aiming for an optimal overall solution by making informed decisions about where to place each customer within the routes.

Parallel Cheapest Insertion Strategy​

The parallel cheapest insertion strategy employs a parallel approach to insertion, simultaneously considering multiple customers for placement into routes. By exploring several insertion options at once, this strategy can efficiently identify promising routes, speeding up the initial solution process in large-scale VRPs.

Local Cheapest Insertion Strategy​

The local cheapest insertion strategy focuses on inserting customers into routes one at a time, considering only a subset of nearby customers for each insertion decision. This approach is suitable for VRPs with many customers and helps reduce computation time while still maintaining solution quality.

Savings Strategy​

The savings strategy is a classical heuristic that calculates potential savings in travel costs by merging two separate routes into a single route. It then selects the most advantageous savings to create initial routes. This strategy is beneficial in VRPs with high transportation costs and many routes to merge.

Sweep Strategy​

The sweep strategy constructs initial routes by "sweeping" through the customer locations in a circular pattern from the depot. It efficiently generates initial solutions for VRPs with customers spread in a radial pattern around the depot.

First Unbound Min Value Strategy​

The first unbound min value strategy selects the first customer from the unassigned set that minimizes a specific criterion, such as distance to the depot or proximity to other customers. This approach is quick and effective for small to medium-sized VRPs.

Christofides Strategy​

The Christofides strategy is a well-known heuristic specifically designed for the Traveling Salesman Problem (TSP). It constructs initial solutions for VRPs by treating the problem as a TSP and applying the Christofides algorithm. Although primarily intended for TSP, it can serve as a starting point for VRP solutions.

Sequential Cheapest Insertion Strategy​

The sequential cheapest insertion strategy builds initial solutions by inserting customers sequentially based on their cheapest insertion cost. This approach optimizes routes progressively, considering the best placement for each customer in the context of the entire solution.

Adjustable Parallel Cheapest Insertion Strategy (SWAT Proprietary Heuristic)​

The adjustable parallel cheapest insertion strategy is a proprietary heuristic developed by our team. It optimizes the first stage of the solution process in incremental solver calls, speeding up the optimization for VRPs with incremental changes to the problem instance.

Logistics Parallel Cheapest Insertion Strategy (SWAT Proprietary Heuristic)​

The logistics parallel cheapest insertion strategy is another proprietary heuristic specifically tailored for logistics problems, where pickups are located in one geographical location. It optimizes the initial solution construction in VRPs modeled as Pickup and Delivery with Time Windows (PDPTW) in "prebook" mode.

The wide range of first solution strategies available in the VRP Solver technology provides versatility and adaptability for handling diverse VRP scenarios. These strategies, whether standard or proprietary, lay the foundation for subsequent optimization techniques, enabling our VRP Solver to produce high-quality solutions that optimize routes, minimize costs, and meet specific constraints and objectives. The subsequent chapters will delve further into the optimization methodologies and additional advanced features integrated into our VRP Solver technology, providing a comprehensive understanding of its scientific and technical prowess.

Metaheuristic Calculations​

The Role of Metaheuristics in the VRP Solver Technology​

Metaheuristics play a pivotal role in the VRP Solver technology, enhancing its ability to efficiently find high-quality solutions for complex Vehicle Routing Problems (VRPs). Metaheuristics are high-level optimization strategies that guide the search for optimal solutions by exploring the solution space, allowing the VRP Solver to navigate through vast and complex solution landscapes effectively. SWAT’s solution is utilizing the Metaheuristics search which starts right after First Solution Strategy phase and continues on a predefined time to reach operationally feasible and satisfactory solution.

Special heuristics for “operationally accepted plans”​

Fair Distribution Heuristics: Path Equalizer​

Purpose of the Path Equalizer​

The proprietary Path Equalizer is a powerful fair distribution heuristic integrated into the VRP Solver technology. Its primary purpose is to achieve equitable distribution of workload among vehicles in the fleet while optimizing overall route efficiency. The Path Equalizer ensures that each vehicle's routes are balanced in terms of distance or time traveled, minimizing disparities between them. By promoting fair distribution, the Path Equalizer contributes to increased operational efficiency and resource utilization, making it an essential component for optimizing real-world vehicle routing scenarios.

How Path Equalizer Works​

The Path Equalizer works by redistributing customer assignments among vehicles to balance their respective routes. It achieves this by considering the variance in path lengths among the vehicles and identifying opportunities for reassignment to achieve a more even distribution. The heuristic's algorithm analyzes the distance or time traveled by each vehicle and strategically swaps customer assignments between vehicles to reduce route imbalances.

Parameters Controlling Path Equalizer Application​

The Path Equalizer offers flexibility through customizable parameters, allowing users to control its application according to their specific fairness and efficiency objectives. The key parameters controlling the Path Equalizer are:

  • use_path_equalizer (Optional): This parameter determines whether to activate the Path Equalizer. By default, it is set to false, but users can enable it to apply the heuristic during the optimization process.

  • path_equalizer_weight (Optional): The path_equalizer_weight parameter defines the weight assigned to the additional cost element produced by variance in path lengths. By adjusting this parameter, users can balance the importance of fairness against other optimization objectives, such as cost minimization.

The Path Equalizer is a proprietary fair distribution heuristic, specifically designed for the VRP Solver technology. It aims to achieve a more balanced workload distribution among vehicles, thereby optimizing overall route efficiency and resource utilization. By leveraging the Path Equalizer's customizable parameters, users can tailor its application to align with their specific fairness and efficiency goals, making it a valuable tool in solving real-world vehicle routing problems with equitable distribution requirements. The subsequent chapters will continue to explore additional aspects of our VRP Solver technology, providing a deeper understanding of its scientific and technical prowess.

Handling Special Constraints​

Vehicle Efficiency Constraints​

The vehicle efficiency constraints feature is a powerful capability integrated into the VRP Solver technology to optimize the usage of vehicles' capacities during trips. By imposing loaded and unloaded capacity checks, fleet operators can ensure that vehicles are utilized efficiently and adhere to specific business requirements. The vehicle efficiency constraints feature provides fine-grained control over the capacities of vehicles throughout their routes, enabling the optimization of resources and costs in real-world logistics operations.

Loaded and Unloaded Capacity Checks​

The vehicle efficiency constraints consist of two types of capacity checks: loaded capacity and unloaded capacity checks.

Loaded Capacity Check​

The loaded capacity check enforces that, during each trip, the vehicle should be loaded with not less than a predefined minimum amount of capacity. This constraint ensures that vehicles carry a sufficient load during their trips, avoiding underutilization of resources.

Unloaded Capacity Check​

The unloaded capacity check applies at the end of each trip. It enforces that the vehicle should not be loaded with more than a predefined maximum amount of capacity when it returns to the depot or completes its final delivery. This constraint prevents vehicles from returning to the depot with excess unused capacity, optimizing the efficiency of fleet operations.

Strictness Options​

The vehicle efficiency constraints feature offers two strictness options for both loaded and unloaded capacity checks: strict and weak.

Strict​

If a capacity check is set to strict, it means that the constraint must always be satisfied, even if it results in a suboptimal solution or if no feasible solution exists. This option is useful when certain business rules or regulations mandate strict adherence to capacity requirements.

Flexible (strict=false)​

If a capacity check is set to flexible (strict=false) it means that the constraint is considered as an optimization objective, but not a strict requirement. In cases where the constraint cannot be fully satisfied, a configurable penalty is added to the objective value, reflecting the deviation from the desired capacity. The weak option allows more flexibility and can be useful when it is acceptable to incur a penalty for minor capacity deviations.

Penalties and Impact on the Objective Value​

When vehicle efficiency constraints are set to weak and are not strictly satisfied, a penalty is incurred, which contributes to the objective value of the optimization problem. The penalty represents the cost or undesirability associated with failing to meet the specified capacity requirements.

The penalty calculation consists of two components:

  • Fixed Penalty: The fixed penalty is a pre-defined value that represents the cost incurred for violating the capacity constraint. It is a constant value specified by the user.

  • Linear Penalty: The linear penalty is calculated as the product of the over/under-capacity cost and the amount by which the capacity constraint is violated. This component adds a cost proportional to the magnitude of the violation.

The objective value is the sum of all costs and penalties associated with various constraints and optimization objectives in the VRP. By including penalties for capacity violations, the VRP Solver technology aims to find solutions that minimize the overall objective value, while still satisfying capacity constraints to the best possible extent.

The vehicle efficiency constraints feature in the VRP Solver technology enables fleet operators to optimize the usage of vehicles' capacities during trips. By setting loaded and unloaded capacity checks, strictness options, and penalties, the VRP Solver ensures that vehicles operate efficiently, minimizing underutilization and unnecessary returns with unused capacity. The fine-grained control over capacity constraints allows fleet operators to align their logistics operations with specific business requirements and optimize overall resource utilization, making the VRP Solver a valuable tool for solving real-world vehicle routing problems with complex capacity constraints. The subsequent chapters will continue to explore additional aspects of our VRP Solver technology, showcasing its scientific rigor and practical applications in the field of vehicle routing optimization.

Dynamic Break Control​

The dynamic break control mechanism in the VRP Solver technology is a powerful feature designed to manage the driving hours and breaks of vehicles during their routes. By dynamically controlling breaks, fleet operators can ensure driver safety and compliance with driving regulations, such as maximum driving hours and mandatory rest periods. The dynamic break control mechanism considers various sub-parameters to optimize break scheduling while maximizing route efficiency and adherence to time windows.

Sub-parameters Controlling Dynamic Break Control​

  • Dynamic Break Duration: The dynamic_break_duration sub-parameter specifies the maximum duration for which a vehicle can drive continuously without taking a break. If a dynamic break is not required, this value may be set to 0. By configuring the dynamic break duration, fleet operators can enforce driving hour restrictions and prevent driver fatigue.

  • Dynamic Break Min Path Duration: The dynamic_break_min_path_duration sub-parameter determines the minimum path duration required for a dynamic break to be triggered. If the real path duration is less than this value, then no dynamic break will be added. This feature allows for dynamic breaks to be applied only in specific situations, ensuring breaks are scheduled efficiently without causing unnecessary delays.

  • Dynamic Break Start Time and End Time: The dynamic_break_start_time and dynamic_break_end_time sub-parameters define the time window during which a dynamic break can start and end, respectively. This ensures that dynamic breaks are scheduled within appropriate time frames, aligned with driver availability and the overall trip schedule.

  • Dynamic Break Average Time Between Breaks: The dynamic_break_avg_time_between_breaks sub-parameter determines the average time between consecutive breaks. By setting this value, fleet operators can control the frequency of breaks, ensuring that drivers have sufficient rest periods during their routes.

  • Dynamic Break Max Latency: The dynamic_break_max_latency sub-parameter sets the maximum allowed break latency. Break latency refers to the time between when a dynamic break becomes required and when it is actually scheduled. This parameter ensures that dynamic breaks are scheduled promptly and do not result in excessive delays.

Purpose and Impact​

The dynamic break control mechanism serves two main purposes:

  • Driver Safety and Compliance: By enforcing maximum driving hours and mandatory rest periods, the dynamic break control mechanism promotes driver safety and ensures compliance with driving regulations. It prevents drivers from exceeding safe driving limits, reducing the risk of accidents and driver fatigue.

  • Route Efficiency: The dynamic break control mechanism optimizes the scheduling of breaks to minimize their impact on route efficiency. By carefully considering the sub-parameters and aligning breaks with the trip schedule, the VRP Solver technology can strike a balance between driver safety and route optimization.

The dynamic break control mechanism is a critical feature in the VRP Solver technology, ensuring driver safety and compliance with driving regulations while optimizing route efficiency. By considering various sub-parameters, fleet operators can customize break scheduling to meet specific requirements, maximizing resource utilization and adhering to time windows. The dynamic break control mechanism makes the VRP Solver a valuable tool for real-world logistics and transportation operations, contributing to safer and more efficient vehicle routing solutions. The subsequent chapters will continue to explore additional aspects of our VRP Solver technology, showcasing its scientific rigor and practical applications in the field of vehicle routing optimization.

Geofence Constraints​

The geofence constraint feature in the VRP Solver technology enables fleet operators to define geographical boundaries, known as geofences, that vehicles must adhere to during their routes. Geofences are virtual perimeters that can represent specific regions, zones, or areas of interest. By imposing geofence constraints, fleet operators can ensure that vehicles operate within predefined boundaries, optimizing route planning and compliance with specific operational requirements.

Support for Multiple Geofences​

The VRP Solver technology provides robust support for multiple geofences, allowing fleet operators to define and manage several distinct geographical regions. Each geofence can have its unique characteristics and constraints, enabling more complex and versatile logistics planning.

For example, consider a delivery operation with multiple distribution centers located in different districts of the city. Each distribution center can be associated with its geofence, defining the region where the vehicles are allowed to operate. The VRP Solver can then generate optimized routes that respect the boundaries of each geofence, ensuring that vehicles remain within their designated operational areas.

Fuzzy Cross-Border Assignment​

In addition to supporting multiple geofences, the VRP Solver technology offers the ability to assign fuzzy cross-border locations to vehicles. Fuzzy cross-border assignment allows for more flexible vehicle routing decisions when customers or stops are located close to the geofence boundaries.

With fuzzy cross-border assignment, the VRP Solver considers that customers located near a geofence boundary can be served by vehicles on either side of the boundary. This feature helps avoid unnecessarily long detours caused by strict adherence to geofence borders. By allowing vehicles to serve customers close to the geofence boundary, the VRP Solver maximizes route efficiency and reduces travel distances, leading to improved overall optimization.

Cross-border assignments is activated by assigning more than one geofence to vehicle and node, resulting in possibility to optimize the route efficiency overall.

Time Window Violation Allowance​

The time window violation allowance feature in the VRP Solver technology provides fleet operators with the flexibility to allow vehicles to be late for their scheduled stops within specified time windows. This feature is particularly useful in real-world logistics scenarios where strict adherence to time windows may not always be feasible due to unforeseen circumstances or traffic delays. This feature is optional and can be activated if operational scenario allows time window violations. Violations would be minimized by applying the penalty for every second of the violation.

Allowing Vehicle Lateness​

By enabling the time window violation allowance, fleet operators can relax the requirement for vehicles to arrive at customer locations precisely within their designated time windows. Instead, vehicles are allowed to arrive late, but within a predefined tolerance, without incurring significant penalties.

This allowance is especially relevant for scenarios where punctuality is not the sole priority or when avoiding excessive route modifications is more crucial than strict time window compliance. Allowing vehicle lateness helps the VRP Solver technology explore more feasible and efficient routing options, improving overall solution quality and practicality.

The time window violation allowance feature in the VRP Solver technology provides fleet operators with the ability to relax strict time window requirements and allow vehicle lateness within specified tolerances. By configuring the penalty coefficient for time window violations, fleet operators can influence the importance of time window adherence in the optimization process.

Penalty Coefficient for Time Window Violations​

When vehicle lateness is allowed and a vehicle arrives late at a customer location, a penalty is incurred to account for the time window violation. The penalty coefficient for time window violations determines the cost associated with each unit of time window deviation.

The penalty coefficient is a configurable parameter set by the fleet operator, reflecting the relative importance or cost of late arrivals. A higher penalty coefficient implies that time window violations are more costly, encouraging the VRP Solver to prioritize solutions that minimize lateness.

By adjusting the penalty coefficient, fleet operators can strike a balance between the importance of adhering to time windows and the practicality of the solutions. A lower penalty coefficient might indicate that lateness is more acceptable and can lead to more relaxed time window constraints, while a higher coefficient emphasizes the importance of strict time window adherence.

Maximum number of consecutive Pickup and Dropoff Locations​

The maximum number of consecutive pickup and dropoff locations feature in the VRP Solver technology imposes constraints on the consecutive non-identical pickup and dropoff locations that a vehicle can make during its route. This constraint enhances the efficiency of the VRP Solver by controlling the complexity and length of vehicle routes, leading to improved overall solution quality and route optimization.

Constraints on Consecutive Non-identical Pickup Locations​

The maximum pickup locations constraint specifies the maximum number of consecutive non-identical pickup locations that a vehicle can make before performing any dropoff. In other words, it limits the length of continuous pickup operations that a vehicle can execute without making any deliveries.

By setting a reasonable maximum value for consecutive non-identical pickup locations, fleet operators can prevent vehicles from performing excessively long pickup sequences. This constraint ensures that the vehicle does not overcommit to picking up multiple loads without offloading any items, which can lead to inefficient route planning and increased travel distances.

Constraints on Consecutive Non-identical Dropoff Locations​

Similarly, the maximum dropoff locations constraint determines the maximum number of consecutive non-identical dropoff locations that a vehicle can execute before any pickups. It restricts the length of continuous dropoff operations without performing any pickups.

This constraint is valuable in scenarios where vehicles may need to make multiple deliveries in a row before starting any pickup operations. By setting an appropriate limit, fleet operators can prevent vehicles from executing overly long dropoff sequences without performing any pickups, thereby optimizing route planning and resource utilization.

Purpose and Benefits​

The limitations on consecutive non-identical pickup and dropoff locations offer several benefits:

  • Optimized Route Length: By restricting the length of continuous pickup and dropoff sequences, the VRP Solver technology can generate more compact and efficient vehicle routes. This leads to reduced travel distances and overall transportation costs.

  • Balanced Workload: The constraints help in balancing the workload between pickups and dropoffs, ensuring that vehicles do not become overloaded with pickups or deliveries in a single sequence. This balanced approach optimizes vehicle utilization and enhances route efficiency.

  • Practicality and Feasibility: By preventing excessively long pickup or dropoff sequences, the VRP Solver generates solutions that are more practical and easier to implement in real-world logistics operations. It avoids unrealistic scenarios where a vehicle performs an impractical number of pickups or deliveries without alternating between the two.

Time Dependent Pipelines​

Time-dependent pipelines in the VRP Solver technology are a sophisticated implementation of multi-stage optimization strategies that consider time as a critical factor in vehicle routing. These pipelines leverage the temporal aspects of the problem, such as time windows, travel times, and time-dependent constraints, to generate highly optimized solutions for time-sensitive logistics operations. SWAT solver technology in combination with Time-dependent Map Engine provides ability to optimize vehicle motion taking into account variations of the traffic conditions during the day.

Optimization Benefits of Time Dependent Pipelines​

The implementation of multi-stage time-dependent pipelines offers several optimization benefits:

  • Realistic Time-Based Solutions: By explicitly considering time-dependent factors, the pipelines generate solutions that align with real-world operational constraints. This results in practical and feasible solutions, especially for time-sensitive logistics operations.

  • Improved Time Window Adherence: The time-dependent optimization stage ensures that vehicles adhere to time windows, reducing customer waiting times and preventing delays.

  • Efficient Resource Utilization: Time-dependent pipelines balance workloads among vehicles, leading to more evenly distributed routes and better resource utilization.

  • Accurate Travel Time Estimations: Time-dependent pipelines consider dynamic travel times, which accurately reflect the impact of traffic conditions and varying speeds, leading to more accurate estimations and better route planning.

Parallel Execution Strategies​

The parallel execution of first solution strategies is a powerful optimization technique employed by the VRP Solver technology to accelerate the search for high-quality solutions in vehicle routing problems. This strategy leverages the capabilities of modern computing systems to concurrently explore multiple initial solution paths, leading to faster and more efficient results.

How Parallel Execution Works​

In parallel execution, the VRP Solver simultaneously launches multiple instances of the solver, each exploring a different first solution strategy. These instances run independently and concurrently on multiple processing cores or computing nodes. By exploiting the available parallel processing power, the VRP Solver explores a diverse set of initial solution paths in parallel. Results are compared after the finalization of parallel computations and overall best result is chosen as final. SWAT technology stack allows to have parallel distributed calculations on a cluster of virtual machines in a cloud environment, not only on a single machine.

Benefits of Parallel Execution​

The parallel execution of first solution strategies offers several benefits:

  • Faster Exploration: By running multiple instances in parallel, the VRP Solver significantly reduces the time needed to explore different initial solution options. This results in a substantial speedup compared to sequential execution, especially for problems with a large solution space.

  • Diverse Solution Paths: Parallel execution allows the VRP Solver to explore diverse solution paths simultaneously. This increases the chances of finding promising initial solutions from various starting points, potentially leading to more diverse and high-quality solutions.

  • Early Termination: The parallel execution strategy can be designed to implement early termination criteria. Once a satisfactory initial solution is found, the other instances can be terminated, further reducing the optimization time.

  • Multi-Core Utilization: Modern computing systems often feature multiple processing cores, and parallel execution effectively utilizes these resources, optimizing computational efficiency.

Optimizing Overall Solution Quality​

Parallel execution strategies, combined with diverse first solution strategies, contribute to the overall optimization process by enhancing the likelihood of finding good initial solutions quickly. These initial solutions then serve as starting points for subsequent refinement and metaheuristic stages, resulting in improved overall solution quality.

Multi-Dimensional Capacity and Demand​

The VRP Solver technology provides robust support for multi-dimensional vehicle capacity and node demand, allowing fleet operators to optimize vehicle routing problems with complex and diverse resource constraints. This is achieved through the use of key-value capacity dictionaries, a flexible and efficient data structure that enables the representation of multi-dimensional capacities and demands.

Key-Value Capacity Dictionaries​

In the context of the VRP Solver technology, key-value capacity dictionaries serve as a versatile mechanism for defining multi-dimensional capacities and demands. Each vehicle and node is associated with a capacity dictionary, where each key represents a specific dimension, and its corresponding value indicates the capacity or demand in that dimension.

For example, consider a vehicle that can carry goods with two different attributes: weight and volume. The vehicle's capacity dictionary could look like this:


Vehicle Capacity Dictionary:

{

'weight': “2000”

'volume': “10”

}

Similarly, for a node (customer or stop) with multi-dimensional demand, the demand dictionary might be represented as follows:


Node Demand Dictionary:

{

'weight': “500”,

'volume': “3”

}

Benefits of Key-Value Capacity Dictionaries​

The use of key-value capacity dictionaries provides several benefits for modeling and solving multi-dimensional vehicle routing problems:

  • Flexibility: Key-value capacity dictionaries allow fleet operators to define an arbitrary number of capacity dimensions and their corresponding values. This flexibility enables the representation of various real-world constraints, such as weight, volume, quantity, or any other relevant resource.

  • Efficiency: By using dictionaries, the VRP Solver can efficiently access and manipulate multi-dimensional capacities and demands during the optimization process. This leads to faster computation and improved performance for large-scale problem instances.

  • Scalability: The key-value approach easily scales to accommodate problems with varying numbers of dimensions. This scalability is crucial for handling complex logistics scenarios with multiple resources to manage.