The Vehicle Routing Problem

A special case of the general vehicle routing problem (VRP) is the school bus problem. Each bus has the same passenger capacity

Q

and a group of

n

students is distributed in 2D; we seek a set of bus routes that minimizes the total distance traveled by the buses to pick up all the students. Each bus is assumed to start and finish at the school.

Finding the true optimum is difficult. This Demonstration shows how the Clarke–Wright heuristic (CW) can provide a feasible solution to this problem. Here we wish to use the minimal number of school buses,

⌈n/Q⌉

(where

⌈x⌉

is the least integer greater than or equal to

x

). After the CW method finds a solution, you can use a traveling salesman problem algorithm to optimize each route. You can add students with ⌘+click or Alt+click.