Route Optimization: How to Measure Fuel and Time Savings in Distribution

---

What is Route Optimization?

Route optimization is the science of determining the most efficient path under multiple constraints.

Route optimization is a mathematical and algorithmic approach that enables the most efficient way to reach multiple delivery points. It is the practical application of classic operational research problems such as the “Travelling Salesman Problem” and the “Vehicle Routing Problem.”

The optimization process considers the following variables:

• Distance and time: Physical distance between points and estimated driving time.
• Vehicle capacity: Weight, volume, and pallet limitations.
• Time windows: Delivery intervals specified by the customer.
• Driver constraints: Working hours, break requirements, and certifications.
• Traffic conditions: Historical and real-time congestion data.
• Vehicle specifications: Fuel consumption, emission class, and refrigeration capacity.

Optimization Goals

Route optimization is not a one-dimensional problem. Different priorities require different optimization goals:

• Distance minimization: Reducing total kilometers traveled.
• Time minimization: Shortening total operational time.
• Cost minimization: Lowering fuel, labor, and vehicle expenses.
• Capacity maximization: Increasing vehicle utilization rates.
• Service level: Improving on-time delivery rates.

Manual Planning vs. Algorithmic Optimization

Limitations of traditional manual route planning:

• The human brain cannot optimize more than 15-20 points.
• It is impossible to evaluate all variables simultaneously.
• Even experienced planners show a 15-25% deviation from the optimal solution.
• Difficulty in responding quickly to dynamic changes.

Advantages of algorithmic optimization:

• Evaluates thousands of points in seconds.
• Accounts for all constraints simultaneously.
• Produces consistent and repeatable results.
• Capable of real-time re-optimization.

---

VRP Algorithms and Solution Approaches

VRP is one of the most extensively studied problems in combinatorial optimization.

The Vehicle Routing Problem (VRP) is an optimization problem defined by Dantzig and Ramser in 1959, which has been the subject of thousands of academic studies since. It is classified as NP-hard; meaning as the problem size grows, finding the optimal solution becomes exponentially difficult.

VRP Variants

The basic VRP problem is diversified with different constraints:

CVRP – Capacitated VRP

Each vehicle has a specific capacity limit. This is the most common variant and covers the majority of distribution scenarios.

VRPTW – VRP with Time Windows

Each customer has a specific delivery time window. This is a critical variant for last-mile delivery.

VRPPD – VRP with Pickup and Delivery

Scenarios involving both delivery and collection. Used for reverse logistics and complex operations.

MDVRP – Multi-Depot VRP

Distribution from multiple depots. Used for large-scale distribution networks.

DVRP – Dynamic VRP

Adaptation to real-time changes, such as new orders, cancellations, and traffic updates.

Solution Algorithms

1. Exact Algorithms

These guarantee the optimal solution but can only be applied to small problems:

• Branch and Bound: Optimal solution via systematic search.
• Branch and Cut: An improved version using cutting planes.
• Mixed-Integer Programming: A mathematical programming approach.

Limitation: Calculation time becomes unacceptable beyond 50-100 points.

2. Constructive Heuristics

Building routes step-by-step starting from an empty solution:

• Nearest Neighbor: Select the closest point at each step.
• Savings Algorithm (Clarke-Wright): Save by merging routes.
• Sweep Algorithm: Clustering via angular scanning.
• Insertion Heuristics: Add points to the most suitable position.

Advantage: Fast, understandable, and provides a good initial solution.

3. Improvement Heuristics

Iteratively improving the existing solution:

• 2-opt: Swapping two edges within a route.
• 3-opt: Swapping three edges for more comprehensive improvement.
• Or-opt: Moving points or sequences.
• Relocate/Exchange: Transferring points between routes.

4. Metaheuristics

Sophisticated approaches developed for complex problems:

• Genetic Algorithms: Mimicking natural selection and mutation.
• Simulated Annealing: A method inspired by the metal cooling process.
• Tabu Search: Search with memory to escape local optima.
• Ant Colony Optimization: Simulating ant colony behavior.
• Particle Swarm Optimization: Optimization based on swarm intelligence.

Hybrid Approaches

Modern optimization software typically uses hybrid strategies:

1. Fast initial solution with constructive heuristics.
2. Local improvement with improvement heuristics.
3. Global search with metaheuristics.
4. Multi-solution discovery via parallel computing.

