Contract Net Protocol based Insertion Approach for the Dynamic multi-vehicle Pick-up and Delivery Problem

Abstract

In this paper, we investigate in the application of the Contract Net negotiation Protocol (CNP) to deal with a dynamic hard transportation problems. Our interest in the Multi-agent negotiation approaches accounts for its proved suitablity with dynamic and uncertain domains [8][9]. We address the resolution of the uncapacitated-multi-vehicle-Dynamic Pickup and Delivery Problem with Time Windows m-DPDPTW, which is applied in the real world to the courier distribution services. This problem consists in finding the least cost routing allowing to satisfy requests of carrying items from pick-up locations to delivery ones, while dynamic requests continuously come to the planning center [4]. Our problem is implemented into a multi-agent system where cooperative agents representing the transporters and planning center negotiate possible m-DPDPTW solutions under the Contract Net Protocol[17][20].