Dynamic Planning of Pickup and Delivery Operations by means of Genetic Algorithms

Customers are making increasing demands on the flexibility and the promptness of transportation services. In order to meet these requirements, planning methods are needed which are able to intelligently react on dynamically revealed information. Algorithms for dispatching transportation requests which arrive dynamically during the planning period can contribute to this goal. In this paper a Genetic Algorithm based approach for the Dynamic Pickup and Delivery Problem with Time Windows (DPDPTW) is developed. First, a Genetic Algorithm for the (static) PDPTW is described which features a special group-oriented genetic encoding. In order to be able to solve the dynamic problem, the Genetic Algorithm is embedded in a rolling horizon framework. Special synchronization and updating mechanisms are provided which assure that the reusable solution knowledge in the population is preserved over the plan revisions. The approach is evaluated using a large number of problem instances with varying degrees of dynamism.