PORT OF KODIAK TERMINAL OPERATION CONTRACT City of Kodiak and Horizon Lines of Alaska, LLC

Exhibit 10.41.1

FINAL 03-01-05

PORT OF KODIAK

TERMINAL OPERATION CONTRACT

City of Kodiak and Horizon Lines of Alaska, LLC

This Terminal Operation Contract made and entered into as of January 1, 2005, by and between the City of Kodiak, Alaska, a municipal corporation organized and existing under the laws of the state of Alaska, hereinafter referred to as the “City,” and Horizon Lines of Alaska, LLC, a limited liability company organized under the laws of state of Delaware, hereinafter referred to as the “Operator.”

W I T N E S S E T H

WHEREAS, the parties desire to enter into a Terminal Operation Contract and Operator is willing and able to perform the services; and

WHEREAS, the Operator and the City have entered into a Preferential Use Agreement and a Warehouse Lease Agreement, both dated January 1, 2005, and the City agrees that it is in the best interest of the public for the Operator to provide services for the Port of Kodiak at Piers I, II, and III.

NOW, THEREFORE, in consideration of the terms, covenants, conditions, and agreements herein contained and further enumerated in the Pier II Warehouse Lease Agreement, and Preferential Use Agreement, the Operator and the City hereby agree as follows:

1. Term. This Contract shall continue in effect for a period of fifty-four (54) months commencing on January 1, 2005, and shall continue in full force and effect until midnight June 30, 2009, unless terminated pursuant to the terms of paragraph 14 below.

2. Facility. The City will make available to the Operator that certain terminal and adjacent property at Piers I, II, and III, as depicted in Exhibit A to this Contract, hereinafter referred to as the “Facility.” The City shall have the right to make additions, alterations, or improvements to the Facility which do not impede Operator’s access to or use of the Facility.

3. Terminal Operator Services. The parties recognize that Horizon is a party to a Preferential Use Agreement, hereinafter referred to as the “PUA,” and that Horizon has the right to perform its own stevedoring and shore-side services. Subject to the foregoing and to any future modifications or revisions of the PUA, the Operator at the Facility agrees to perform in a prompt, efficient, prudent, and economical manner the following services:

A. Provide all clerical personnel, laborers, and supervision necessary to perform cargo terminal services.

B. The Operator has the exclusive right to perform loading, discharging, and stevedoring of vessels twenty-four (24) hours per day, seven (7) days per week. Unless services are requested, the following vessels are exempt from using the services of the Operator: vessels of the Alaska Marine Highway System, vessels in port at the invitation of the City for special occasions where the ship will be open to the public, U.S. flagged government vessels, including university research vessels, and vessels seeking fuel or other services from Petro Marine Services. Commercial fishing vessels, catcher-processors and fish processors, and cargo vessels under 300’ are also exempt unless loading or unloading commercial freight or hazardous materials.

FINAL 03-01-05

C. Without limiting the foregoing, the Operator shall:

(1) Perform the stowage of cargo on board vessels in accordance with instructions received from their masters or their designated representatives.

(2) Discharge cargo vessels and transport the cargo or containers to a place of rest in the Facility.

(3) Transport containers between the yard and vessels and load and stow containers onto the vessels.

(4) Lash and unlash cargo on vessels.

(5) Open and close hatches and cells.

(6) Plug and unplug shipboard electrical reefer receptacles if necessary to the extent not performed by the vessels.

(7) Check and tally containers and container seals and cargo.

(8) Spot vessels and handle lines as may be required.

(9) Plan the layout and parking of containers and cargo.

(10) Transport empty and loaded containers within the Facility.

(11) Receive and deliver empty or loaded containers or chassis.

(12) Perform all necessary housekeeping services.

(13) Furnish all security at Pier III, for commercial cargo vessels, in accordance with USCG approved facility security plan, except for cruise ship operations.

(14) Visually inspect the condition of containers and cargo discharged from vessels at the Facility, reporting to the vessels’ masters or agents any damage or defects noted.

(15) Prepare daily reports reflecting the movement of containers or cargo.

(16) Provide expeditious movement of containers and cargo.

(17) Perform such other duties as are reasonable in such operations and as negotiated between the parties involved.

(18) Bill, receive, or attempt to collect and, where applicable, remit to the City, all charges incurred under the applicable Port of Kodiak Tariff by persons, vessels, or cargo utilizing Port facilities or services subject to this Contract.

D. The Operator shall not discriminate for or against any shipper or carrier and shall give due recognition to the priorities afforded by Alaska Marine Highway System and the secondary preferential use of Harbor Enterprises, Inc., dba Petro Marine Services, or its successor at Pier I.

FINAL 03-01-05

4. Definition of Vessel. For the purpose of this Contract, the term “vessel” shall mean and include every type of propelled or non-self propelled vessel, including, without limitation, barges, container vessels, break-bulk vessels, and combinations of break-bulk and container vessels, and all other types of cargo or passenger vessels.

5. Terminal Operator’s Equipment. The Operator will provide all equipment necessary to perform the services required by this Contract.