---

Last-Mile Delivery Optimization

The last mile is the most expensive and complex link in the logistics chain.

Last-mile delivery is the stage where the product is delivered from the distribution center to the end consumer. It is the shortest but most expensive segment of the logistics chain, accounting for 40-50% of total delivery costs.

Challenges of Last-Mile

Density and Distribution

High address density in urban distribution may seem like an advantage, but:

• Finding parking causes time loss.
• Waiting for elevators or climbing stairs increases time.
• Traffic congestion creates unpredictable delays.
• One-way streets and restricted zones extend the route.

Time Window Pressure

Consumer expectations are becoming increasingly narrow:

• Same-day delivery is becoming standard.
• 2-hour delivery windows are being requested.
• Expectation for real-time tracking and ETA.
• Flexible delivery options (leave at door, give to neighbor).

Cost of Failed Delivery

When the recipient cannot be reached:

• Second delivery attempt is a full-cost event.
• Return to warehouse and rescheduling.
• Customer dissatisfaction and churn.
• Cost of the return process.

Last-Mile Optimization Strategies

1. Micro-Fulfillment and Pre-positioning

Predicting demand to position products closer to the end customer:

• Urban micro-depots.
• Delivery from within retail stores.
• Mobile distribution points.

2. Dynamic Routing

Continuous optimization with real-time data:

• Live traffic integration.
• Adding new orders.
• Re-routing after failed deliveries.

3. Alternative Delivery Points

Options beyond home delivery:

• Parcel lockers.
• Pickup points.
• Click and collect: In-store delivery.

4. Crowdsourced Delivery

Flexible capacity via the gig economy model:

• Additional drivers during peak demand.
• Private vehicle or bicycle couriers.
• Flexible pricing.

5. Autonomous Delivery Technologies

Next-generation solutions:

• Delivery robots (sidewalk robots).
• Drone delivery (in limited scenarios).
• Autonomous delivery vehicles.

Last-Mile KPIs

• Delivery success rate: Percentage of successful first-attempt deliveries.
• Cost per delivery: Total cost / number of deliveries.
• Delivery time: Time elapsed from order confirmation to delivery.
• Customer satisfaction: NPS or CSAT score.
• Carbon footprint: CO2 emissions per delivery.

---

Fleet Management and Vehicle Tracking Systems

GPS-based fleet management provides visibility and control.

Fleet management is a systematic approach to the planning, coordination, and control of a commercial vehicle fleet. Modern fleet management combines GPS tracking, telematics, and data analysis.

Components of a GPS Tracking System

1. On-Board Unit (OBU)

• GPS receiver – location data.
• GSM/LTE modem – data transmission.
• OBD-II connection – vehicle data.
• Additional sensors – temperature, door opening, fuel level.

2. Data Transmission Infrastructure

• Data transfer via mobile network.
• Cloud-based data storage.
• API integrations.

3. Management Platform

• Real-time map view.
• Reporting and analytics.
• Alarm and notification management.
• Mobile applications.

Insights from Telematics Data

Location and Movement Data

• Instant location and speed.
• Route history and breadcrumbs.
• Duration and location of stops.
• Geofencing (zone entry/exit).

Driver Behavior Analysis

• Hard braking and sudden acceleration.
• Speed limit violations.
• Idling duration and intensity.
• Calculation of overall driver score.

Vehicle Health Data

• Diagnostic Trouble Codes (DTC).
• Fuel level and consumption.
• Maintenance requirements.
• Tire pressure (TPMS integration).

Fleet Optimization Applications

Route Compliance Analysis

Comparison of the planned route with the actual route:

• Deviation detection and root cause analysis.
• Identification of unnecessary stops.
• Evaluation of alternative routes.

Fuel Management

Controlling fuel costs:

• Fuel consumption analysis (L/100km).
• Driver-based comparison.
• Abnormal consumption alerts.
• Eco-driving training recommendations.

Maintenance Planning

Preventing breakdowns with preventive maintenance:

• Maintenance schedules based on mileage/hours.
• Predictive maintenance based on engine data.
• Minimization of vehicle downtime.

Safety and Compliance

Compliance with legal and corporate rules:

