Solving the General Pick-up and Delivery Problem with Time Windows by a Column Generation Strategy

DONDO RODOLFO; CERDÁ JAIME; MENDEZ CARLOS

Montevideo, República Oriental del Uruguay

Congreso; XIII Congreso Latino-Iberoamericano de Investigación Operativa (CLAIO 2006); 2006

Universidad de la República

This work presents an  incomplete column-generation algorithm able to obtain (near)optimal solutions to realistic pick-up and delivery problems (PDP) while considering several operative costs. As in other column-generation algorithms, our procedure involves the solution of the master set partitioning problem but as slave tour-generation problem we use a original MILP formulation that is able to handle the complex side-constraints involved in the general PDP. This formulation tackles nodes assignment and nodes sequencing decisions trough different sets of binary variables and it is based on a continuous cost/time/load representation. A benchmark problem with 104 visit-nodes and its real-world-oriented modification  have been solved to optimality in low CPU times.