An IP based heuristic algorithm for the Vehicle and Crew Scheduling Pick-up and Delivery Problem with Time Windows

DAMIÁN BAKARCIC; GABRIELA DI PIAZZA; ISABEL MÉNDEZ-DÍAZ; PAULA ZABALA

Enschede

Workshop; 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization - CTW2013; 2013

In this paper we address the Vehicle and Crew Scheduling Pick-up and Delivery Problemwith Time Windows (VCSPDPTW herein): a real life problem involving the planning of thepick-up and delivery of a set of merchandise requests according to certain time restrictions and based on a set of available vehicles. In addition, the allocation of crews to the vehicles which perform each task must also be scheduled.The objective is to provide a planning, that is, a set of routes for the vehicles and a schedule for the crew, over a given time horizon of T days, in order to ensure that all requests are accomplished at minimum operation costs. These costs are only associated with the vehicle routes and are composed of the total travel distance, the penalty in the delay of drop-os, and a special penalty associated with travelling without a load. The proposed solution involves stating the problem as an integer programming model in combination with a column generation approach, in which we generate the columns associated with the vehicle routes.