6. Public Berth. It is agreed that the berths and facilities as above mentioned are public berths and shall be made available to and are available to all types of vessels that may wish to load or unload without discrimination in favor of or against any vessel, shipper, or consignee provided, however, that the City at its option, may determine that a given vessel is unsuitable for servicing at the berth and may prohibit the berthing of such vessel or alternatively may require such vessel owner to post such bond as the City may deem appropriate in the circumstances. Nothing herein contained is to be deemed to allow the berthing or transit of cargo which is prohibited by any applicable law including, without limitations, explosives or other dangerous commodities.

7. Crane.

A. The parties recognize that there is a Paceco 30-ton crane (the “crane”) at Pier III. The Operator’s use of the crane is limited to the loading and unloading of containers only, and the Operator maintains the crane.

B. Operator shall provide competent and qualified operators for the crane who shall be available on a 24-hour basis throughout the term of this Contract to provide crane services to vessels utilizing the Pier III Terminal. Third parties requiring use of the crane shall request such services through Operator and shall be charged at the rate of $1,000.00 per hour, with a minimum of one hour for equipment warm-up plus a minimum of one hour for equipment usage. Operator shall retain $850.00 per hour of this amount and shall remit the balance of $150.00 per hour to the City.

C. It is recognized that some vessels carry on-board cranes or other ship’s gear for the discharging or loading of cargo. In the interests of safety and expeditious handling of cargo, it is agreed that ship’s cranes or ship’s gear may be used for the discharge or loading of cargo unless, in the City’s opinion the ship’s cranes are not suitable for the handling of such cargo.

8. Compensation to City. As and for compensation to the City, the City shall be entitled to all income derived from wharfage, dockage, and sale of water. All such sums shall be a charge against the vessel or cargo, as the case may be, and shall be collected by the Operator and remitted by the Operator to the City. Such remittances shall be accompanied by appropriate itemized documentation. Charges shall be paid by the Operator to the City within ninety (90) days after the first billing to the vessel or cargo, as the case may be or within ten (10) working days of receipt of payment by the Operator, whichever is less, provided that credit terms shall be those chosen by the Operator. All such billings to the vessels and cargo will be itemized for services rendered by the Operator and shall be made promptly after performance of those services.

9. Compensation to Operator. The Operator shall be entitled to keep all other charges (including charges for electrical energy, storage, and the movement of cargo) authorized

FINAL 03-01-05

and fixed in accordance with the applicable Port of Kodiak Tariff. The Operator shall be bound by any future modification or amendments of the Port of Kodiak Tariff; provided, however, the City shall not alter the credit terms of the tariff during the term of this Contract. When charges involve stevedoring or other labor services based upon an hourly wage rate, then the Operator may add to the total applicable labor charge an administrative fee of thirty percent (30%) and shall collect such fee from the person or vessel requiring the services in question. In no event, however, shall the Operator charge or collect an administrative fee with respect to any portion of its labor costs, which are based upon or derived from wage rates exceeding those applicable to similar work under contracts or agreements subject to the Davis-Bacon Act. If, on the date of execution of this Contract, there exists a labor organization which represents a majority of the individuals living in or around Kodiak, Alaska, who earn their livelihood as stevedores or longshoremen, then the Operator shall make reasonable good-faith efforts to negotiate a collective bargaining agreement with said labor organization for the provision of stevedoring labor services under this Contract.

10. Indemnification.

A. The Operator, in operating pursuant to this Contract, is an independent contractor, and is in no way an agent, servant, or employee of the City. The Operator shall be responsible for and shall indemnify, defend, and hold the City harmless from and against any and all claims, demands, and causes of action which arise out of or relate to the operation of this Contract, including, but not limited to any and all claims alleging that the negotiation, execution, or performance of this Contract violates or contravenes any federal, state, or local law or regulation. The only exception to this indemnity provision shall be for claims resulting from the negligence, gross negligence, or willful misconduct of the City or its employees, agents, or servants, with respect to which the Operator’s obligations under this paragraph shall be limited to that portion of any such claim not attributable to the City.

B. Notwithstanding any provision of this Contract, Operator shall not be liable for, and shall not be liable to indemnify, defend or hold the City harmless from, any condition at the Facility, whether known or unknown, which was in existence before July 1, 2004.

11. Bond. The Operator, at its sole expense, shall furnish the City with employee fidelity coverage in the amount of $50,000, naming the City as a loss payee, covering embezzlement or mysterious disappearance of funds that may have been collected by the Operator for the benefit of the City as provided in Paragraphs 7 and 8 above.

12. Insurance. The Operator shall carry, at its sole expense, comprehensive general liability insurance, comprehensive automobile liability insurance (or equivalent coverage), contractual liability, and personal injury liability insurance, all with a combined single limit of at least one million dollars per occurrence naming the City, as well as, the Operator as insureds. The Operator shall provide to the City evidence of insurance in an amount not less than $50,000 for loss due to property lost or stolen while in the Operator’s custody or control or while the Operator is otherwise acting pursuant to this Contract. The Operator shall provide to the City proof of Workmen’s Compensation and U.S. Longshoremen and Harbor Worker’s Compensation insurance or compliance with the self-insuring requirements of the State of Alaska. The insurance coverage to be obtained by the Operator pursuant to this paragraph shall be non-cancelable except upon at least thirty days prior written notice to the City and the insurer shall

