A comprehensive web application for solving complex vehicle routing problems using Google OR-Tools and Google Routes API. This application enables users to upload Excel files containing delivery, pickup, truck, depot, and employee data, then generates optimized routes that minimize total costs while respecting real-world constraints.
This VRP solver addresses the Capacitated Vehicle Routing Problem with Pickup and Delivery (CVRPPD), incorporating multiple dimensions including:
- Distance constraints (vehicle range limitations)
- Volume and weight capacity constraints
- Time windows (employee work hours)
- Pickup-delivery pairing constraints
- Cost optimization (fuel + labor costs)
Decision Rationale:
- Simplicity over complexity: The frontend requirements are straightforward - file upload, column mapping interface, and basic visualization
- No framework overhead: Avoiding the performance and bundle size overhead of React/Vue/Angular for a relatively simple UI
- Fundamentals focus: Chosen to solidify core frontend development skills without framework abstractions
- Rapid prototyping: Faster initial development without build tools, transpilation, or complex tooling setup
Key Features:
- Drag-and-drop Excel file upload with validation
- Dynamic column mapping interface for flexible data structures
- Progressive web app workflow (Upload → Map → Solve → Visualize)
- Responsive design with CSS animations and modern UI patterns
Decision Rationale:
- Rapid iteration: Python's expressiveness enables quick development and testing of complex VRP algorithms
- OR-Tools integration: Google OR-Tools has excellent Python bindings, despite the underlying C++ implementation
- No performance concerns:
- OR-Tools solver is implemented in C++, so Python wrapper doesn't impact solving performance
- Single-user application doesn't require high-concurrency server frameworks
- I/O operations (file processing, API calls) benefit more from Python's ecosystem than raw performance
- Rich ecosystem: Pandas for Excel processing, requests for API integration, Flask for lightweight web serving
- Configurable mapping system: Dynamic field processors allow flexible Excel column mapping
- Chunked processing: Handles large files efficiently using pandas chunking
- Type safety: Robust data validation and type conversion with fallback defaults
- Multi-sheet support: Processes multiple Excel sheets (deliveries, trucks, depots, pickups, employees)
- Intelligent caching: Persistent disk-based cache prevents redundant API calls
- Rate limiting: Implements Google's 3000 elements/minute quota with rolling window tracking
- Batch processing: Optimizes API usage by batching distance matrix requests
- Exponential backoff: Handles API errors and rate limits gracefully
- Address normalization: Consistent address handling for reliable caching
Multi-dimensional optimization:
- Cost dimension: Primary objective combining fuel costs (distance/MPG × gas price) and labor costs (time × hourly rate)
- Distance dimension: Enforces vehicle range constraints
- Volume/Weight dimensions: Respects truck capacity limits
- Time dimension: Handles employee work hour constraints
- Pickup-delivery constraints: Ensures proper sequencing of pickup/delivery pairs
Solver strategies:
- Multiple first-solution strategies with fallback (PATH_CHEAPEST_ARC, PARALLEL_CHEAPEST_INSERTION, SAVINGS, etc.)
- Guided Local Search metaheuristic for solution improvement
- Configurable time limits for responsive user experience
- Comprehensive logging for debugging and optimization analysis
- SQLite for simplicity: Lightweight, serverless database perfect for single-user applications
- File caching: Temporary storage of uploaded Excel files with TTL expiration
- API response caching: Persistent storage of Google Routes API responses
- Python 3.8+
- Google Maps API key with Routes API enabled
- Clone the repository:
git clone <repository-url>
cd vehicle-routing-problem-app- Set up Python environment:
cd server
pip install -r requirements.txt- Configure environment:
# Create .env file in server directory
echo "GOOGLE_MAPS_API_KEY=your_api_key_here" > .env- Initialize database:
python -c "from server.db.init_db import init_app; from flask import Flask; app = Flask(__name__); init_app(app)"- Start the server:
python app.py- Access the application:
Open
http://localhost:5000in your browser
The application expects Excel files with the following sheets:
| Column | Description | Example |
|---|---|---|
| UID | Unique truck identifier | "TRUCK_001" |
| Max Volume | Maximum cargo volume | 1000.0 |
| Max Weight | Maximum cargo weight | 5000.0 |
| Current Location | Starting address | "123 Main St, City, State" |
| End Location | Return address | "123 Main St, City, State" |
| Range | Maximum travel distance | 300.0 |
| MPG | Miles per gallon | 8.5 |
| Column | Description | Example |
|---|---|---|
| UID | Unique delivery identifier | "DEL_001" |
| Current Location | Pickup address | "456 Oak Ave, City, State" |
| Destination | Delivery address | "789 Pine St, City, State" |
| Volume | Package volume | 50.0 |
| Weight | Package weight | 25.0 |
Same structure as Deliveries sheet.
| Column | Description | Example |
|---|---|---|
| UID | Unique depot identifier | "DEPOT_001" |
| Location | Depot address | "100 Warehouse Rd, City, State" |
| Column | Description | Example |
|---|---|---|
| UID | Unique employee identifier | "EMP_001" |
| Hours Available | Work hours available | 8.0 |
| Hourly Pay Rate | Cost per hour | 25.00 |
| Truck UID | Assigned truck | "TRUCK_001" |
- Fuel price: $3.50/gallon (configurable in
cost_dimension.py) - Vehicle fixed cost: $1 per vehicle used
- Penalty for dropped nodes: $1,000,000 (encourages complete solutions)
- Time limit: 30 seconds per solve attempt
- Metaheuristic: Guided Local Search
- Multiple strategy fallback: 6 different first-solution strategies
- Google Routes API: 3000 elements per minute (automatically throttled)
- Batch size: 25×25 origins/destinations per request
The solver implements a sophisticated CVRPPD algorithm:
- Problem modeling: Converts real-world constraints into OR-Tools dimensions and constraints
- Distance matrix generation: Uses Google Routes API for accurate travel times and distances
- Multi-objective optimization: Balances fuel costs, labor costs, and constraint satisfaction
- Constraint handling: Enforces capacity, time, range, and pickup-delivery pairing constraints
- Solution refinement: Applies local search metaheuristics for solution improvement