Exhibit 3.78

CERTIFICATE OF INCORPORATION

OF

Allied Waste of Long Island, Inc.

UNDER SECTION 402 OF THE BUSINESS CORPORATION LAW

* * * * *

     WE, THE UNDERSIGNED, all of the age of eighteen years or over, for the purpose of forming a corporation pursuant to Section 402 of the Business Corporation Law of New York, do hereby certify:

     FIRST: The name of the corporation is: Allied Waste of Long Island, Inc.

     SECOND: The purposes for which it is formed are: To engage in any lawful act or activity for which corporations may be organized under the Business Corporation Law provided that the corporation is not formed to engage in any act or activity which requires the consent or approval of any state official, department, board, agency or other body, without such consent or approval first being obtained.

     THIRD: The office of the corporation is to be located in the County of New York, State of New York.

     FOURTH: The aggregate number of shares which the corporation shall have authority to issue is One Thousand (1,000) each without par value.

     FIFTH: The Secretary of State is designated as the agent of the corporation upon whom process against the corporation may be served. The post office address to which the Secretary of State shall mail a copy of any process against the corporation served upon him is: c/o C T Corporation System, 1633 Broadway, New York, New York 10019.

     SIXTH: The name and address of the registered agent which is to

Page 1

be the agent of the corporation upon whom process against it may be served, are C T Corporation System, 1633 Broadway, New York, New York 10019.

     SEVENTH: No director shall be personally liable to the corporation or its shareholders for damages for any breach of duty in such capacity, except that this provision shall not eliminate or limit the liability of any director if a judgement or other final adjudication adverse to such director establishes that such director’s acts or omissions were in bad faith or involved intentional misconduct or a knowing violation of law or that such director personally gained in fact a financial profit or other advantage to which such director was not legally entitled or that such director’s acts violated section 719 of the Business Corporation Law, nor shall this provision eliminate or limit the liability of any director for any act or omission prior to the adoption of this provision.

     IN WITNESS WHEREOF, we have made and signed this certificate this February 11th A.D. 1997 and we affirm the statements contained therein as truth under penalties of perjury.

/s/ Janice L. Rockey  

Janice L. Rockey, Incorporator 

/s/ Mary Janiszewski  

Mary Janiszewski, Incorporator 

Page 2