FINAL 03-01-05

unconditionally covenant in said insurance policy or policies. Operator shall obtain the agreement of the insurer, through endorsement or otherwise, to tender to the City thirty days written notice of expiration or termination of any such policy or policies. The Operator shall provide the City with proof of such insurance and bonding pursuant to this paragraph and Paragraph 11 above prior to the effective date of this Contract, and this Contract shall not become effective until and unless such proof is made.

13. Damage to the Wharf Facilities and Improvements. The Operator shall pay for all damage to City-owned property caused by the negligence of the Operator, its agents, employees, or invitees. The City shall make the Operator an additional insured, as its interests may appear, on any policy or policies of insurance the City may secure in contemplation of such risk.

14. Default and Termination.

A. The term of this Contract is for a fifty-four (54) month period described in Paragraph 1 above. Notwithstanding the foregoing, the City retains the right to declare a default hereunder and terminate the Contract should the Operator fail to perform any covenant hereof or pay any sum due hereunder within thirty (30) days after written notice specifying the alleged violation or default by the Operator.

B. During the term of this Agreement, both Operator and the City shall have the option to terminate this Agreement early, with 30 days notice, by either party giving written notice of its election to do so. In the event of any such early termination, the City and Operator shall each fully, faithfully, and timely perform all of their obligations under this Agreement through such early termination date.

15. Inspection of Books. The City reserves the right at any reasonable time after seven days written notice to Operator to inspect and make copies of the books and records of the Operator related to operations conducted pursuant to this Contract. The Operator agrees that cargo manifests shall not be released by Operator to a third party except in accordance with the laws of the United States.

16. Non-Assignability. The parties stipulate and agree that the services rendered under this Contract are of such a nature that the rights and duties arising to the Operator hereunder shall not be delegable or assignable to another party without the prior written consent of the City, which consent shall not be unreasonably withheld. Nothing in this paragraph is intended, however, to restrict the Operator in its selection of employees to carry out this Contract or any of its terms. Furthermore, notwithstanding the foregoing, the Operator shall have the right to assign this Contract to any corporation, the stock of which is owned solely by the Operator, after thirty (30) days prior notice to the City, or to any affiliate of Operator after five (5) days prior notice to the City, provided that Operator shall remain primarily responsible to the City for the due performance of this Contract during any period of assignment. A change of control of Operator does not constitute a delegation or assignment for purposes of this provision.

17. Compliance with Federal, State, and Local Laws. At all times during the Contract period, the Operator shall conduct operations in accordance with all applicable federal, state, and local laws and ordinances.

18. Severability. If any part, term or provision of this Agreement is declared null or unenforceable by a court of competent jurisdiction, the validity and enforceability of the rest of this Agreement shall not be affected.

FINAL 03-01-05

19. Waivers. No waiver by Operator or the City of any covenant or condition of this Agreement shall be construed as a waiver of any other covenant of condition, nor shall the waiver of one breach be considered as a waiver of any other breach.

20. Modifications and Notices.

A. No modification of this Agreement shall be effective unless submitted in writing and agreed to by Operator and the City in writing. No modification of one provision of this Agreement shall be considered a waiver, breach or cancellation of any other provision.

B. All notices required to be given under this Agreement shall be effective on the date of receipt and shall be mailed to the parties at the following addresses:

Horizon Lines of Alaska, LLC

1717 Tidewater Road

Anchorage, Alaska 99501

City Manager

City of Kodiak

710 Mill Bay Road, Room 220

Kodiak, Alaska 99615

Any notice or document delivered by facsimile transmission to a facsimile machine at which the recipient routinely receives such transmissions shall be effective upon the date of receipt of the complete and fully legible document (so long as the original is also mailed in accordance with this paragraph) unless the transmission occurred outside of the usual business hours of the recipient, in which event the document shall be deemed to have been received on the next business day.

21. Alaska Law. The parties agree that this Agreement was entered into in the State of Alaska, that Alaska law will govern its interpretation and application, and that venue of any suit or other action arising out of this Agreement shall be in Alaska.

22. Binding on Successors and Assigns. All provisions of this Agreement shall inure to the benefit of and be binding on the parties, their successors, and permitted assigns.

23. Complete Agreement. This Agreement, including Exhibit A, hereto, and the Preferential Use Agreement and Warehouse Lease Agreement, both dated January 1, 2005, between the Operator and the City, constitute the final agreement between the parties. They are the complete and exclusive expression of the parties’ agreement on the matters contained in this Agreement. All prior and contemporaneous oral and written negotiations and agreements between the parties on the matters contained in this Agreement are expressly merged into and superseded by the aforementioned agreements.

FINAL 03-01-05

IN WITNESS WHEREOF, these parties have signed this Agreement on the date or dates indicated beneath the signature of their respective officers or agents.