• Driver working hour tracking (tachograph integration).
• Speed limit compliance reports.
• Accident analysis and reporting.

---

Delivery Windows and Time Management

Time window management balances customer satisfaction and operational efficiency.

Delivery windows are the time intervals during which the customer accepts delivery. In the VRPTW (VRP with Time Windows) problem, these constraints significantly complicate routing but are critical for customer satisfaction.

Window Types

Hard Time Window

Strict limits that cannot be violated:

• Appointment-based deliveries (service sector).
• Production line replenishment (JIT).
• Cold chain products (specific hours).
• Legal restrictions (night delivery bans).

Soft Time Window

Preferred but flexible intervals:

• Customer preference window.
• Early/late delivery is possible but penalized.
• Penalty coefficient in the optimization algorithm.

Time Window Optimization

1. Window Assignment Strategies

Determining the appropriate window when taking an order:

• Capacity-based: Limited delivery slots in each window.
• Geography-based: Assigning windows based on regions.
• Dynamic pricing: Premium pricing for peak windows.

2. Cluster Creation

Grouping addresses with similar windows:

• Both geographical and temporal proximity.
• Assigning vehicles based on regions.
• Minimum window overlap within a route.

3. Buffer Time Management

Buffer time for unexpected situations:

• Average deviation analysis in the delivery process.
• Dynamic buffer based on traffic density.
• Based on customer type (easy/difficult delivery).

4. ETA Calculation and Update

Accuracy of estimated time of arrival:

• Machine learning model with historical data.
• Real-time traffic integration.
• Dynamic updates based on route progress.
• Customer notification (SMS, app).

Window Violation Scenarios

Early Arrival

• Waiting time and cost.
• Subsequent deliveries are affected.
• Alternative: break at an intermediate point.

Late Arrival

• Customer dissatisfaction.
• Risk of failed delivery.
• Proactive communication is mandatory.

Customer Not Found

• Alternative delivery options.
• Authorization to leave with a neighbor.
• Safe drop instructions.
• Redirection to a delivery point.

---

Dynamic Route Planning and Real-Time Adjustments

Real-time optimization goes beyond static planning.

Dynamic route planning is an optimization approach that adapts in real-time to changing conditions throughout the day. Static planning is done at the start of the day and remains unchanged; dynamic planning is continuously updated.

Events Triggering Dynamic Planning

External Factors

• Traffic changes: Accidents, road work, congestion.
• Weather conditions: Rain, snow, fog.
• Road closures: Emergency situations.

Operational Events

• New orders: Deliveries added during the day.
• Cancellation/changes: Customer requests.
• Failed delivery: Unable to reach recipient.
• Vehicle breakdown: Change in fleet capacity.
• Driver delay: Unexpected situations.

Re-optimization Strategies

1. Full Re-optimization

All unassigned deliveries are re-planned:

• Most comprehensive approach.
• High calculation cost.
• Necessary for major changes.

2. Partial Re-optimization

Only affected routes are updated:

• Faster calculation.
• Local improvement.
• Sufficient for most scenarios.

3. Insertion Heuristic

Adding the new point to existing routes:

• Fastest approach.
• Ideal for adding a single point.
• May deviate from the global optimum.

Real-Time Data Integration

Traffic Data

• API from traffic information providers.
• Fusion of historical and live data.
• Segment-based driving time estimation.

Vehicle Location Data

• Live location from GPS tracking system.
• Route progress status.
• Estimated time of completion.

Order Management System

• Automatic transfer of new orders.
• Order status updates.
• Customer contact information.

Dispatcher Interface

For effective dynamic planning, the dispatcher interface should include the following features:

• Map view: Live location of all vehicles.
• Alarm panel: Highlighting critical events.
• Scenario simulation: Testing before making decisions.
• One-click re-assignment: Quick manual intervention.
• Driver communication: Instant notifications and messaging.

---

Field Example: A Distribution Optimization Case

---

The 7 Most Common Route Planning Mistakes

---

Distribution Efficiency Metrics Table

Track the following metrics regularly to measure the success of route optimization. Improvement cannot be made without measurement:

Measurement frequency: Daily operational tracking, weekly trend analysis, monthly management reporting. For comparisons, use the base value first, then the value after optimization.

---

Route Optimization Checklist

---

Frequently Asked Questions (FAQ)

---