<Page>
EXHIBIT 3.1
STATE OF DELAWARE
OFFICE OF THE SECRETARY OF STATE
-------------------------------
I, WILLIAM T. QUILLEN, SECRETARY OF STATE OF THE STATE OF DELAWARE, DO
HEREBY CERTIFY THE ATTACHED IS A TRUE AND CORRECT COPY OF THE RESTATED
CERTIFICATE OF "APCOA, INC.", FILED IN THIS OFFICE ON THE TWENTY FOURTH DAY OF
FEBRUARY, A.D. 1994, AT 2 O' CLOCK P.M.
[GREAT SEAL OF THE STATE OF DELAWARE
- 1793 - 1847 - 1907]
[SEAL William T. Quillen
SECRETARY'S OFFICE --------------------------------------
1793 DELAWARE 1855] William T. Quillen, Secretary of State
0923153 8100 AUTHENTICATION: 7043209
944031036 DATE: 03-01-94
<Page>
AMENDED AND RESTATED CERTIFICATE OF INCORPORATION
OF
APCOA, INC.
(Originally incorporated on September 24, 1981, under the name of 120
OAKLAND PLACE, INC.)
APCOA, Inc., a corporation organized and existing under and by virtue
of the General Corporation Law of the State of Delaware (the "Corporation"),
DOES HEREBY CERTIFY:
FIRST: That the Board of Directors of the Corporation, has
duly adopted resolutions setting forth a proposed amendment and restatement of
the Certificate of Incorporation of the Corporation and declaring said amendment
and restatement to be advisable. The resolution setting forth the proposed
amendment and restatement is as follows:
RESOLVED, that the Corporation's Certificate of Incorporation
be amended in accordance with Section 242 of the General Corporation Law of the
State of Delaware to effect certain changes in said Certificate of
Incorporation, and that the Amended and Restated Certificate of Incorporation
attached hereto be adopted, in accordance with Sections 242 and 245 of the
General Corporation Law of the State of Delaware, as the Amended and Restated
Certificate of Incorporation of the Corporation,
SECOND: That in lieu of a meeting and vote of stockholders,
both of the stockholders of the Corporation have given their written consent to
said amendment and restatement and said amendment and restatement was duly
adopted in accordance with the applicable provisions of Sections 242, 245 and
228 of the General Corporation Law of the State of Delaware.
THIRD: That the capital of the Corporation shall not be
reduced under or by reason of said amendment and restatement.
<Page>
IN WITNESS WHEREOF, said APCOA, Inc. has caused this
certificate to be signed by its President, and attested by its Assistant
Secretary, this 24th day of February, 1994.
By: /s/ S. Waiver Stuelpe, Jr.
--------------------------------
Name: B. Waiver Stuelpe, Jr.
Title: President
B. Waiver Stuelpe
ATTEST:
By: /s/ William J. Montie
--------------------------------------
Name: William J. Montie
Assistant Secretary
2
<Page>
AMENDED AND RESTATED CERTIFICATE OF INCORPORATION
OF
APCOA, INC.
ARTICLE I
The name of the corporation (which is hereinafter referred to
as the "Corporation") is:
APCOA, Inc.
ARTICLE II
The address of the Corporation's registered office in the
state of Delaware is The Corporation Trust Center, 1209 Orange Street in the
City of Wilmington, County of New Castle. The name of the Corporation's
registered agent at such address is The Corporation Trust Company.
ARTICLE III
The purpose of the Corporation shall be to engage in any
lawful act or activity for which corporations may be organized and incorporated
under the General Corporation Law of the State of Delaware
ARTICLE IV
Section 1. The Corporation shall be authorized to issue 5,000
shares of capital stock, of which 3000 shares
<Page>
shall be shares of Common Stock, $1.00 par value ("Common Stock"), and 2000
shares shall be shares of Preferred Stock, $.01 par value ("Preferred Stock").
Section 2. Shares of Preferred Stock may be issued from time
to time in one or more series. The Board of Directors of the Corporation
(hereinafter referred to as the "Board") is hereby authorized to fix the voting
rights, if any, designations, powers, preferences and the relative,
participation, optional or other rights, if any, and the qualifications,
limitations or restrictions thereof, of any unissued series of Preferred Stock;
and to fix the number of shares constituting such series, and to increase or
decrease the number of shares of any such series (but not below the number of
shares thereof then outstanding).
Section 3. Except as otherwise provided by law or by the
resolution or resolutions adopted by the Board designating the rights, powers
and preferences of any series of Preferred Stock, the Common Stock shall have
the exclusive right to vote for the election of directors and for all other
purposes. Each share of Common Stock shall have one vote, and the Common Stock
shall vote together as a single class.
ARTICLE V
Unless and except to the extent that the By-Laws of the
Corporation shall so require, the election of directors of the Corporation need
not be by written ballot.
2
<Page>
ARTICLE VI
In furtherance and not in limitation of the powers conforrod
by law, the Board is expressly authorized and empowered to make, alter and
repeal the By-Laws of the Corporation by a majority vote at any regular or
special meeting of the Board or by written consent, subject to the power of the
stockholders of the Corporation to alter or repeal any By Laws made by the
Board.
ARTICLE VII
The Corporation reserves the right at any time from time to
time to amend, alter, change or repeal any provision contained in this
Certificate of Incorporation, and any other provisions authorized by the laws of
the State of Delaware at the time in force may be added or inserted, in the
manner now or hereafter prescribed by law; and all rights, preferences and
privileges of whatsoever nature conferred upon stockholders, directors or any
other persons whomsoever by and pursuant to this Certificate of Incorporation in
its present form or as hereafter amended are granted subject to the right
reserved in this Article.
3
<Page>
ARTICLE VIII
Section 1. ELIMINATION OF CERTAIN LIABILITY OF DIRECTORS. A
director of the Corporation shall not be personally liable to the Corporation or
its stockholders for monetary damages for breach of fiduciary duty as a
director, except for liability (i) for any breach of the director's duty of
loyalty to the Corporation or its stockholders, (ii) for acts or omissions not
in good faith or which involve intentional misconduct or a knowing violation of
law, (iii) under Section 174 of the General Corporation Law of the State of
Delaware, or (iv) for any transaction from which the director derived an
improper personal benefit.
Section 2. INDEMNIFICATION AND INSURANCE.
-----------------------------
(a) RIGHT TO INDEMNIFICATION. Each person who was or is made a
party or is threatened to be made a party to or is involved in any action, suit
or proceeding, whether civil, criminal, administrative or investigative
(hereinafter a "proceeding"), by reason of the fact that he or she, or a person
of whom he or she is the legal representative, is or was a director or officer
of the Corporation or is or was serving at the request of the Corporation as a
director, officer, employee or agent of another corporation or of a partnership,
joint venture, trust or other enterprise, including service with respect to
employee benefit plans, whether the basis of such proceeding is alleged action
in an official
4
<Page>
capacity as a director, officer, employee or agent or in any other capacity
while serving as a director, officer, employee or agent, shall be indemnified
and held harmless by the Corporation to the fullest extent authorized by the
General Corporation Law of the State of Delaware, as the same exists or may
hereafter be amended (but, in the case of any such amendment, only to the extent
than such amendment permits the Corporation to provide broader indemnification
rights than said law permitted the Corporation to provide prior to such
amendment), against all expense, liability and loss (including attorneys' fees,
judgments, lines, ERISA excise taxes or penalties and amounts paid or to be paid
in settlement) reasonably incurred or suffered by such person in connection
therewith and such Indemnification shall continue as to a person who has ceased
to be a director, officer, employee or agent and shall inure to the benefit of
his or her heirs, executors and administrators; PROVIDED, HOWEVER, that, except
as provided in paragraph (b) hereof, the Corporation shall indemnify any such
person seeking indemnification in connection with a proceeding (or part thereof)
initiated by such person only if such proceeding (or part thereof) was
authorized by the Board. The right to indemnification conferred in this Section
shall be a contract right and shall include the right to be paid by the
Corporation the expenses incurred in defending any such proceeding in advance of
its final disposition; PROVIDED, HOWEVER, that, if the General Corporation Law
5
<Page>
of the State of Delaware requires, the payment of such expenses incurred by a
director or officer in his or her capacity as a director or officer (and not in
any other capacity in which service was or is rendered by such person while a
director or officer, including, without limitation, service to an employee
benefit plan) in advance of the final disposition of a proceeding, shall be made
only upon delivery to the Corporation of an undertaking, by or on behalf of such
director or officer, to repay all amounts so advanced if it shall ultimately be
determined that such director or officer is not entitled to be indemnified under
this Section or otherwise. The Corporation may, by action of the Board, provide
indemnification to employees and agents of the Corporation with the same scope
and effect as the foregoing indemnification of directors and officers.
(b) RIGHT OF CLAIMANT TO BRING SUIT. If a claim under
paragraph (a) of this Section is not paid in full by the Corporation within
thirty days after a written claim has been received by the Corporation, the
claimant may at any time thereafter bring suit against the Corporation to
recover the unpaid amount of the claim and, if successful in whole or in part,
the claimant shall be entitled to be paid also the expense of prosecuting such
claim. It shall be a defense to any such action (other than an action brought to
enforce a claim for expenses incurred in defending any proceeding in
6
<Page>
advance of its final disposition where the required undertaking, if any is
required, has been tendered to the Corporation) that the claimant has not met
the standards of conduct which make it permissible under the General Corporation
Law of the State of Delaware for the Corporation to indemnify the claimant for
the amount claimed, but the burden of proving such defense shall be on the
Corporation. Neither the failure of the Corporation (including its Board of
Directors, independent legal counsel, or its stockholders) to have made a
determination prior to the commencement of such action that indemnification of
the claimant is proper in the circumstances because he or she has met the
applicable standard of conduct set forth in the General Corporation Law of the
State of Delaware, nor an actual determination by the Corporation (including its
Board of Directors, independent legal counsel, or its stockholders) that the
claimant has not met such applicable standard of conduct, shall be a defense to
the action or create a presumption that the claimant has not met the applicable
standard of conduct.
(c) NON-EXCLUSIVITY OF RIGHTS. The right to indemnification
and the payment of expenses incurred in defending a proceeding in advance of its
final disposition conferred in this Section shall not be exclusive of any other
right which any person may have or hereafter acquire under any statute,
7
<Page>
provision of the Certificate of Incorporation, By-law, agreement, vote of
stockholders or disinterested directors or otherwise .
(d) INSURANCE. The Corporation may maintain insurance, at its
expense, to protect itself and any director, officer, employee or agent of the
Corporation or another corporation, partnership, joint venture, trust or other
enterprise against any such expense, liability or loss, whether or not the
Corporation would have the power to indemnify such person against such expense,
liability or loss under the General Corporation Law of the State of Delaware.