ISYE 671Linear Optimization & Network Flows

← ProjectDownload: Markdown

Case Study 4: Routing Problem

Delivery Route Optimization for a Regional Grocery E-Commerce Service

ISYE 671 — Linear Optimization and Network Flows

Background

FreshCart Midwest is a regional online grocery delivery service operating in the greater Champaign-Urbana metropolitan area. The company operates a single fulfillment center (depot) and delivers grocery orders to residential customers using a fleet of delivery vans. Business has grown rapidly, and the operations team needs a systematic approach to daily route planning.

You have been brought in as an operations research consultant to develop and solve a vehicle routing model that minimizes total delivery cost while respecting vehicle capacity and customer time windows. The problem is a Capacitated Vehicle Routing Problem with Time Windows (CVRPTW).

Problem Data

Depot

The FreshCart fulfillment center (node 0) is located at coordinates (40.0, 40.0) on a grid representing the delivery area (each grid unit ≈ 0.5 miles). The depot opens at 6:00 AM and all vehicles must return by 4:00 PM (a 10-hour operating window, i.e., 600 minutes from 6:00 AM).

Customers

On the day being planned, there are 15 customers with confirmed delivery orders. Each customer has a delivery location, an order size (in standard tote equivalents), a delivery time window, and a service time.

Cust. X Y Demand (totes) Window Open Window Close Service (min)
1 22 58 5 8:00 11:00 10
2 35 72 7 8:00 12:00 12
3 50 65 4 9:00 13:00 8
4 62 50 6 8:00 11:30 10
5 18 45 8 9:00 13:00 15
6 55 38 5 9:00 12:00 10
7 28 30 7 10:00 14:00 14
8 45 22 4 8:00 12:00 8
9 70 42 6 9:00 13:00 10
10 15 65 5 9:00 12:30 10
11 38 48 4 12:00 15:00 10
12 60 28 8 8:00 11:00 15
13 25 18 3 11:00 15:00 8
14 48 55 6 10:00 13:30 10
15 33 35 7 8:00 11:00 12

Total demand: 85 totes.

Vehicle Fleet

FreshCart operates a homogeneous fleet of 5 identical delivery vans:

Parameter Value
Number of vans 5
Capacity per van 25 totes
Fixed cost per trip $65
Variable cost $1.00 per mile
Maximum route duration 540 minutes (9 hours)

Not all vehicles must be used. A vehicle incurs its fixed cost only if dispatched.

Travel Times and Distances

Travel between any two locations uses Euclidean distance (in grid units). Convert to miles by multiplying by 0.5 (each grid unit = 0.5 miles). Travel speed is 25 mph in urban/residential areas, so travel time in minutes between locations \(i\) and \(j\) is:

\[t_{ij} = \frac{d_{ij} \times 0.5}{25} \times 60 = 1.2 \times d_{ij} \text{ minutes}\]

where \(d_{ij} = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}\) is the Euclidean distance in grid units.

Your Assignment

Part 1: Model Formulation

Formulate a mixed-integer programming model for this CVRPTW.

  1. Decision variables: Define binary routing variables \(x_{ijk}\) (whether vehicle \(k\) travels directly from node \(i\) to node \(j\)), continuous time variables \(w_{ik}\) (arrival time of vehicle \(k\) at node \(i\)), and any auxiliary variables needed.

  2. Objective function: Minimize total delivery cost = fixed vehicle costs + variable travel costs.

  3. Constraints: Formulate all of the following:

    • Each customer is visited exactly once by exactly one vehicle.
    • Route continuity (flow conservation at each customer node for each vehicle).
    • Vehicle capacity constraints.
    • Time window constraints with arrival time tracking.
    • Depot departure and return constraints.
    • Subtour elimination (choose and justify your approach: MTZ or flow-based).
    • Maximum route duration.

  4. Variable and constraint counts: Count the number of binary variables and constraints in your formulation. Is this problem tractable for an exact MIP solver?

  5. Assumptions: Document any simplifying assumptions (e.g., symmetric travel times, no traffic variability).

Part 2: Implementation and Solution

Implement the model in AMPL/Gurobi in a Google Colab notebook.

  1. Solve the model: Solve the MIP formulation. Set a time limit (e.g., 10 minutes) and report the best solution found, the MIP gap, and solve time.

  2. Solution visualization: Create a plot (using matplotlib) showing all customer locations, the depot, and each vehicle’s route as a differently colored path.

  3. Route summary table: For each vehicle used, report the ordered sequence of customers visited, total distance, total totes delivered, departure/arrival times, and route cost.

Part 3: Operational Analysis

  1. Fleet utilization: How many vehicles are used in the optimal solution? What is the average vehicle utilization (totes delivered / capacity)?

  2. Time window analysis: Identify which customers have the tightest time windows. For the 3 tightest-window customers, solve the model with their windows widened by 1 hour and report any cost savings.

  3. Capacity sensitivity: If FreshCart upgraded to larger vans (30-tote capacity) at a higher fixed cost of $80/trip, would it reduce total cost? Solve the modified model and compare.

  4. Operations memo: Write a 1-page operational brief for FreshCart’s VP of Logistics summarizing the recommended daily routing plan, fleet utilization findings, and your recommendation on van capacity upgrades.

Deliverables