The Data and Decision Sciences Lab is constantly working with local community partners on several data related projects that have a local and global impact.
Solving the Capacitated Vehicle Routing Problem: A Heuristic Approach
Community Partner: UniGroup
Team Members Involved
The capacitated vehicle routing problem (CVRP) is defined by a collection of delivery vehicles (trucks) generally of the same capacity that operate from a single location (depot) and are charged with meeting the needs (demand) of the customers (nodes). The objective of the CVRP is to minimize the number of trucks and the combined total distance traveled, subject to meeting the node demands and not exceeding the trucks’ capacities. In the classic CVRP, the trucks are required to return to the depot. Consider the example of a company (depot) that supplies several stores (nodes) with the amount of products (demand) they need on a weekly basis. The company aims to have the fewest number of drivers (trucks) traveling the least amount of miles (cost), while meeting the demand of all its stores. In this project, both cluster first route second and simulated annealing heuristics were applied to the CVRP. A business case study of one depot and one hundred eleven delivery nodes with varying demand was implemented using simulated annealing. Results were obtained in a reasonable timeframe and were very competitive with results from commercially available products.