9807

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 and a group of 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, (where is the least integer greater than or equal to ). 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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Details of the CW method can be found in [1]. A complication is that the method, which forms routes and merges them, might not end up with a solution that uses the minimal number of buses. For example, with 10 students and capacity 5, the method can end up with loads of size 4, 3, 3, and then no further merging will respect the capacity restraint. In this Demonstration we want to minimize the number of buses, and that is achieved by adding a small amount of randomization to CW and running it 10 times with such randomization in addition to once with no randomization. The random enhancement comes when routes are selected to be merged: instead of greedily choosing a merge with the largest savings, one can randomly choose between the two best. Then the least-cost solution is chosen from among those of the 11 solutions that use the minimum number of buses.
The initial runs are performed without the traveling-salesman post-process step. If such post-processing is requested (as in the second snapshot), it is done on the best run achieved without post-processing. This was done so that you can see the same student partition with and without the post-processing. Another approach, which is only a little slower, is to run a traveling salesman improvement on each of the 11 initial runs and then choose the best. The sweeping method, described in [1], appears to be not as good, but does yield the minimum number of routes.
The third snapshot shows that the heuristic is not always optimal, since it is clear that the point on the blue tour that is on the green line could be added to the green tour with a reduction in total cost. One can try post-processing that moves single points around to try to improve the routes, but that is slow and has not been included here.
Reference
[1] G. Gutin, "Traveling Salesman Problems," in Handbook of Graph Theory (J. L. Gross and J. Yellen, eds.), Boca Raton, FL: CRC Press, 2004 pp. 279–299.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+