Capacitated Vehicle Routing Problem Optimization Case Study
CAPACITATED VEHICLE ROUTING PROBLEM Optimization
Case Study Description
The Goal of the Study
- To dispatch UPS delivery trucks to the routes that minimize the total travel distance in the given constraint using the Heuristic (Improved Savings : built on the idea of Clark and Wright) and the Meta-Heuristic Algorithm (Genetic).
Constraint
- The Capacity of the UPS Truck = 1,500 kg
- The number of the available truck = 5 trucks
- 29 delivery spots (Node) with different demand
Assumption
- Distance between delivery locations is the Euclidean distance
- All the trucks are dispatched from the UPS center (1500 S. Jefferson St, Chicago, IL 60607)
Google Operation Research Tools
To run the Improved Saving Algorithm Python Code, Google OR tools are required to be installed.
Heuristic Algorithm Application
Improved Saving Algorithm (Clark and Wright)
Total Travel Distance
- 54.124 Kilometer
Truckloads ( Capacity : 1,500 kg )
- Truck 1 ( Red ) : 1,480 kg
- Truck 2 ( Green ) : 1,490 kg
- Truck 3 ( Pink ) : 1,340 kg
- Truck 4 ( Blue ) : 1,460 kg
- Truck 5 ( Brown) : 470 kg
Routes
- Truck 1 : UPS Depot ⎯ Gyu gaku BBQ ⎯ Mercy Hospital ⎯ Yongdoo's House ⎯ Bronzeville Jewel ⎯ Bronzeville Mariano's ⎯ IIT Yongdoo's Office ⎯ Bridgeport Polish Hotdog ⎯ UPS Depot
- Truck 2 : UPS Depot ⎯ South Loop Jewel ⎯ South Loop Trader Joe's ⎯ SAIC ⎯ The Purple Pig ⎯ Au Cheval ⎯ West Loop Target ⎯ West Loop Mariano's ⎯ UPS Depot
- Truck 3 :UPS Depot ⎯ South Loop Whole Foods ⎯ Chinatown Mariano's ⎯ Connie's Pizza ⎯ Bridgeport Ricobene's ⎯ Ashland Mariano's ⎯ Bridgeport Buffalo Wing ⎯ High Five Ramen ⎯ UPS Depot
- Truck 4 : UPS Depot ⎯ South Loop Best Buy ⎯ Nordstrom Rack ⎯ West Loop Starbucks ⎯ Rush Hospital ⎯ Little Italy Jewel ⎯ Costco ⎯ UPS Depot
- Truck 5 : UPS Depot ⎯ South Loop Home Depot ⎯ South Loop Target ⎯ UPS Depot
1/6
Meta-Heuristic Algorithm Application
Genetic Algorithm
MUTATION RATE : 0.1
CROSSOVER RATE : 0.7
POPULATION SIZE : 100
Total Travel Distance
- 77.305 Kilometer
Truckloads ( Capacity : 1,500 kg )
- Truck 1 ( Red ) : 1,480 kg
- Truck 2 ( Green ) : 1,100 kg
- Truck 3 ( Pink ) : 1,320 kg
- Truck 4 ( Blue ) : 1,310 kg
- Truck 5 ( Brown) : 1,030 kg
Routes
- Truck 1 : UPS Depot ⎯ West Loop Target ⎯ IIT Yongdoo's Office ⎯ Bridgeport Buffalo Wing ⎯ Bronzeville Mariano's ⎯ Bronzeville Jewel ⎯ Bridgeport Ricobene's ⎯ UPS Depot
- Truck 2 : UPS Depot ⎯ South Loop Home Depot ⎯ Chinatown Mariano's ⎯ South Loop Trader Joe's ⎯ South Loop Best Buy ⎯ South Loop Jewel ⎯ SAIC ⎯ UPS Depot
- Truck 3 : UPS Depot ⎯ High Five Ramen ⎯ Rush Hospital ⎯ Au Cheval ⎯ Costco ⎯ Gyu gaku BBQ ⎯ UPS Depot
- Truck 4 : UPS Depot ⎯ South Loop Target ⎯ Bridgeport Polish Hotdog ⎯ Connie's Pizza ⎯ South Loop Whole Foods ⎯ Little Italy Jewel ⎯ West Loop Mariano's ⎯ West Loop Starbucks ⎯ Nordstrom Rack ⎯ UPS Depot
- Truck 5 : UPS Depot ⎯ The Purple Pig ⎯ Mercy Hospital ⎯ Yongdoo's House ⎯ Ashland Mariano's ⎯ UPS Depot
1/6
Copyright © 2022 Yongdoo Lee Portfolio - All Rights Reserved.