Our work in linear programming and integer programming, initially
supported by an NSF research contract, is now the basis for an
active relationship with Alamo
Rent-A-Car. Our client uses our software to control shifts
of cars between locations as well as exchanges with manufacturers.
In this multi-phase project, Daniel H. Wagner Associates developed a
large-scale linear program for optimizing Alamo Rent A Car,s
rental fleet allocation and disposition. Alamo has over 130,000
cars distributed in over 170 locations throughout North America.
The objective of this model was to minimize total fleet cost
subject to demand, utilization, and vehicle mix constraints.
The main output of this model was an explicit description of
where every vehicle is located over the entire planning horizon,
typically 78 weeks. Among the costs considered by the model were
purchase costs, leasing costs, maintenance costs, transportation
costs, mileage costs, infleet costs, outfleet costs, and penalties
(such as lost revenue when cars are unavailable, or too much
surplus when the fleet is underutilized). There were a variety
of constraints placed on the fleet management problem. Every
location had a demand projection as a function of time, as well
as a desired vehicle utilization and mix. Leased vehicles have
constrained lifetimes, whereas purchased vehicles do not. The
tradeoff between the two types of vehicles lies in the residual
value of the make and model of the car. There were also operational
constraints involving when vehicles can enter and exit the fleet,
as well as how vehicles can move from location to location.
The Fleet Management Planning Aid (FMPA) was implemented in
C on an Enterprise 5000 with 8 available processors. Although
this problem is naturally cast as an integer program, its size
made it intractable. Even as a linear program, the globally optimal
formulation becomes too impractical to solve. The technique we
employed was a multistage linear program, dividing the problem
into several nearly independent sub-problems. This represents
a compromise between optimality and time/resources required to
achieve a solution. The nature of the multistage formulation
also helped to make the problem more amenable to a multi-threaded
implementation. This led to more efficient use of the available
system resources.
