The authors have previously introduced the concept of building a delivery network using an agent-based system. The delivery networks are built in response to a real-world problem that involves delivering post to a large number of households within an urban area. The initial agent based system worked to primarily resolve hard constraint violations. To further improve the solution obtained by the agents, we propose to allow agents to negotiate exchanges of work. We demonstrate the solution obtained may be further improved by allowing such negotiated transactions.