This Vehicle Routing add-in
is a modification of parts of the Combinatorics add-in.
The Optimal Sequence add-in was constructed with parts
of the Optimize
add-in.
The new add-in is better in many respects since it is devoted
to the single purpose of routing.
My inspiration for this topic is an e-mail I received some
time ago from a member of a group that delivers singing messages
on Valentines Day. Calls come from citizens of the city asking
to schedule the delivery of singing valentines. Each delivery
requires a team of live singers. Of course the destinations
are in all parts of the city, and singers are also geographically
dispersed. The chair person of the group wanted a tool to assign
and route singers to destinations. Since this is a once-in-a-year
event staffed by volunteers, the person didn't have money to
spend, so he tried my Combinatorics add-in
for TSP problems. The add-in was unsuccessful because it could
not handle multiple vehicles.
At a seminar I heard about the problem of assigning Catholic
priests to outlying rural parishes in Texas. Each parish could
not afford a dedicated priest so the problem was to assign
priests to the parishes to minimize the travel required. Again
the problem is a VRP with priests in the role of vehicles and
parishes in the role of delivery locations.
A small-time liquor distributor once wrote that he wanted
a tool to schedule his delivery trucks. He noted that commercial
VRP packages start in price at about 10,000 $US. That cost
was too high for him, so he wondered if one of my add-ins might
be useful.
My latest direct experience was with students from Texas A&M
working on their senior project. VRP was part of their design
problem. The VRP included with the Combinatorics add-in was
insufficient in some respects. In particular the add-in required
that when one trip was completed at a depot, the next truck
was forced to leave from the same depot. This makes it difficult
to model multi-depot problems with the Combinatorics add-in.
This experience lead directly to the revision of the add-in
reported here. With the new add-in there is no restriction
on the starting and returning locations.
Vehicle routing is necessary for many businesses and there
are a number of vendors offering commercial software and services.
OR/MS Today has published regular surveys on features and prices
of VRP products. Click here to
see the 2010 survey. The industry provides useful tools,
but their costs may be excessive for small businesses and nonprofit
institutions. Our routing add-in should be thought of as a
very distant and very introductory cousin of the commercial
systems. Since it is free, the add-in might be useful for institutions
that are small and/or poor. Also, the VBA code can be modified
to accept new model features so students and others are invited
to experiment.
The Routing add-in uses the Optimal Sequence add-in
that provides search heuristics for finding solutions, so the
two add-ins must be simultaneously installed. The only limits
to the size of problems that can be formulated are the worksheet
limitations of Excel, but for large problems, time and memory
requirements may be excessive. Since heuristics are used, solutions
found are local optimums. Options are included to find several
local optimum solutions during a single run of the add-in. |
