Wimpy Delivery Route Optimization

TL;DR

To optimize fast-food delivery logistics across Fifth Settlement, New Cairo, I designed a two-phase mathematical modeling framework for the Wimpy branch at Golden Square Mall. Phase 1 established all-pairs shortest paths across an 11-node network using Linear Programming (LP) in Excel and verified them via the Floyd-Warshall algorithm in TORA. Phase 2 solved the Traveling Salesman Problem (TSP) by benchmarking three heuristics: Nearest Neighbor with Subtour Reversal, Tabu Search, and Genetic Search. Tabu Search and Nearest Neighbor achieved the optimal circuit of 52.9 km (~53 km), with Tabu Search selected as the superior algorithm due to its robust ability to escape local optima in scaled networks.

Problem & Justification

High-density urban hubs require rapid and cost-effective delivery management. For fast-food chains like Wimpy in Golden Square Mall (New Cairo), transit delay directly degrades product quality and customer satisfaction. The delivery environment presents several specific operational challenges:

• Time Sensitivity: Fast-food orders demand tight delivery windows to ensure food arrives hot and fresh.
• High Demand Density: Golden Square serves a diverse customer demographic—including residential compounds (Mivida, Hyde Park, Dyar), university students (AUC), and major commercial areas.
• Cost & Overhead: Inefficient routing inflates fuel consumption, driver wear-and-tear, and operational costs.

The primary objective was to mathematically model and optimize delivery routes across a 5 km operational radius, establishing both point-to-point shortest paths and an all-inclusive single-vehicle distribution circuit.

System Description & Delivery Network

The network encompasses 11 interconnected nodes within the 5 km service radius. Node 1 serves as the origin (Wimpy branch), while Nodes 2 through 11 represent high-frequency customer clusters:

Every node is connected to adjacent nodes forming a well-connected directional graph. Inter-node distances were calculated using Google Maps distance matrix data to account for actual road networks and directional travel rules.

❮

🔍 Click to expand

🔍 Click to expand

❯

✕

Technical Details & Methodology

The project was executed through a structured two-phase mathematical modeling approach.

Phase 1: Shortest Route Problem (SRP)

To find the optimal individual route from Wimpy (Node 1) to any given destination, a Linear Programming (LP) network flow model was formulated:

LP Objective Function

Minimize the total distance $Z$ across all active directed arcs $(i, j)$:

$\min Z = \sum_{i=1}^{11} \sum_{j=1}^{11} c_{ij} x_{ij}$

Where:

• $c_{ij}$ represents the distance (in km) from node $i$ to node $j$.
• $x_{ij} \in \{0, 1\}$ is a binary decision variable indicating whether the path from $i$ to $j$ is traversed.

Flow Conservation Constraints

$\sum_{j} x_{ij} - \sum_{k} x_{ki} = \begin{cases} 1 & \text{if } i = \text{Source Node (Node 1)} \\ -1 & \text{if } i = \text{Destination Node} \\ 0 & \text{otherwise} \end{cases}$

The LP formulation was implemented and solved in Excel Solver. To ensure complete mathematical verification, the identical network matrix was processed using the Floyd-Warshall all-pairs shortest path algorithm in TORA.

❮

🔍 Click to expand

🔍 Click to expand

❯

✕

Phase 2: Traveling Salesman Problem (TSP)

When a single delivery driver needs to visit all 10 customer nodes in a single trip and return to Wimpy, the problem transforms into a classic Traveling Salesman Problem (TSP). Three heuristic methodologies were implemented and compared:

1. Nearest Neighbor & Subtour Reversal Heuristic:
   • Constructs an initial greedy tour by sequentially visiting the closest unvisited node.
   • Applies systematic subtour reversals to eliminate crossing edges and reduce total tour length.
2. Tabu Search Heuristic:
   • Explores neighbor solutions through pair swaps while maintaining a short-term memory list (“tabu list”) with a tenure period of 3 iterations.
   • Prevents cycling back to previously visited states, enabling the search to escape local optima.
3. Genetic Search Algorithm:
   • Simulates biological evolution over 25 iterations across 74 cycles with a population size of 6 and a mutation probability of 0.01.
   • Uses crossover operators to combine parent tours and evolve better routing sequences.

Heuristic Algorithmic Comparison

The three TSP heuristic models were benchmarked across tour distance, computational behavior, and solution quality:

❮

🔍 Click to expand

🔍 Click to expand

🔍 Click to expand

❯

✕

Results & Strategic Analysis

Key Findings

• Verification: 100% agreement between Excel LP Solver outputs and TORA’s Floyd-Warshall algorithm, validating the network distance matrix.
• Optimal Circuit: Both Tabu Search and Nearest Neighbor + Reversal achieved the minimum total circuit distance of 52.9 km (~53 km).
• Performance Gap: Tabu Search outperformed Genetic Search by 10.2 km (16.2% distance reduction), demonstrating superior local optima escape capabilities.

Why Tabu Search Wins for Operations

While Nearest Neighbor with Reversal matched the 52.9 km result, Tabu Search is the recommended methodology for production deployment:

1. Escape from Local Optima: Tabu Search allows non-improving moves when trapped in local minima, utilizing its tabu memory list to explore new search space areas. Greedy heuristics like Nearest Neighbor fail when scale increases.
2. Genetic Search Limitations: In this configuration, Genetic Search suffered from premature convergence due to small population constraints (6 individuals) and limited generational steps, yielding a sub-optimal 63.1 km route.

Recommendations & Future Scope

Based on the study findings, the following implementation roadmap is recommended for Wimpy operations:

• Deploy Tabu Search Engine: Embed Tabu Search routing logic into dispatch management software for multi-stop delivery runs.
• Dynamic Traffic Matrix Integration: Extend the static Google Maps distance matrix to include live traffic API inputs (accounting for rush hour bottlenecks on South 90th Street).
• Dynamic Node Management: Periodically update network nodes to accommodate new compound entrances and commercial developments in New Cairo.
• Multi-Vehicle VRP Extension: Scale the single-vehicle TSP model into a Capacitated Vehicle Routing Problem (CVRP) to optimize multi-driver fleets during peak ordering hours.