Solving the general pick-up and delivery problem with time windows by a column generation strategy

R. DONDO; J. CERDÁ; C.A. MÉNDEZ

Montevideo, Uruguay

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

Operations Research Department of the University of the Republic of Uruguay

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.