A suitable method for distributed transportation scheduling is necessary for the development of an agent-based logistics support system for the Australian Defence Force. Manager Agents (MA) require resources to be transported, in large quantities and on a global scale, using the services of many Transport Agents (TA). In this paper, we investigate the application of Fisher?s Extended Contract Net Protocol (ECNP) to our transportation domain. ECNP provides a distributed and reactive approach to transportation scheduling that is fairly suited to this domain, but has its shortfalls. This includes the inability for TA to bid for partial routes, in addition to partial quantities, for a transportation task. A new protocol is proposed, based on ECNP, called the Provisional Agreement Protocol (PAP), which overcomes these shortfalls. Five speech acts, together with policies regarding the persistence and commitment of tasks and bids, are proposed. This allows agents to revisit bid options that were previously selected, and thus accomodates bidding for partial routes.